深入理解计算机系统—虚拟内存（一）

        一个系统中的进程是与其他进程共享 CPU 和主存资源的。然而，共享主存会形成特殊的挑战。随着对 CPU 需求的增长，进程以某种合理的平滑方式慢了下来。但是如果太多的进程需要太多的内存，那么它们中的一些就根本无法运行。

        为了更加有效地管理内存并且少出错，现代系统提供了一种对主存的抽象概念，叫做虚拟内存（VM）。虚拟内存是硬件异常，硬件地址翻译，主存，磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的，一致的和私有的地址空间。

        通过一个清晰的机制，虚拟内存有三个重要能力

        ① 它将主存看成一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，高效地使用了主存。

        ② 为每个进程提供了一致的地址空间，从而简化了内存管理。

        ③ 保护了每个进程的地址空间不被其他进程破坏

 9.1 物理和虚拟地址

        计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址。第一个字节的地址为 0，接下来为 1 以此类推。 CPU 访问内存的最自然的方式就是使用物理地址。这种方式称为物理寻址。 图 9-1 展示了一个物理寻址的示例，该示例的上下文是一条加载指令，它读取从物理地址4处开始的4字节字。当CPU 执行这条加载指令时，会生成一个有效物理地址，通过内存总线，把它传递给主存。主存取出从物理地址 4 处开始的4字节字，并把它返回给 CPU，CPU会将它存放在一个寄存器里。

         早期的 PC 使用物理寻址，而且诸如数字信号处理器，嵌入式微控制器以及Cray超级计算机这样的系统仍然继续使用这种寻址方式。然而，现代处理器使用的是一种称为虚拟寻址的寻址形式

         使用虚拟寻址，CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到内存之前先转化成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译。就像异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。 CPU 芯片上叫做内存管理单元的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

9.2 地址空间

        地址空间是一个非负整数地址的有序集合：{0，1，2,,,,,,}

        如果地址空间中的整数是连续的，那么我们说它是一个线性地址空间。为了简化讨论，总是假设使用的是线性地址空间。在一个带虚拟内存的系统中，CPU 从一个有 N=2^n 个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间：{0,1,2,,,,N-1}

        一个地址空间的大小是由表示最大地址所需要的位数来描述的，例如，一个包含 N=2^n 个地址的虚拟地址空间就叫做一个 n 位地址空间。现代系统通常支持 32 位或 64 位虚拟地址空间。

        一个系统还有一个物理地址空间，对应于系统中物理内存的 M 个字节： {0,1,2,,,M-1}

   M 不要求是 2 的幂，但是为了简化讨论，假设 M=2^m

        地址空间的概念很重要，它清楚地区分了数据对象（字节）和它们的属性（地址）。一旦认识这种区别，就可以推广，允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。这是虚拟内存的基本思想，主存中的每字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。 

9.3 虚拟内存作为缓存的工具

        概念上，虚拟内存被组织为一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存在主存中。和存储器层次结构中其他缓存一样，磁盘（较低层）上的数据被分割成块，这些块作为磁盘和主存（较高层）之间的传输单元。  VM 系统通过将虚拟内存分割为称为虚拟页的大小固定的块来处理这个问题，每个虚拟页的大小为 P=2^p 字节。类似的，物理内存被分割为物理页，大小也为 P 字节 （物理页被称为页帧）

        在任何时候，虚拟页面的集合部分都分为三个不相交的子集：

         ① 未分配的：VM 系统还未分配(或创建)的页，未分配的块没有任何数据和它们相关联，因此不占用任何磁盘空间。

        ② 缓存的：当前已缓存在物理内存中的已分配页

        ③ 未缓存的：未缓存在物理内存中的已分配页。

图 9-3 的示例展示了一个有 8 个虚拟页的小虚拟内存。虚拟页 0 和 3 还没有被分配，因此在磁盘上还不存在。虚拟页 1 4 6 被缓存在物理内存中。页2 5 7已经被分配了，但是当前并未缓存在主存中。

        

