一个系统中的进程是与其它进程共享 CPU 和内存资源的。然而，共享内存会形成一些特殊的挑战。如果有太多的进程占用内存，内存很快就会被占满，当一个新来的进程没有内存空间可用时，那它就无法运行。内存中的数据还很容易被破坏，例如，当某个进程不小心写了另一个进程使用的内存，原来的数据就被覆盖，这可能会导致非业务逻辑上的程序错误，这些错误往往都难以定位原因。为了更加有效地管理内存并且减少出错，现代操作系统提出了一个抽象的概念，叫做虚拟内存(Virtual Memory)。
什么是虚拟内存
虚拟内存是硬件异常、地址翻译硬件、内存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的、私有的地址空间。虚拟内存机制提供了三个重要的能力：
- 它将内存看成是磁盘的高速缓存，在内存中只保留磁盘的活动区域，并根据需要在磁盘和内存之间来回传送数据，通过这种方式，它高效地使用了内存。
- 它为每个进程提供了一致的虚拟地址空间，从而简化了内存管理。
- 它保护了每个进程的内存不被其他进程破坏。
虚拟内存的原理
物理寻址和虚拟寻址
计算机系统的内存可以视为一个 M 字节大小的数组。每字节都有一个唯一的物理地址(Physical Address, PA)。第一个字节的地址为 0，接下来为 1，再下一个为 2，以此类推。
图 1-1 物理寻址
图 1-1 展示了一个物理寻址的示例，假设 CPU 正在执行的是一条加载指令，它将读取从物理地址 4 开始的 4 字节数据。当 CPU 执行这条加载指令时，会生成一个有效物理地址 4，4 通过内存总线传递到内存。然后内存取出从物理地址 4 开始的 4 字节数据，并将数据返回给 CPU，CPU 会将数据存放在一个寄存器里。像这样 CPU 直接访问物理地址的形式就被称为物理寻址(physical addressing)。
早期的 PC 都使用物理寻址。而且，诸如数字信号处理器、嵌入式微控制器以及 Cray 超级计算机这样的系统仍然继续在这种寻址方式。 然而，现代处理器使用的是一种称为虚拟寻址(virtual addressing)的寻址形式。 如图 1-2 所示
图 1-2 虚拟寻址
使用虚拟寻址，CPU 生成一个虚拟地址(Virtual Address, VA)来访问内存，这个虚拟地址在被送到内存之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的过程叫做地址翻译(address translation)。地址翻译需要硬件和操作系统之间的紧密合作。CPU 芯片上的硬件叫做内存管理单元(Memory Management Unit, MMU)，它利用存放在内存中的页表来动态翻译虚拟地址，该表的内容由操作系统来管理。
地址空间
地址空间(address space)是一个非负整数地址的有序集合：
$$ \{0,;1,;2,; …\} $$
在一个带虚拟内存的系统中，CPU 从一个有 N=2ⁿ 个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间(virtual address space)。
$$ \{0,;1,;2,; …,;N-1\} $$
一个地址空间的大小是由表示最大地址所需要的位数来描述的。例如，一个包含 N=2ⁿ 个地址的虚拟地址空间就叫做一个 n 位地址空间。现代系统通常支持 32 位或者 64 位虚拟地址空间。一个系统还有一个物理地址空间(physical address space)，对应于系统中物理内存的 M 个字节：
$$ \{0,;1,;2,; …,;M-1\} $$
地址空间的概念是重要的，因为它解除了数据和物理地址的绑定。一旦认识到这一点，我们就可以允许每个数据有多个地址，其中每个地址都选自一个不同的地址空间。 内存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。
虚拟内存作为缓存的工具
从概念上来说，虚拟内存同样可以视为一个存放在磁盘上的 N 字节大小的数组，每字节都有一个唯一的虚拟地址。磁盘上数组的内容被缓存在内存中。和 存储器层次结构 中其他缓存一样，磁盘（较低层）上的数据被分割成块，这些块作为磁盘和内存（较高层）之间的传输单元。VM 系统通过将虚拟内存分割为虚拟页(Virtual Page, VP)来处理这个问题，每个虚拟页的大小为 P=2ᴾ 字节。类似地，物理内存被分割为物理页(Physical Page, PP)，大小也为 P 字节。
在任意时刻，虚拟页面的集合都分为三个不相交的子集：
- 未分配的：VM 系统还未分配或者创建页。未分配的页没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
- 已缓存的：当前已缓存在物理内存中的已分配页。
- 未缓存的：当前未缓存在物理内存中的已分配页。
图 1-3 内存作为缓存
图 1-3 展示了一个有 8 个虚拟页的虚拟内存。虚拟页 0 和 3 还没有被分配，因此在磁盘上还不存在。虚拟页 1、4 和 6 被缓存在物理内存中。虚拟页 2、5 和 7 虽然已经被分配了，但是当前并未缓存在内存中。
DRAM 缓存的组织结构
为了清晰理解存储层次结构中不同的缓存概念，我们将使用术语 SRAM 缓存来表示位于 CPU 和内存之间的 L1、L2 和 L3 高速缓存，用术语 DRAM 缓存来表示虚拟内存系统的缓存，它在内存中缓存虚拟页。
在存储器层次结构中，DRAM 缓存所处的层次对它的组织结构有很大的影响。回想一下，DRAM 比 SRAM 要慢大约 10 倍，而磁盘要比 DRAM 慢大约 100 000 倍。因此，DRAM 缓存不命中比起 SRAM 缓存不命中所花费的代价要昂贵得多，这是因为 DRAM 缓存不命中要由磁盘来服务，而 SRAM 缓存不命中通常是由内存来服务的。 而且，从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约 100 000 倍。归根到底，DRAM 缓存的组织结构完全是由巨大的不命中开销驱动的。
由于极高的不命中代价和访问第一个字节的开销，虚拟页往往很大，通常是 4KB-2MB。 DRAM 缓存是全相联的，即任何虚拟页都可以放置在任何物理页中。不命中时的替换策略也很重要，因为替换错了虚拟页的代价也非常高。因此，与硬件对 SRAM 缓存相比，操作系统对 DRAM 缓存使用了更复杂更精密的替换算法。最后，因为对磁盘的访问时间很长，DRAM 缓存总是使用写回，而不是直写。
1 | # Linux、Mac 系统可以通过以下命令来查看虚拟页大小 |
页表
同任何缓存一样，虚拟内存系统需要判断一个虚拟页是否缓存在 DRAM 中。如果命中，系统还必须确定这个虚拟页存放在哪个物理页中。如果不命中，系统需要知道这个虚拟页存放在磁盘的哪个位置，然后在 DRAM 中选择一个牺牲页，再将虚拟页从磁盘复制到 DRAM，替换掉这个牺牲页。
这些功能是由软硬件联合提供的，包括操作系统、地址翻译硬件和一个存放在物理内存中叫做页表(page table)的数据结构，页表将虚拟页映射到物理页。 每当地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与 DRAM 之间来回传送页。
图 1-4 页表的基本组织结构
图 1-4 展示了一个页表的基本组织结构。页表就是一个页表条目(Page Table Entry, PTE)的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE。 为了方便描述，我们将假设每个 PTE 是由一个有效位(valid bit)和一个 n 位地址字段组成的。有效位表明了该虚拟页是否被缓存在 DRAM 中。如果设置了有效位，那么地址字段就表示 DRAM 中物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，如果是一个空地址，则表示这个虚拟页还未被分配；否则，这个地址就指向该虚拟页在磁盘上的起始位置。
示例中展示了一个有 8 个虚拟页和 4 个物理页的系统的页表。四个虚拟页(VP 1、VP 2、VP 4、VP 7)被缓存在 DRAM 中。两个虚拟页(VP 0、VP 5)还未被分配，而剩下的虚拟页(VP 3、VP 6)已经被分配了，但是还未被缓存。
页命中
考虑一下当 CPU 想要读包含在 VP 2 中的一个字时会发生什么，VP 2 被缓存在 DRAM 中。地址翻译硬件根据虚拟地址定位到 PTE 2，并从内存中读取它。因为设置了有效位，那么地址翻译硬件知道 VP 2 已经缓存在内存中了。所以它使用 PTE 2 中的地址字段(该地址字段指向 PP 1 的起始位置)构造出这个字的物理地址。
图 1-5 页命中
缺页
在虚拟内存的习惯说法中，DRAM 缓存不命中称为缺页(page fault)。图 1-6 展示了缺页之前页表的状态。CPU 引用了 VP 3 中的一个字，VP 3 未缓存在 DRAM 中。地址翻译硬件从内存中读取 PTE 3，从有效位推断出 VP 3 未缓存，这时触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页(假定是存放在 PP 3 中的 VP 4)，如果 VP 4 已经被修改了，那么内核就会将它复制回磁盘。同时，内核也会修改 PTE 4 的信息，用来反映 VP 4 不再缓存在内存中这一事实。
图 1-6 VM 缺页之前页表的状态
接下来，内核从磁盘复制 VP 3 到内存中的 PP 3，更新 PTE 3，随后返回。最后，当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发到地址翻译硬件。现在 VP 3 已经缓存在内存中，那么地址翻译硬件也能正常处理了。图 1-7 展示了在缺页之后页表的状态。
图 1-7 VM 缺页之后页表的状态
虚拟内存是在 20 世纪 60 年代早期发明的，远在 CPU-内存之间差距的加大而产生 SRAM 缓存之前。因此，虚拟内存系统使用了和 SRAM 缓存不同的术语，即使它们的许多概念是相似的。在虚拟内存的习惯说法中，块被称为页。在磁盘和内存之间传送页的活动叫做交换(swapping)或者页面调度(paging)。页从磁盘换入 DRAM 或从 DRAM 换出磁盘时会一直等待到最后时刻(也就是当有不命中发生时)才换入页面的这种策略称为按需页面调度(demand paging)。也可以采用其他的方法，例如，尝试着预测不命中，在页面实际被引用之前就换入页面。然而，所有现代系统使用的都是按需页面调度的方式。
分配虚拟页面
图 1-8 展示了当操作系统分配一个新的虚拟内存页时对页表的影响(例如 C 调用 malloc 函数的结果)。VP 5 的分配过程是在磁盘上创建页面并更新 PTE 5，使它指向磁盘上这个新创建的页面的起始位置。
图 1-8 分配虚拟页面
程序的局部性
当我们了解虚拟内存的概念之后，如果和直接使用物理内存相比较，我们会担心它的效率。因为页不命中的处罚很大，我们担心页面调度会破坏程序性能。实际上，虚拟内存工作得相当好，这主要归功于我们的老朋友——局部性(locality)。
尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存的总数，但是局部性保证了在任意时刻，程序将趋向于在一个较小的活动页面(active page)集合上工作，这个集合叫做工作集(working set)或者常驻集合(resident set)。 在初始开销之后(也就是将工作集页面调度到内存中)，接下来对这个工作集的引用将导致命中，不会产生额外的磁盘流量。
只要我们的程序有好的局部性，虚拟内存系统就能工作得相当好。但是，不是所有的程序都能展现良好的局部性。如果工作集的大小超出了物理内存的大小，那么程序将处于一种不幸的状态，叫做抖动(thrashing)，这时页面将不断地换进换出。 虽然虚拟内存通常是高效的，但是如果一个程序跑起来慢的像爬一样，那么聪明的程序猿会考虑是不是发生了抖动。
小结
在前文中，我们看到虚拟内存提供了一种机制，用 DRAM 缓存来自(通常更大的)虚拟地址空间的页面。有趣的是，一些早期的系统，比如 DEC PDP-11/70，支持的是一个比物理内存更小的虚拟地址空间。然而，虚拟内存仍然是一个有用的机制，因为它大大地简化了内存管理，并提供了一种自然的保护内存的方法。
1 | # Linux 系统可以通过以下命令来查看物理地址空间和虚拟地址空间大小 |
虚拟内存作为内存管理的工具
到目前为止，我们都假设有一个单独的页表，将一个虚拟地址空间映射到物理地址空间。实际上操作系统为每个进程提供了一个独立的页表，也就是一个独立的虚拟地址空间。 图 1-9 展示了基本思想。进程 i 的页表将 VP 1 映射到 PP 2，VP 2 映射到 PP 7。相似地，进程 j 的页表将 VP 1 映射到 PP 7，VP 2 映射到 PP 10。注意，多个虚拟页面可以映射到同一个物理页面上。
图 1-9 进程的独立页表
按需页面调度和独立虚拟地址空间的结合，对系统中内存的使用和管理造成了深远的影响。 特别地，VM 简化了链接和加载、代码和数据共享，以及应用程序的内存分配。
图 1-10 进程地址空间
- 简化链接。独立的虚拟地址空间允许每个进程的内存映像使用相同的格式，而不管代码和数据实际存放在物理内存的何处。
- 就像图 1-10 中看到的，一个给定的 Linux 系统上的每个进程都使用类似的内存格式。对于 64 位虚拟地址空间，代码段总是从虚拟地址 0x400000 开始。数据段跟在代码段之后，中间有一段符合要求的对齐空白。栈占据用户进程地址空间最高的部分，并向下生长。这样的一致性极大地简化了链接器的设计和实现，允许链接器生成链接完全的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。
- 简化加载。虚拟内存使得向内存中加载可执行文件和共享对象文件更加容易。
- 要把目标文件中 .text 和 .data 段加载到一个新创建的进程中，Linux 加载器为代码和数据段分配虚拟页，把它们标记为未被缓存的，将页表条目指向目标文件中适当的位置。有趣的是，加载器从不从磁盘到内存实际复制任何数据。每个虚拟页初次被引用时，要么是 CPU 取指令时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页，而不需要加载器来操心。
- 简化共享。独立虚拟地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的机制。
- 一般而言，每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程共享的。在这种情况下，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。然而，在另一些情况下，还是需要进程来共享代码和数据。例如，每个进程必须调用相同的操作系统内核代码，而每个 C 程序都会调用 C 标准库中的函数，比如 printf。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和 C 标准库的副本，如图 1-10 所示。
- 简化内存分配。虚拟内存向用户进程提供了一个简单的分配额外内存的机制。
- 当一个运行在用户进程中的程序要求额外的堆空间时(如调用 malloc 函数)，操作系统分配一个适当数字(例如 k)个连续的虚拟内存页面，并且将它们映射到物理内存中任意位置的 k 个物理页面。由于页表工作的方式，操作系统没有必要分配 k 个连续的物理内存页面。页面可以随机地分散在物理内存中。
虚拟内存作为内存保护的工具
任何现代计算机系统必须为操作系统提供手段来控制对内存的访问
- 不允许一个用户进程修改它的只读代码段
- 不允许它读或修改任何内核中的代码和数据结构
- 不允许它读或者写其他进程的私有内存
- 不允许它修改任何与其他进程共享的虚拟页面，除非所有的共享者都显式地允许它这么做(通过进程间通信来实现)。
基于 VM 地址翻译机制，我们能用一种十分简单的方式来提供访问控制。因为 CPU 每次生成一个虚拟地址时，地址翻译硬件都会读一个 PTE，所以通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面的访问。图 1-11 展示了大致的思想。
图 1-11 带许可位的页表
示例中，每个 PTE 已经添加了三个许可位。SUP 位表示进程是否必须运行在内核(超级用户)模式下才能访问该页。运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些 SUP 为 0 的页面。READ 位和 WRITE 位控制对页面的读和写访问。例如，如果进程 i 运行在用户模式下，那么它有读 VP 0 和读写 VP 1 的权限。然而，不允许它访问 VP 2。
如果一条指令违反了这些许可条件，那么 CPU 就触发一个一般保护故障，将控制传递给内核中的一个异常处理程序。Linux shell 一般将这种异常报告为段错误(segmentation fault)。
虚拟内存的实现
内存映射
Linux 通过将一个虚拟内存区域与一个磁盘上的对象(object)关联起来，以此来初始化这个虚拟内存区域的内容，这个过程称为内存映射(memory mapping)。虚拟内存区域可以映射成两种类型的对象：
- Linux 文件系统中的普通文件。
- 一个虚拟内存区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区(section)被分成页大小的片，每一片都包含一个虚拟页面的初始内容。因为按需进行页面调度，所以这些虚拟页面没有实际进入物理内存，直到 CPU 第一次引用到页面。如果虚拟内存区域比文件区要大，那么就用零来填充这个区域的余下部分。
- 匿名文件。
- 一个虚拟内存区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。
无论在哪种情况中，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件(swap file)之间换来换去。交换文件也叫做交换空间(swap space)或者交换区域(swap area)。需要注意的一点是，在任何时刻，交换空间 都限制着当前运行着的进程能够分配的虚拟页面的总数。
动态内存分配
虽然可以使用低级的 mmap 和 munmap 函数来创建和删除虚拟内存的区域，但是 C 程序员还是会觉得当运行时需要额外虚拟内存时，用动态内存分配器(dynamic memory allocator)更方便，也有更好的可移植性。
动态内存分配器维护着一个进程的虚拟内存区域，称为堆(heap)(见图 1-12)，它紧接在未初始化的数据区域后开始，并向上生长(向更高的地址)。对于每个进程，内核维护着一个变量 brk(读做 break)，它指向堆的顶部。
图 1-12 堆
分配器将堆视为一组不同大小的块(block)的集合来维护。每个块就是一个连续的虚拟内存片(chunk)，要么是已分配的，要么是空闲的。已分配的块显式地保留为供应用程序使用，空闲块可用来分配。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。两种风格都要求应用显式地分配块。它们的不同之处在于由哪个实体来负责释放已分配的块。
- 显示分配器(explicit allocator)，要求应用显式地释放任何已分配的块。
- 例如，C 标准库提供一种叫做 malloc 程序包的显式分配器。C 程序通过调用 malloc 函数来分配一个块，并通过调用 free 函数来释放一个块。C++ 中的 new 和 delete 操作符与 C 中的 malloc 和 free 相当。
- 隐式分配器(implicit allocator)，要求分配器检测一个已分配块何时不再被程序所使用并进行释放。
- 隐式分配器也叫做垃圾收集器(garbage collector)，自动释放未使用的已分配的块的过程叫做垃圾收集(garbage collection)。诸如 Lisp、Java 之类的高级语言就依赖垃圾收集来释放已分配的块。
总结
虚拟内存是对内存的一个抽象。支持虚拟内存的 CPU 通过使用一种叫做虚拟寻址的间接形式来引用内存。CPU 产生一个虚拟地址，在被发送到内存之前，这个地址被翻译成一个物理地址。从虚拟地址空间到物理地址空间的地址翻译要求硬件和软件紧密合作。地址翻译硬件通过使用页表来翻译虚拟地址，而页表的内容是由操作系统负责维护的。