CSAPP笔记-虚拟内存

引言

虚拟内存（VM）是现代操作系统提供的一种对主存的抽象概念，它为每个进程提供了一个大的、一致的和私有的地址空间，旨在更加有效地管理内存并减少出错。

虚拟内存提供了三个重要的能力： - 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。（细细品味，可以说是面试必问八股） - 它为每个进程提供了一致的地址空间，从而简化内存管理。 - 它保护了每个进程的地址空间不被其它进程破坏。

本章将从两个角度来看待虚拟内存。前一部分来描述虚拟内存如何工作，后一部分描述应用程序如何使用和管理虚拟内存。

物理和虚拟寻址

计算机系统的主存被组织成一个由M个连续字节大小的单元组成的数组，因此每个字节都有一个唯一的物理地址（Physical Address）。CPU访问内存最自然的方式就是直接使用这个物理地址，下图展示一条加载指令直接读取地址4开始的4字节字：

然而现代处理器则使用一种虚拟寻址（virtual addressing）的方式：

其实就是多了一个MMU地址翻译的中转步骤。MMU叫内存管理单元（Memory Management Unit），它是一个硬件组件，能够利用在主存中的查询表来动态翻译虚拟地址，而查询表的内容由操作系统管理。（是不是就是页表？）

地址空间

可以看作就是一个线性地址空间（因为不存在断裂吧）：0, 1, ⋯, N − 1。

如果是虚拟地址空间（大小为 N ）,那么应该满足 N = 2ⁿ，其中现代系统通常支持 n = 32 或 64 位虚拟地址空间。

系统肯定还有一个物理地址空间（大小为 M），事实上不要求是2的幂（但你买的到这种内存条吗）。因此CSAPP为了简化讨论，令 M = 2^m。主存中每个字节都有一个选自虚拟地址空间和选自物理地址空间的地址。

虚拟内存作为缓存的工具

可以把主存看做是磁盘的高速缓存。磁盘上的数据被分割成块（和Cache的缓存行类似？），这些块则作为磁盘（较低层）和主存（较高层）之间的传输单元。VM系统则通过将虚拟内存分割为称为虚拟页（Virtual Page, VP）的大小固定的块来处理这个问题。每个虚拟页的大小为 P = 2^p字节。类似地，物理内存被分割成物理页（Physical Page, PP），每个物理页的大小也为 P 字节。物理页也被称为页帧（page frame）。

在任意时刻，虚拟页面可被分为三个不相交的子集： - 未分配的：VM系统还未分配的页。没有任何数据与它关联，因此不占用任何磁盘空间。 - 缓存的：当前已缓存在物理内存中的已分配页。 - 未缓存的：未缓存在物理内存中的已分配页。它们被保存在磁盘上，直到需要时才被加载到物理内存中。

从上图我们可以看出，只有已缓存的页才有VP和PP之间的地址映射关系。

DRAM缓存的组织结构

使用SRAM缓存来描述位于CPU和主存之间的L1、L2和L3缓存，使用DRAM缓存来描述虚拟内存系统的缓存，它在主存中缓存虚拟页。

然而考虑到，DRAM虽然只比SRAM慢大约10倍，但是磁盘要比DRAM慢大约100 000多倍。因此DRAM的不命中相比SRAM要昂贵的多，这导致我们的虚拟页往往很大，通常是 4KB~2MB，且DRAM缓存是全相联的（即任何虚拟页都可以放置在任何的物理页中）。

CSAPP还提到DRAM不命中的替换策略也很重要，但没细说（因为采用了更复杂精密的替换算法）。最后由于磁盘访问时间很长，DRAM缓存总是写回而非直写。

页表

VM系统一定要有种方法来判定虚拟页和物理页之间的地址映射关系。如果一个VP是已缓存的，系统必须确定该页存放在哪个物理页。如果是未缓存的，系统还必须判断这个虚拟页存放在磁盘的哪个位置，然后在物理页中选择一个牺牲页，并将虚拟页从磁盘复制到DRAM中，替换掉这个牺牲页。

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

下图展示了页表的基本组织结构：

页表就是一个页表条目（Page Table Entry，PTE）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。图中假设一个PTE是由一个有效位（valid bit）和一个 n 位地址字段组成的。