9.3.1 DRAM 缓存的组织结构

        有助于清晰理解存储器层次结构中不同的缓存概念，用 SRAM 缓存 来表示位于 CPU 和 主存之间的 L1 L2 L3 高速缓存，并且用 DRAM缓存 来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。         

        在存储器层次结构中，DRAM缓存 的位置对它的组织结构有很大影响。DRAM 比 SRAM 要慢大约 10 倍，而磁盘要比 DRAM 慢大约 100 000 多倍。因此，DRAM 缓存中的不命中比起 SRAM 缓存中的不命中要昂贵很多，因为 DRAM 缓存不命中要由磁盘来服务，而 SRAM 缓存不命中通常是由基于DRAM 的主存来服务的。 而且，从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约 100 000 倍，归根到底，DRAM 缓存的组织结构完全是由巨大的不命中开销驱动的。 

        因为大的不命中处罚和访问第一个字节的开销，虚拟页往往很大，通常是 4KB~2MB。由于大的不命中处罚，DRAM 缓存是全相联的，即任何虚拟页都可以放置在任何物理页中，不命中时的替换策略也很重要，因为替换错了虚拟页的处罚也非常之高。因此，与硬件对SRAM缓存相比，操作系统对 DRAM 缓存使用了更复杂精密的替换算法。最后，因为对磁盘的访问时间很长，DRAM 缓存总是使用写回，而不是直写。

9.3.2 页表

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

        这些功能是由软硬件联合提供的，包括操作系统软件，MMU（内存管理单元）中的地址翻译硬件和一个存放在物理内存中叫做页表的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表，操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页。

         图 9-4 展示了一个页表的基本组织结构。页表就是一个页表条目（PTE）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE。为了目的，每个 PTE 是由一个有效位和一个 n 位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在 DRAM 中。如果设置了有效位，那么地址字段就表示 DRAM 中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么一个空地址表示这个虚拟页还未被分配。否则，这个地址就指向该虚拟页在磁盘上的起始位置。

        图9-4中的示例展示了一个有 8 个虚拟页和 4个物理页的系统的页表。四个虚拟页（VP1，VP2，VP4 和 VP7）当前被缓存在 DRAM 中。两个页（VP0 VP5）还未被分配，而剩下的页（VP3 VP6）已经被分配了，但是当前还未被缓存。图 9-4 中一个要点，因为 DRAM 缓存是全相联的，所以任意物理页都可以包含任意虚拟页。

 9.3.3 页命中

        考虑下当CPU想要读包含在 VP2 中的虚拟内存的一个字时发生什么，VP2 被缓存在 DRAM 中。这里将使用 9.6 节中详细描述的一种技术，地址翻译硬件将虚拟地址作为一个索引来定位 PTE2，并从内存中读取它。因为设置了有效位，那么地址翻译硬件就知道 VP2 是缓存在内存中的，所以使用 PTE 中的物理内存地址（该地址指向 PP1 中缓存页的起始位置），构造出这个字的物理地址。

        9.3.4 缺页

        在虚拟内存的习惯说法中，DRAM缓存不命中称为缺页。图 9-6 展示了在缺页之前示例页表的状态。 CPU 引用了 VP3 中的一个字，VP3 并未缓存在 DRAM 中。地址翻译硬件从内存中读取 PTE 3，从有效位推断出 VP3 并未缓存，并且触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在 PP3 中的 VP4。如果 VP4 已经被修改了，那么内核就会将它复制回磁盘。无论哪种情况，内核都会修改 VP4 的页表项目，反映出 VP4 已经不再缓存在主存中。

        接下来，内核从磁盘复制 VP3 到内存中的 PP3，更新 PTE 3，随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在，VP3 已经缓存在主存中，那么页命中也能由地址翻译硬件正常处理了。

        虚拟内存系统使用了和 SRAM 缓存不同的术语，即使它们的许多概念相似。在虚拟内存的习惯说法中，块被称为页。在磁盘和内存之间传送页的活动叫做 交换 或 页面调度。页从磁盘换入（或页面调入）DRAM 和 从DRAM换出（或页面调出） 磁盘。一直等待，直到最后，当有不命中发生时，才换入页面的这种策略叫做按需页面调度。也可以采用其他方法，例如尝试预测不命中，在页面实际被引用前就换入页面.然而，所有现代系统都使用按需页面调度的方式。

