虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。

本章的前一部分描述虚拟内存工作原理，后一部分描述应用程序如何使用和管理虚拟内存。

9.1 物理和虚拟寻址

物理寻址 (physical addressing)：计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址（Physical Address, PA).

物理地址应用：早期的PC，而诸如数字信号处理器、嵌入式微控制器（汽车、电梯、数字图像帧等）以及Cray超级计算机仍然继续使用这种寻址方式。

PhysicalAddressing

虚拟寻址 (virtual addressing)：CPU 通过生成一个虚拟地址 (Virtual Address, VA)来访问主存，这 个虚拟地址在被送到内存之前先转换成适当的物理地址。

地址翻译 (address translation)：个虚拟地址转换为物理地址

内存管理单元 (Memory Management Unit, MMU)：利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

VirtualAddressing

9.2 地址空间

  • 地址空间 (address space)：非负整数地址的有序集合
  • 线性地址空间 (linear address space)：地址空间中的整数是连续的
  • 虚拟地址空间 (virtual address space)： 个虚拟地址的集合，现代系统通常支持32位或者64位虚拟地址空间
  • 物理地址空间 (physical address space)： 个（不要求，但假设）物理地址的集合

虚拟地址思想：允许每个数据对象有多个独立的地址，每个地址都选自一个不同的地址空间。

9.3 虚拟内存作为缓存工具

虚拟内存被组织为一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存在主存中。

VM 系统通过将虚拟内存分割为称为虚拟页 (Virtual Page, VP)的大小固定的块来作为磁盘（低层）和主存（高层）之间的传输单元，页面大小 字节 相似地，物理内存也分为物理页 (Physical Page, PP)，大小也为 字节 物理页也被称为页帧。

虚拟页面三种状态
未分配 VM 系统还未分配(或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间（虚拟页也是根据需要创建的）。
已缓存 当前已缓存在物理内存中的已分配页。
未缓存 当未缓存在物理内存中的已分配页。
example1

使用虚拟内存优点

  • 有效使用主存：使用DRAM作为作为部分虚拟地址空间的缓存
  • 简化内存管理：每个进程都使用统一的线性地址空间
  • 独立空间地址：一个进程不能影响其他进程内存，用户程序无法获得特权内核信息和代码

9.3.1 DRAM 缓存的组织结构

DRAM 缓存的组织结构完全是由巨大的不命中开销驱动的。DRAM比SRAM要慢大约10倍，而磁盘要比DRAM慢大约100000多倍。

由于大的不命中处罚和访问第一个字节开销：虚拟页尺寸通常是4KB~4MB

由于大的不命中处罚，DRAM 缓存全相联 任何虚拟页都可以放置在任何的物理页中。？？？？？？？？？？？？？ 需要一个更大的映射函数，不同于硬件对SRAM缓存

硬件对 SRAM 缓存相比，操作系统对 DRAM 缓存使用了更复杂精密的替换算法。

DRAM 缓存总是使用写回，而不是直写。

9.3.2 页表

虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在 DRAM 中的某个地方。如果是，系统还必须确定这个虚拟页存放在哪个物理页中。如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到 DRAM 中，替换这个牺牲页。

页表将虚拟页映射到物理页：页表就是一个页表条目 (Page Table Entry, PTE)的数组，将虚拟页地址映射到物理页地址。每个页在页表中一个固定偏移量处都有一个 PTE。

我们将假设每个 PTE 是由一个有效位 (valid bit)和一个n位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在 DRAM 中。 - 有效位1，地址字段表示 DRAM 中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。 - 有效位0，那么一个空地址表示这个虚拟页还未被分配。 - 有效位0，地址不为空，这个地址就指向该虚拟页在磁盘上的起始位置。

PageTable

数量 其中，n 为虚拟地址大小，P 为页大小。

9.3.3 页命中 Page Hit

页命中：虚拟内存中的一个字存在于物理内存中 (DRAM缓存命中)。虚拟地址 -> 定位PTE -> 从内存读取

PageHit

9.3.4 缺页 Page Fault

缺页：引用虚拟内存中的字，不在物理内存中 (DRAM 缓存不命中)。

缺页处理：关键是按需页面调度/交换，当有不命中时页从磁盘换入（或者页面调入）DRAM 和从 DRAM 换出（或者页面调出）磁盘。 1. 从有效位判断未缓存，触发缺页异常 2. 调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，牺牲页如果已经被修改则复制回磁盘。 3. 内核从磁盘复制 VP 到内存中的 PP, 更新 PTE，随后返回 4. 重新启动导致缺页的指令，命中！

PageFault1 PageFault2

9.3.5 分配页面

操作系统分配一个新的虚拟页面（如malloc结果），内核在磁盘上分配 VP5，将 PTE5 指向这个新创建的页面。

AllocatePage

9.3.6 局部性

  • 虚拟内存看上去效率低，但是工作相当好，归功于“局部性”。
  • 程序引用的不同页面的总数可能超出物理内存总的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面(active page)集合上工作，这个集合叫做工作集(working set)或者常驻集合(resident set)。程序的局部性越好，工作集越小。
  • 工作集大小 < 物理内存大小：初始开销，即将工作集页面调度到内存中之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。
  • 工作集大小 > 物理内存大小：抖动（thrashing)页面不断换进换出，导致程序性能暴跌。

9.4 虚拟内存作为内存管理的工具