有效位表明该虚拟页当前是否被缓存在DRAM中。如果设置了有效位，那么地址字段则表示DRAM中相应的物理页的起始位置，这个物理页缓存了该虚拟页。如果没设置有效位，那么一个空地址表示这个虚拟页还未被分配。否则这个地址就指向虚拟页在磁盘中的起始地址。

页命中

下图给了一个页命中的例子：

VP2将作为一个索引定位PTE2，并从内存中读取它。因为设置了有效位，故VP2被缓存在DRAM中。使用PTE内的物理内存地址来构造VP2内被访问字的物理地址。

缺页

在虚拟内存的习惯说法中，DRAM缓存不命中被称为缺页（page fault）。下图展示缺页前的页表状态示例：

CPU引用了VP3的一个字，VP3并未缓存在DRAM中。地址翻译硬件从内存读取PTE3，发现有效位为0，因此触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在图里中就是PP3，内部包含VP4。如果VP4被修改了，那么内核会将它复制回磁盘。

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

CSAPP漏说了，就是对于PTE4，系统还会将其有效位清零，同时将PTE4的地址字段更新为VP4在磁盘上的位置，以便将来需要时可以重新加载它。

所有现代系统都使用按需页面调度的方式，即直到一个虚拟页被访问时才将它加载到DRAM中。虽然也可以预先加载一些页，但这通常是没有必要的，因为大多数程序具有局部性（locality），即它们倾向于访问最近访问过的页以及与这些页相邻的页。

分配页面

下图展示当操作系统分配一个新的VP时对页表的影响：

VP5的分配过程是在磁盘空间创建空间，并更新PTE5，使它指向磁盘上这个新创建的页面。VP5的有效位被清零，因为它还未被加载到DRAM中。

局部性

虚拟内存的不命中处罚非常大（前面提到了），但是事实上虚拟内存工作地相当好，这归功于局部性。

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

不幸的是，如果工作集超出物理内存的大小，则会进入一种抖动（thrashing）的状态，这时页面将不断地换进换出。因此程序员需要保证程序有好的时间局部性。

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

实际上，操作系统为每个进程提供了一个独立的页表（自然也就是一个独立的虚拟空间），举例：

这里我们可以看到多个虚拟页面可以映射到同一个共享物理页面上。

目前可以总结一下，按需页面调度+虚拟内存有以下好处： - 简化链接。独立的地址空间允许每个进程的内存映像使用相同的基本格式，无需管比如代码或数据实际存放在物理内存的何处。之前的CSAPP的章节有给个例子：

对于64位的地址空间，代码段总是从0x400000开始，数据段在代码段后，中间有一段符合要求的对齐空白。栈占据用户进程地址空间最高的部分,并向下生长。这样的一致性极大地简化了链接器的设计和实现,允许链接器生成完全链接的可执行文件,这些可执行文件是独立于物理内存中代码和数据的最终位置的。

简化加载。要把目标文件中.text 和.data 节加载到一个新创建的进程中,Linux 加载器为代码和数据段分配虚拟页,把它们标记为无效的(即未被缓存的),将页表条目指向目标文件中适当的位置。后续按需自动调入页面。
简化共享。在一些情况中,还是需要进程来共享代码和数据。例如,每个进程必须调用相同的操作系统内核代码,而每个C程序都会调用C标准库中的程序,比如 printf。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面,从而安排多个进程共享这部分代码的一个副本,而不是在每个进程中都包括单独的内核和C标准库的副本。
简化内存分配。当一个运行在用户进程中的程序要求额外的堆空间时(如调用 malloc 的结果),操作系统分配一个适当数字(例如k)个连续的虚拟内存页面,并且将它们映射到物理内存中任意位置的k个任意的物理页面。

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

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

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

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

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

地址翻译

CSAPP首先给了一个表，就是一些常用的符号：

地址翻译就是一个 N 元素的虚拟地址空间中的元素和一个 M 元素的物理地址空间的元素之间的映射：

MAP : VAS → PAS ∪ ⌀.

下图展示了MMU如何利用页表来实现这种映射。

CPU中的一个控制寄存器，页表基址寄存器（Page Table Base Register，PTBR），包含了当前页表的起始地址。n 位的虚拟地址包含两个部分：一个 p 位的虚拟页面偏移（Virtual Page Offset，VPO）和一个 n − p 位的虚拟页号（Virtual Page Number，VPN）。地址翻译硬件使用VPN作为索引来访问页表中的PTE。将页表条目中的物理页号（Physical Page Number，PPN）与虚拟页面偏移VPO组合起来就得到了物理地址。