9.3.5 分配页面

        图 9-8 展示了当前操作系统分配一个新的虚拟内存页时对我们示例页表的影响，例如，调用malloc 的结果，在示例中，VP5 的分配过程是在磁盘上创建空间并更新 PTE5 ，使它指向磁盘上这个新创建的页面。

9.3.6 局部性

        尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存总的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面集合上工作，这个集合叫做工作集或者常驻集合。在初始开销，也就是将工作集页面调度到内存之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。

        只要程序有好的时间局部性，虚拟内存系统就能工作的相当好。但是，当然不是所有的程序都能展现良好的时间局部性。如果工作集的大小超出了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动，这时页面将不断地换进换出。虽然虚拟内存通常是有效的，但是如果一个程序性能慢得像爬一样，那么聪明的程序员会考虑是否发生了抖动。

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

         上一节中，虚拟内存如何提供一种机制，利用 DRAM 缓存来自通常更大的虚拟地址空间的页面。然而早期一些系统，支持的是一个比物理内存更小的虚拟地址，但虚拟地址仍然是一个有用的机制，它大大简化了内存管理，并提供了一种自然的保护内存的方法。

        到目前，假设有一个单独的页表，将一个虚拟地址空间映射到物理地址空间。实际上，操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。 图9-9 展示了基本思想，在这个示例中，进程 i 的页表将 VP1 映射到 PP2 ，VP2 映射到PP7.相似的，进程j 的页表将 VP1映射到 PP7，VP2 映射到 PP10。注意，多个虚拟页面可以映射到同一个共享物理页面上

         

按需页面调度和独立的虚拟地址空间的结合，对系统中内存的使用和管理造成了深远影响。特别的，VM 简化了链接和加载，代码和数据共享，以及应用程序的内存分配。 

        ① 简化链接：独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。例如，像我们在图8-13中看到的，一个给定的 Linux 系统上的每个进程都使用类似的内存格式。对于 64 位地址空间，代码总是从虚拟地址 0x400000 开始。数据段跟在代码段之后，中间有一段符合要求的对齐空白。栈占据用户进程地址空间最高的部分，并向下生长。这样的一致性极大地简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置。

        ② 简化加载：虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。要把目标文件中.text 和 .data 节加载到一个新创建的进程中，Linux 加载器为代码和数据段分配虚拟页，把它们标记为无效的（未被缓存的），将页表条目指向目标文件中适当的位置。有趣的是，加载器从不 从磁盘到内存实际复制任何数据。 在每个页初次被引用时，要么是 CPU 取指令时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页。

 将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作 内存映射。 Linux 提供一个称为 mmap 的系统调用，允许应用程序自己做内存映射。在9.8节更详细描述应用级内存映射。 

        ③ 简化共享 。独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。一般而言，每个进程有自己私有的代码，数据，堆以及栈区域，是不和其他进程共享的。在这种情况中，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。

然而一些情况中，还是需要进程来共享代码和数据。例如，每个进程必须调用相同的操作系统内核代码，而每个C程序都会调用 C标准库中的程序，比如 printf。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分页码的一个副本，而不是在每个进程中都包括单独的内核和C标准库的副本，如图9-9。 

        ④ 简化内存分配。虚拟内存向用户进程提供一个简单的分配额外内存的机制。当一个运行在用户进程中的程序要求额外的堆空间时（如调用 malloc 的结果），操作系统分配一个适当数字（例如 k ）个连续的虚拟内存页面，并将它们映射到物理内存中任意位置的 k 个任意的物理页面。由于页表工作的方式，操作系统没有必要分配 k 个连续的物理内存页面，页面可以随机地分散在物理内存中。

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

        任何现代计算机系统必须为操作系统提供手段来控制对内存系统的访问。不应该允许一个用户进程修改它的只读代码段，而且也不应该允许它读或修改任何内核中的代码和数据结构。不应该允许它读或者写其他进程的私有内存，并且不允许它修改任何与其他进程共享的虚拟页面，除非所有的共享者都显示地允许它这么做（通过调用明确的进程间通信系统调用）。

        提供独立的地址空间使得区分不同进程的私有内存变得容易。但是，地址翻译机制可以以一种自然的方式扩展到提供更好的访问控制。 因为每次 CPU 生成一个地址时，地址翻译硬件都会读一个 PTE，所以通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单

         在这个示例中，每个 PTE 中添加了三个许可位。SUP 位表示进程是否必须运行内核（超级用户）模式下才能访问该页。 运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些 SUP 为 0 的页面。READ 位 和 WRITE 位控制对页面的读和写访问。例如，如果进程 i 运行在用户模式下，那么它有读 VP0 和 写 VP1 的权限，然而不允许访问VP2

        如果一条指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell 一般将这种异常报告为“ 段错误 ”。 