核心思想：每个进程都拥有独立的虚拟地址空间。

  • 简化链接
    • 每个程序都有相似的虚拟地址空间
    • 代码、数据和堆都使用相同的起始地址
    • 每个进程的内存映像使用相同的基本格式，这样的一致性极大地简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。
  • 简化加载
    • Linux 加载器 (execve)为代码和数据段分配虚拟页，把它们标记为无效的（即未被缓存的）将页表条目指向目标文件中适当的位置。
    • 每个页面被初次引用时，虚拟内存系统会按照需要自动的调入数据页。
  • 简化内存分配
    • 当一个运行在用户进程中的程序要求额外的堆空间时（如调用 malloc），操作系统分配一个适当数字，如k个连续的虚拟内存页面，并且将它们映射到物理内存中任意位置的k个任意的物理页面。由于页表工作的方式，操作系统没有必要分配是个连续的物理内存页面。物理页面可以随机地分散在物理内存中。
    • 每个虚拟内存页面都要映射到一个物理页面
    • 一个虚拟内存页面每次可以分配到不同的物理页面
  • 简化共享
    • 不同的虚拟页面映射到相同的物理页面
    • 一般来讲还是需要进程共享代码和数据，而不是给每个进程创建完全私有的代码、数据、堆以及栈区域
Management

9.5 虚拟内存作为内存保护的工具

在PTE（页表条目）上扩展许可位来控制对一个虚拟页面内容的访问，内存管理单元 (MMU) 每次访问数据都要检查许可位。

Protection

如图所示三个许可位：SUP 位表示进程是否必须运行在内核(超级用户）模式下才能访问该页。运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些 SUP 为 0 的页面。READ 位和 WRITE 位控制对页面的读和写访问。

9.6 地址翻译

symbols

地址翻译是一个 iV 元素的虚拟地址空间（VAS)中的元素和一个 M 元素的物理地址空间(PAS)中元素之间的映射:

虚拟地址处的数据在的物理地址处虚拟地址处的数据不在物理内存中

AddressTranslationBasedOnPageTable

CPU 中的一个控制寄存器，页表基址寄存器（Page Table Base Register, PTBR)指向当前页表。n 位的虚拟地址包含两个部分：一个 p 位的虚拟页面偏移(Virtual Page Offset，VPO)和一个(n-p)位的虚拟页号(Virtual Page Number, VPN)。MMU 利用 VPN 来选择适当的 PTE。例如，VPN 0 选择 PTE 0, VPN 1选择 PTE 1，以此类推。将页表条目中物理页号(Physical Page Number, PPN)和虚拟地址中的 VPO 串联起来，就得到相应的物理地址。注意，因为物理和虚拟页面都是 P 字节的，所以物理页面偏移(Physical Page Offset, PPO)和 VPO 是相同的。

地址翻译：页面命中

  1. 处理器生成一个虚拟地址，并把它传送给 MMU。
  2. MMU 生成 PTE 地址，并从高速缓存/主存请求得到它。
    • PTE 地址(PTEA)：%CR3 + 页号 * 字节数
  3. 高速缓存/主存向 MMU 返回 PTE。
  4. MMU 构造物理地址，并把它传送给高速缓存/主存。
  5. 高速缓存/主存返回所请求的数据字给处理器。

地址翻译：缺页异常

  1. 处理器生成一个虚拟地址，并把它传送给 MMU。
  2. MMU 生成 PTE 地址，并从高速缓存/主存请求得到它。
    • PTE 地址(PTEA)：%CR3 + 页号 * 字节数
  3. 高速缓存/主存向 MMU 返回 PTE。
  4. PTE 中的有效位是零，所以 MMU 触发了一次异常，传递 CPU 中的控制到操作系统内核中的缺页异常处理程序。
  5. 缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘（写回策略）。
  6. 缺页处理程序页面调入新的页面，并更新内存中的 PTE。
  7. 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。
TranslationPageFault

9.6.1 结合高速缓存和虚拟内存

CacheAndMemory

9.6.2 利用 TLB 加速地址翻译

页表条目 (PTEs) 与其他内存数据字一样缓存在 L1中。每次 CPU 产生一个虚拟地址，MMU 就必须查阅一个 PTE, 以便将虚拟地址翻译为物理地址。 + PTE可能被其他数据引用所替换/驱逐，导致不命中，从内存多取一次数据，代价是几十到几百个周期。 + PTE 碰巧缓存在 L1 中（Cache 命中），那么开销仍需要 1~2 个周期。

翻译后备缓冲器 (Translation Lookaside Buffer, TLB)：MMU中一个小的具有高相联度的存储集合。

用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果 TLB 有： 个组，那么 TLB 索引(TLBI)是由 VPN 的 t 个最低位组成的，而 TLB 标记(TLBT)是由 VPN 中剩余的位组成的。

  1. CPU 产生一个虚拟地址.

  2. MMU 根据 VPN 标记索引

  3. 从 TLB 中取出相应的 PTE

VPNTLBPTE

  1. MMU 将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。

  2. 高速缓存/主存将所请求的数据字返回给 CPU。

当 TLB 不命中时，MMU 必须从 L1 缓存中取出相应的 PTE。新取出的 PTE 存放在 TLB 中，可能会覆盖一个已经存在的条目。因为局部性，TLB不命中很少发生。

TLB

9.6.3 多级页表