下图展示了当页面命中和缺页时，CPU硬件执行步骤：

页面命中具体步骤： 1. 处理器生成一个虚拟地址,并把它传送给 MMU 2. MMU生成 PTE 地址,并从高速缓存/主存请求得到它。 3. 高速缓存/主存向MMU 返回 PTE。 4. MMU 构造物理地址,并把它传送给高速缓存/主存。 5. 高速缓存/主存返回所请求的数据字给处理器。

页面命中的过程完全由硬件处理，但是不同的是，处理缺页需要硬件和操作系统内核协作完成。具体步骤如下： 1. 处理器生成一个虚拟地址,并把它传送给 MMU 2. MMU生成 PTE 地址,并从高速缓存/主存请求得到它。 3. 高速缓存/主存向 MMU 返回 PTE。（前三步和页面命中的情况一样） 4. PTE 中的有效位是零,所以 MMU 触发了一次异常,传递 CPU 中的控制到操作系统内核中的缺页异常处理程序。 5. 缺页处理程序确定出物理内存中的牺牲页,如果这个页面已经被修改了,则把它换出到磁盘。 6. 缺页处理程序页面调入新的页面,并更新内存中的PTE。 7. 缺页处理程序返回到原来的进程,再次执行导致缺页的指令。CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理内存中,所以就会命中。

结合高速缓存和虚拟内存

大多数系统选择直接使用物理地址来访问SRAM高速缓存（就是Cache），下图给出一个示例，可以看到就多了一个L1高速缓存的中转：

注意页表条目和其它数据字一样可以缓存。

在 x86 这类硬件页表遍历架构里，CR3 里放的是顶级页表的物理地址。访问页表本身必须要经过物理锚点，这同时也为SRAM缓存页表提供了保证，因为SRAM缓存是通过物理地址访问的。

利用TLB加速地址翻译

许多系统在MMU中就包括了一个关于PTE的小的缓存，称为翻译后备缓冲器（Translation Lookaside Buffer，TLB）。

TLB则是一个小的、虚拟地址的缓存，其中每一行都保存着一个由单个PTE组成的块。TLB通常有高度的相联度。

上图可以看到，VP中的VPN被拆成两个部分用于访问TLB，分别是标记和索引字段，对应于组选择和行匹配。如果TLB有 T = 2^t 个组，那么TLB索引（TLBI）是由VPN的低 t 位组成的，而TLB标记（TLBT）则是由VPN的高 n − p − t 位组成的。

下图展示了TLB命中和不命中时的步骤：

非常直观。

多级页表

目前为止我们一直假设系统针对一个进程只使用一个单独的页表来进行地址翻译。但如果假设我们有一个32位地址空间、4KB的页面和一个4字节的PTE，那么按前面的来看，我们需要一个4MB的页表驻留在内存。对于64位的地址空间，那就有点无法想象了。

可以考虑使用有层次结构的页表。还是上面那个例子，假设在这一时刻，虚拟地址空间有如下形式：内存的前2K个页面分配给的代码和数据，接下来的6K个页面还未分配，再接下来的1023个页面也未分配，接下来的一个页面分配给了用户栈。下图展示我们如何为这个虚拟地址空间构造一个两级的页表层次结构。

一级页表中的每个PTE负责映射虚拟地址空间中一个4MB的片（chunk），这里每一片都是由1024个连续页面组成的。假设地址空间是4GB，那么1024个PTE就足以覆盖整个空间。

如果片i中的每个页面都未被分配，那么一级PTE i就为空。然而如果片i中至少有一个页面被分配，那么一级PTE i就指向一个二级页表的基址。

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

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

下图描述了使用k级页表层次结构的地址翻译：

访问k个PTE看样子很昂贵，但事实上TLB能够起作用。实际上多级页表的地址翻译并不比单级页表慢很多。

端到端的地址翻译

CSAPP在这节给出一个综合示例，该示例运行在有一个TLB和L1 d-cache的小系统上，该小系统有以下假设： - 内存按字节寻址 - 内存访问是针对1字节的字的（不是4字节的字） - 虚拟地址长14位 - 物理地址长12位 - 页面大小为64字节 - TLB是四路组相联的，总共有16个条目 - L1 d-cache是物理寻址、直接映射的，行大小为4字节，总共16组。

可以推出下图：

考虑TLB、页表和缓存，则有以下快照：