9.6 地址翻译

         这一节内容关于地址翻译的基础知识，了解硬件在支持虚拟内存中的角色。图 9-11 概括了这节使用的所有符号。

         形式上说，地址翻译是一个 N 元素的虚拟地址空间（VAS）中的元素和一个M元素的物理地址空间（PAS）中元素之间的映射：

         图 9-12 展示了 MMU 如何利用页表来实现这种映射。CPU 中的一个控制寄存器，页表基址寄存器（PTBR）指向当前页表。 n 位的虚拟地址包含两个部分：一个 p 位的虚拟页面偏移（VPO）和一个（n-p）位的虚拟页号（VPN）。MMU 利用 VPN 来选择适当的 PTE。例如，VPN 0 选择 PTE 0，VPN1 选择 PTE1，以此类推。将页表条目中物理页号（PPN）和虚拟地址中的VPO串联起来，就能得到相应的物理地址。注意，因为物理和虚拟页面都是P字节的，所以物理页面偏移和VPO是相同的。

 图 9-13a 展示了当前页面命中时，CPU硬件执行的步骤：

        ① 处理器生成一个虚拟地址，并把它传送给 MMU

        ② MMU 生成一个PTE 地址，并从高速缓存/主存请求得到它。

        ③ 高速缓存/主存向 MMU 返回 PTE。

        ④ MMU 构造物理地址，并把它传送给高速缓存/主存中。

        ⑤ 高速缓存/主存返回所请求的数据字给处理器。

         页面命中完全是由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完成，如图 9-13b。

        ① ~ ③ ：如图9-13a中的第1步到第3步相同

        ④：PTE 中的有效位是 0，所以 MMU 触发了一次异常，传递 CPU 中的控制到操作系统内核中的缺页异常处理程序。

        ⑤：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。

        ⑥ ：缺页处理程序页面调入新的页面，并更新内存中的PTE。

        ⑦： 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，在 MMU 执行了图9-13b 中的步骤之后，主存就会将所请求字返回给处理器。 

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

         在任何既使用虚拟内存又使用 SRAM 高速缓存的系统中，都有应该使用虚拟地址还是物理地址来访问 SRAM 高速缓存的问题。但大多数系统是选择物理寻址，使用物理寻址，多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块成为很简单的事情。而且高速缓存无需处理保护问题，因为访问权限的检查是地址翻译的一部分。

        图 9-14 展示了一个物理寻址的高速缓存如何和虚拟内存结合起来。主要思路就是地址翻译发生在高速缓存查找之前。注意，页表条目可以缓存，就像其他的数据字一样。

 9.6.2 利用 TLB 加速地址翻译

        正如看到的，每次 CPU 产生一个虚拟地址，MMU 就必须查阅一个 PTE，以便将虚拟地址翻译成物理地址。在最糟糕的情况下，这会要求从内存多取一次数据，代价是几十到几百个周期。如果PTE碰巧缓存在 L1 中，那么开销就下降到 1 个或 2个周期。然而，许多系统都试图消除即使是这样的开销，它们在 MMU 中包括了一个关于 PTE 的小的缓存，成为 翻译后备缓冲器（TLB）

        TLB 是一个小的，虚拟寻址的缓存，其中每一行都保存着一个由单个 PTE 组成的块。TLB 通常有高度的相联度。如图 9-15 所示，用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号（VPN）中提取出来的。如果 TLB 有 T=2^t 个组，那么 TLB索引（TLBI）是由 VPN 的 t 个最低位组成的，而 TLB 标记（TLBT）是由 VPN 剩余的位组成的。

         图 9-16a 展示了当 TLB 命中时（通常情况）所包括的步骤。这里的关键：所有的地址翻译步骤都是在芯片上的MMU中执行的，因此非常快。

        ① 第一步：CPU产生一个虚拟地址

        ② 第二步和第三步：MMU 从 TLB 中取出相应的 PTE

        ③ 第四步：MMU 将这个虚拟地址翻译成一个物理地址，并将它发送到 高速缓存/主存。

        ④ 第五步：高速缓存/主存将所请求的数据字返回给 CPU。

当 TLB 不命中时， MMU 必须从 L1 缓存中取出相应的 PTE，如图 9-16b。所取出的 PTE 存放在 TLB 中,可能会覆盖一个已经存在的条目。

9.6.3 多级页表

        目前为止，我们一直假设系统只用一个单独的页表来进行地址翻译。但是我们有一个 32 位的地址空间，4 KB 的页面和一个 4 字节的PTE，那么即使应用所引用的只是虚拟地址空间中的很小一部分，也总是需要一个 4MB 的 页表驻留在内存中。对于地址空间为 64 位的系统来说，问题将变得更加复杂。

        用来压缩页表的常用方法是使用层次结构的页表。假设 32位虚拟地址空间 被分为 4KB 的页，而每个页表条目都是 4 字节。还假设在这一时刻，虚拟地址空间有如下形式：内存的前 2K 个页面分配给了代码和数据，接下来的 6K 个页面还未分配，再接下来的 1023 个页面也未被分配，接下来的 1 个页面分配给了用户栈。 图 9-17 展示了如何为这个虚拟地址空间构造一个两级的页表层次结构。

        一级页表中的每个 PTE 负责映射虚拟地址空间中一个 4MB 的片（chunk），这里每一片都是由 1024 个连续的页面组成的。比如， PTE 0 映射第一片，PTE 1 映射接下来的一片，以此类推。假设地址空间是 4GB，1024个PTE已经足够覆盖整个空间了。 

         如果片 i 中的每个页面都未被分配，那么一级 PTE i 就为空。例如，图9-17中，片 2~7 是未被分配的。然而，如果在片 i 中至少有一页是分配了的，那么一级 PTE i 就指向一个二级页表的基址。例如，图9-17中，片0 1 和 8的所有或者部分已经被分配，所以它们的一级PTE就指向二级页表。

         二级页表中的每个 PTE 都负责映射一个 4KB 的虚拟内存页面，就像查看只有一级页表那样。注意，使用 4 字节的 PTE ，每个一级和二级页表都是 4 KB 字节，这刚好和一个页面的大小是一样的。

         这种方法从两个方面减少了内存要求。① 如果一级页表中的一个 PTE 是空的，那么相应的二级页表就不会存在。这代表着一个巨大的潜在节约，因为对于一个典型的程序，4GB 的虚拟地址空间的大部分是未分配的。② 只有一级页表才需要总是在主存中，虚拟内存系统可以在需要时创建，页面调入或调出二级页表，减少了主存的压力，只有最经常使用的二级页表才需要缓存在主存中。

        图 9-18 描述了使用 k 级页表层次结构的地址翻译。虚拟地址被划分为 k 个 VPN 和 1个 VPO 每个 VPN i 都是一个到第 i 级页表的索引，其中 。第 j 级页表中的每个 PTE，，都指向第 j+1 级的某个页表的基址。 第 k 级页表中的每个 PTE 包含某个物理页面的PPN，或者一个磁盘块的地址。 为了构造物理地址，在能够确定 PPN 之前，MMU 必须访问 k 个 PTE。对于只有一级的页表结构，PPO 和 VPO 是相同的。