我们前面已经强调了TLB是虚拟寻址的（通过VPN的位）。由于TLB有4个组，所以VPN的前2位就作为组索引（TLBI）。剩下的6位则作为标记（TLBT），用来区分可能映射到同一个TLB组的不同的VPN。
页表。这里的页表只有一级，有 2⁸ = 256 个页表条目（PTE）。图里只展示了前16个PTE。对于有效位为0的PTE，内部存的值没有意义。（你确定？不是前面说的指向磁盘上的地址吗？）
高速缓存。直接映射的缓存通过物理地址的字段来寻址。因为每个Cache line是4字节的，所以物理地址的低2位被用作块内偏移（CO）。因为Cache有16组，所以物理地址的接下来4位被用作组索引（Cache Index，CI）。剩下的6位则作为标记（Cache Tag，CT），用来区分可能映射到同一个Cache组的不同的物理地址。

接下来假设我们的CPU要执行一条读地址0x03d4处字节的加载指令。我们将该虚拟地址按如下图解析：

开始时，MMU从虚拟地址中抽出VPN(0x0f)，并且检查TLB，看它是否因为前面的某个内存引用缓存了PTE 0x0f的一个副本。TLB从VPN中取出TLB索引0x03和TLB标记0x03。在TLB第3个组的第二个条目得到匹配，获得缓存的PPN0x0d，返回给MMU。

MMU将PPN和VPO连接起来得到物理地址0x354。

接下来，MMU将物理地址发送给缓存。下图给出物理地址的解析：

缓存从物理地址抽出缓存偏移CO0x0，组索引CI0x05和标记CT0x0d。因为组 0x5中的标记与CT 相匹配,所以缓存检测到一个命中,读出在偏移量 CO 处的数据字(0x36),并将它返回给 MMU,随后 MMU 将它传递回CPU。

如果TLB不命中，那么MMU必须从页表中的PTE获取PPN。如果PTE无效，那么就产生一个缺页，内核则需要调入合适的页面，更新页表，并且重新执行导致缺页的指令。另外可能PTE有效，但是PPN不在缓存中，这时就会产生一个缓存不命中，CPU则需要从主存中加载数据字到缓存中，然后再返回给CPU。

案例研究:Intel Core i7/Linux 内存系统

CSAPP给了个运行在Linux的Intel Core i7处理器上的内存系统的案例研究，下图是Core i7内存系统的重要部分：

处理器封装包括四个核、一个大的所有核共享的L3高速缓存，以及一个DDR3存储器控制器。每个核包括一个层次结构的TLB、一个层次结构的数据核指令高速缓存，以及一组快速的点到点链路，这种路基于 Quick Path 技术,是为了让一个核与其他核和外部 I/O 桥直接通信。TLB是虚拟寻址的四路组相联，L1、L2和L3高速缓存都是物理寻址的，块大小为64字节。L1和L2是8路组相联的，而L3是16路组相联的。页大小可以在启动时被配置为4KB或4MB，Linux内核使用4KB的页。

Core i7地址翻译

下图总结了完整的Core i7地址翻译过程：

Core i7采用四级页表层次结构，每个进程有它自己私有的页表层次结构。CR3控制寄存器指向第一级页表(L1)的起始位置。CR3的值是每个进程上下文的一部分，每次上下文切换时，CR3的值都会被恢复。

下图给出了第一级、第二级和第三级页表中条目的格式。当P=1时，地址字段包含一个40位的物理页号（PPN），它指向适当的页表开始处。注意这强加了一个要求，就是物理页表4KB对齐。

下图给出了第四级页表条目格式，地址字段包括一个40位的物理页号（PPN），它指向一个4KB的物理页，包含了被映射的虚拟页的内容。

PTE有三个权限页，控制对页的访问。R/W确定页的内容是可以读写的还是只读的。U/S确定页是用户可访问的还是只能由内核访问的。XD（禁止执行）位是在64位模式下引入的，可以用来禁止从某些内存页取指令。

每次访问一个页时，MMU都会设置A位引用位。内核可以用这个位实现页替换算法。每次对一个页进行写后，MMU会设置D位脏位。该位告诉内核在复制替换页时是否需要将它写回磁盘。

下图给出Core i7 MMU如何使用四级页表来将虚拟地址翻译为物理地址：

Linux虚拟内存系统

Linux为每个进程维护了一个单独的虚拟地址空间，形式如下图所示：