完整VM系统

在结束对虚拟内存的研究之前，让我们仔细看看整个虚拟内存系统是如何组合起来的。我们已经看到了此类系统的关键要素，包括大量页表设计、与 TLB 的交互（有时甚至由操作系统本身处理），以及决定将哪些页保留在内存中、将哪些页踢出内存的策略。然而，还有许多其他特性构成了一个完整的虚拟内存系统，其中包括许多性能、功能和安全特性。这就是我们的关键所在：如何构建完整的虚拟内存系统？实现完整的虚拟内存系统需要哪些功能？它们如何提高性能、增强安全性或改进系统？

为此，我们将介绍两个系统。第一个系统是 “现代 “虚拟内存管理器的最早范例之一，即 20 世纪 70 年代和 80 年代初开发的 VAX/VMS 操作系统 。有些想法，即使是 50 年前的想法，仍然值得了解，这种想法对于大多数其他领域（如物理学）的人来说是众所周知的，但在技术驱动型学科（如计算机科学）中却不得不说。

其次是 Linux，原因显而易见。Linux 是一种广泛使用的系统，可以在小到功率不足的手机系统，大到现代数据中心中最具扩展性的多核系统上有效运行。因此，其虚拟机系统必须足够灵活，以便在所有这些场景中成功运行。我们将对每个系统进行讨论，以说明如何将前面章节中提出的概念整合到一个完整的内存管理器中。

1 VAX/VMS 虚拟内存

VAX-11 微型计算机体系结构由Digital Equipment Corporation (DEC) 于 20 世纪 70 年代末推出。在微型计算机时代，DEC 是计算机行业的巨头；不幸的是，一系列错误的决策和 PC 的出现慢慢地（但肯定地）导致了它们的消亡，。该架构有多种实现形式，包括 VAX-11/780 和功能较弱的 VAX-11/750。

该系统的操作系统被称为 VAX/VMS（或简称 VMS），其主要设计者之一是 Dave Cutler，他后来领导开发了微软的 Windows NT [C93]。VMS 存在一个普遍的问题，即它可以在各种机器上运行，包括非常便宜的 VAXen（是的，这是正确的复数）到同一架构系列中的极其高端和强大的机器。因此，操作系统必须拥有能够在如此广泛的系统中发挥作用（并且运作良好）的机制和策略。

另外一个问题是，VMS 是利用软件创新来掩盖体系结构固有缺陷的一个极好例子。尽管操作系统经常依赖硬件来构建有效的抽象和幻象，但有时硬件设计者并不能完全做到万无一失；在 VAX 硬件中，我们将看到一些这样的例子，以及 VMS 操作系统是如何克服这些硬件缺陷来构建一个有效的、可运行的系统的。

1.1 内存管理硬件

VAX-11 为每个进程提供 32 位虚拟地址空间，分为 512 字节页。因此，虚拟地址由 23 位 VPN 和 9 位偏移量组成。此外，VPN 的上两位用于区分页面所在的分段；因此，如前所述，该系统是分页和分段的混合体。

地址空间的下半部分被称为 “进程空间”，每个进程都是唯一的。在进程空间的前半部分（称为 P0），可以找到用户程序以及向下增长的堆。在进程空间的后半部（P1），我们可以找到向上生长的栈。地址空间的上半部分称为系统空间（S），但只有一半被使用。受保护的操作系统代码和数据存放在这里，操作系统以这种方式在各进程间共享。

VMS 设计人员的一个主要顾虑是，VAX 硬件中的页面大小（512 字节）小得令人难以置信。由于历史原因而选择的这种大小存在一个基本问题，即简单的线性页表过于庞大。因此，VMS 设计人员的首要目标之一就是确保 VMS 不会因为页表而使内存不堪重负。系统通过两种方式减轻了页表对内存的压力。首先，VAX-11 将用户地址空间划分为两个区域，VAX-11为每个进程的每个区域（P0 和 P1）提供一个页表；因此，栈和堆之间未使用的地址空间部分不需要页表空间。基址寄存器和边界寄存器的使用正如你所期望的那样；基址寄存器保存该段的页表地址，边界寄存器保存其大小（即页表条目数）。

其次，操作系统将用户页表（P0 和 P1，每个进程两个）置于内核虚拟内存中，从而进一步降低了内存压力。因此，在分配或增长页表时，内核会从自己的虚拟内存 S 段中分配空间。如果内存压力过大，内核可以将这些页表的页交换到磁盘，从而将物理内存用于其他用途。

将页表放在内核虚拟内存中意味着地址转换变得更加复杂。例如，要转换 P0 或 P1 中的虚拟地址，硬件必须首先尝试在其页表（该进程的 P0 或 P1 页表）中查找该页的页表条目；但在此过程中，硬件可能必须首先查阅系统页表（位于物理内存中）；完成转换后，硬件才能了解页表中的页面地址，然后最终了解所需内存访问的地址。幸运的是，VAX 硬件管理的 TLB 使所有这一切都变得更快，通常（希望）可以避免这种费力的查找。

2 真实的地址空间

研究 VMS 的一个好处是，我们可以看到真实地址空间是如何构建的，如下图所示。

到目前为止，我们假设的地址空间很简单，只有用户代码、用户数据和用户堆，但正如上文所述，真实的地址空间要复杂得多。例如，代码段永远不会从第 0 页开始，而是标记为不可访问，以便为检测空指针访问提供一些支持。因此，在设计地址空间时，需要考虑的一个问题就是对调试的支持，而不可访问的 0 页在某种程度上提供了这种支持。

为什么空指针访问会导致 SEG 错误？

你现在应该对解引用空指针时发生的情况有了很好的了解。一个进程生成了一个虚拟地址 0，具体方法如下：

1 2	int *p = NULL; // set p = 0 *p = 10; // try to store 10 to virtual addr 0

硬件尝试在 TLB 中查找 VPN（此处也是 0），结果导致 TLB 未命中。查阅页表后发现，VPN 0 的条目被标记为无效。这样，我们就有了一个无效访问，它将控制权转移到操作系统，而操作系统可能会终止进程（在 UNIX 系统中，进程会收到一个信号，允许它们对此类故障做出反应；但如果未被捕获，进程就会被杀死）。

也许更重要的是，内核虚拟地址空间（即其数据结构和代码）是每个用户地址空间的一部分。在上下文切换时，操作系统会更改 P0 和 P1 寄存器，使其指向即将运行的进程的相应页表；但不会更改 S 基寄存器和边界寄存器，因此 “相同的 “内核结构会映射到每个用户地址空间。

内核被映射到每个地址空间的原因有很多。举例来说，当操作系统从用户程序（例如在 write() 系统调用中）得到一个指针时，很容易将指针中的数据复制到自己的结构中。操作系统是自然编写和编译的，无需担心访问的数据来自何处。相反，如果内核完全位于物理内存中，就很难做到将页表中的页面交换到磁盘这样的事情；如果内核有自己的地址空间，在用户应用程序和内核之间移动数据又会变得复杂而痛苦。有了这种结构（现在被广泛使用），内核几乎就成了应用程序的一个库，尽管是受保护的库。

关于这个地址空间的最后一点与保护有关。显然，操作系统不希望用户应用程序读写操作系统的数据或代码。因此，硬件必须为页面提供不同的保护级别。VAX 就是这样做的，它在页表的保护位中规定了 CPU 访问特定页面必须达到的权限级别。因此，系统数据和代码的保护级别要高于用户数据和代码；如果试图从用户代码访问此类信息，就会向操作系统发出中断，违规进程很可能会被终止。

2.1 页面替换

VAX 中的页表项 (PTE) 包含以下位：一个有效位、一个保护字段（4 位）、一个修改（或脏）位、一个保留给操作系统使用的字段（5 位），最后是一个物理页号（PFN），用于存储页在物理内存中的位置。精明的读者可能会注意到：没有引用位！因此，VMS 替换算法必须在没有硬件支持的情况下确定哪些页面处于活动状态。

模拟参考位

事实证明，你并不需要硬件引用位来获得系统中正在使用的页面的概念。事实上，早在 20 世纪 80 年代初，Babaoglu 和 Joy 就证明 VAX 的保护位可以用来模拟参考位。基本原理：如果想了解系统中哪些页面正在被活跃使用，可将页表中的所有页面标记为不可访问（但保留进程真正可访问的页面信息，可能在页表条目的 “保留操作系统字段 “部分）。当进程访问页面时，它将向操作系统发出一个中断；然后操作系统将检查该页面是否真的应该被访问，如果是，则将该页面恢复到正常的保护状态（如只读或读写）。在替换时，操作系统可以检查哪些页面仍然标记为不可访问，从而了解哪些页面最近没有被使用过。这种引用位 “仿真 “的关键在于减少开销，同时还能很好地了解页面的使用情况。操作系统在标记页面不可访问时不能过于激进，否则开销会过高。操作系统在标记页面时也不能太被动，否则所有页面最终都会被引用；操作系统也无法很好地知道应该驱逐哪个页面。

开发人员还担心内存占用者，即占用大量内存并导致其他程序难以运行的程序。迄今为止，我们已经研究过的大多数策略都很容易出现这种占用内存的情况；例如，LRU 是一种全局策略，不能在进程之间公平地共享内存。

为了解决这两个问题，开发人员提出了分段 FIFO 替换策略。这种策略的思路很简单：每个进程在内存中可保留的最大页数，即常驻集大小（RSS）。每个页面都保存在一个先进先出列表中；当一个进程超过其 RSS 时，“先进 “的页面就会被驱逐。FIFO 显然不需要任何硬件支持，因此很容易实现。

当然，正如我们前面所看到的，纯粹的 FIFO 性能并不是特别好。为了提高 FIFO 的性能，VMS 引入了两个二次机会列表，即全局的干净页面列表和 脏页面 列表，用于放置从内存中驱逐前的页面。当进程 P 超过其 RSS 时，会从其每个进程的 FIFO 中移除一个页面；如果是干净页面（未修改），则将其放在干净页面列表的末尾；如果是脏页面（已修改），则将其放在脏页面列表的末尾。

如果另一个进程 Q 需要一个空闲页面，它会从全局干净页面列表中获取第一个空闲页面。但是，如果原进程 P 在该页被回收前发生错误，P 会从空闲（或脏页）列表中回收该页，从而避免了代价高昂的磁盘访问。这些全局二次机会列表越大，分段 FIFO 算法的性能就越接近 LRU。

VMS 中使用的另一种优化方法也有助于克服 VMS 中的小页面问题。具体来说，由于页面太小，磁盘在交换过程中的 I/O 效率会非常低，因为磁盘在进行大容量传输时效率更高。为了提高交换 I/O 的效率，VMS 增加了许多优化功能，其中最重要的是集群功能。通过集群，VMS 将全局脏页面列表中的大批量页面集中在一起，然后一次性将它们写入磁盘（从而使它们变得干净）。集群技术在大多数现代系统中都得到了应用，因为可以自由地将页面放置在交换空间的任何位置，这使得操作系统可以对页面进行分组，执行更少、更大的写入操作，从而提高性能。

2.2 其他妙招

VMS 还有两个现在已成为标准的技巧：需求清零和写时复制。现在我们就来介绍一下这些懒惰优化。VMS（以及大多数现代系统）中的一种懒惰形式是页面的需求清零。为了更好地理解这一点，让我们以在地址空间（比如在堆中）中添加一个页面为例。在最简单的实现中，操作系统会在物理内存中找到一个页面，将其清零（这是为了安全起见，否则你就能看到其他进程使用该页面时页面上的内容了！），然后将其映射到地址空间（即设置页表，以便根据需要引用该物理页面），以此来响应向堆中添加页面的请求。但这种天真的实现方式代价高昂，尤其是当该页面未被进程使用时。

通过需求清零，当页面被添加到地址空间时，操作系统只需做很少的工作；它会在页表中添加一个条目，标记该页面不可访问。如果进程读取或写入该页面，操作系统就会收到一个中断。在处理中断时，操作系统会注意到（通常是通过在页表项的 “为操作系统保留 “部分标记的某些位）这实际上是一个需要清零的页面；此时，操作系统会进行必要的工作，找到一个物理页，将其清零，并映射到进程的地址空间中。如果进程从不访问该页，所有这些工作都可以避免，这就是需求清零的优点。

VMS 中另一个很酷的优化（同样，几乎所有现代操作系统中都有这种优化）是写时复制（简称 COW）。这个概念至少可以追溯到 TENEX 操作系统，它的原理很简单：当操作系统需要将一个页面从一个地址空间复制到另一个地址空间时，它可以不复制该页面，而是将其映射到目标地址空间，并在两个地址空间中都标记为只读。如果两个地址空间都只读取该页面，则不会采取进一步的操作，这样操作系统就实现了快速复制，而实际上没有移动任何数据。

但是，如果其中一个地址空间确实尝试向该页面写入数据，则会向操作系统发出中断。操作系统会注意到该页是 COW 页，从而（懒散地）分配一个新页，将数据填入其中，并将这个新页映射到故障进程的地址空间。然后该进程继续运行，现在它拥有自己的页面私有副本。

由于多种原因，COW 非常有用。当然，任何类型的共享库都可以通过写时复制映射到许多进程的地址空间，从而节省宝贵的内存空间。在 UNIX 系统中，由于 fork() 和 exec() 的语义，COW 甚至更为重要。你可能还记得，fork() 会创建一个调用者地址空间的精确副本；如果地址空间很大，创建这样的副本既慢又耗费数据。更糟糕的是，大部分地址空间会立即被后续的 exec() 调用所覆盖，这将使调用进程的地址空间与即将执行的程序的地址空间重叠。通过执行写入时复制 fork()，操作系统避免了大部分不必要的复制，从而在提高性能的同时保留了正确的语义。

3 Lnux 虚拟内存系统

现在我们将讨论 Linux VM 系统的一些更有趣的方面。 Linux 的发展是由真正的工程师解决生产中遇到的实际问题推动的，因此大量的功能已经慢慢地融入到现在功能齐全、功能齐全的虚拟内存系统中。

虽然我们无法讨论 Linux VM 的各个方面，但我们将讨论最重要的方面，特别是它超出了 VAX/VMS 等经典 VM 系统中的范围。我们还将尝试强调 Linux 和旧系统之间的共性。

在本次讨论中，我们将重点关注适用于 Intel x86 的 Linux。虽然 Linux 可以而且确实在许多不同的处理器架构上运行，但 x86 上的 Linux 是其最主要和最重要的部署，因此也是我们关注的焦点。

3.1 Linux 地址空间

与其他现代操作系统和 VAX/VMS 一样，Linux 虚拟地址空间由用户部分（用户程序代码、栈、堆和其他部分所在）和内核部分（内核代码、栈、堆和其他部分所在）组成。与其他系统一样，在上下文切换时，当前运行的地址空间的用户部分会发生变化；而内核部分则在不同进程中保持不变。与其他系统一样，在用户模式下运行的程序也无法访问内核虚拟页；只有进入内核并转换到特权模式，才能访问这些内存。

在经典的 32 位 Linux（即具有 32 位虚拟地址空间的 Linux）中，用户和内核地址空间的分割发生在地址 0xC0000000，即地址空间的四分之三处。因此，虚拟地址 0 到 0xBFFFFFFF 是用户虚拟地址；其余的虚拟地址（0xC0000000 到 0xFFFFFFFF）属于内核虚拟地址空间。64 位 Linux 也有类似的分割，但分割点略有不同。

下图 显示了典型（简化）地址空间的描述。

Linux 的一个有趣之处在于它包含两种内核虚拟地址。第一种称为内核逻辑地址 。内核代码只需调用 kmalloc 即可获得更多此类内存。大多数内核数据结构都在这里，如页表、每个进程的内核栈等。与系统中的大多数其他内存不同，内核逻辑内存不能交换到磁盘。

内核逻辑地址最有趣的地方在于它们与物理内存的联系。具体来说，内核逻辑地址与物理内存的第一部分之间存在直接映射关系。因此，内核逻辑地址 0xC0000000 相当于物理地址 0x00000000，0xC0000FFF 相当于 0x00000FFF，以此类推。这种直接映射有两个意义。首先，在内核逻辑地址和物理地址之间来回转换非常简单；因此，这些地址通常被当作物理地址来处理。其次，如果一块内存在内核逻辑地址空间中是连续的，那么它在物理内存中也是连续的。这使得在内核地址空间的这一部分分配的内存适用于需要连续物理内存才能正常工作的操作，例如通过目录内存访问 (DMA) 进行设备间的 I/O 传输。

另一种内核地址是内核虚拟地址。要获取这种类型的内存，内核代码会调用不同的分配器 vmalloc，该分配器会返回一个指向所需大小的虚拟连续区域的指针。与内核逻辑内存不同，内核虚拟内存通常不是连续的；每个内核虚拟页都可能映射到非连续的物理页（因此不适合 DMA）。不过，这样的内存更容易分配，因此可用于大型缓冲区，而要在这些缓冲区中找到连续的大块物理内存则非常困难。

在 32 位 Linux 中，内核虚拟地址存在的另一个原因是，它们能让内核寻址超过（大约）1 GB 的内存。多年前，机器的内存比现在少得多，因此访问超过 1 GB 的内存不是问题。然而，随着技术的进步，很快就需要让内核使用更大的内存。内核虚拟地址和它们与物理内存一对一的严格映射关系使这成为可能。不过，随着向 64 位 Linux 迁移，这种需求就不那么迫切了，因为内核不再局限于最后 1 GB 的虚拟地址空间。

3.2 页表结构

由于我们关注的是 x86 的 Linux，因此我们的讨论将围绕 x86 提供的页表结构类型展开，因为它决定了 Linux 能做什么、不能做什么。如上所述，x86 提供了一种硬件管理的多级页表结构，每个进程有一个页表；操作系统只需在内存中设置映射，将特权寄存器指向页目录的起始位置，剩下的就交给硬件处理了。操作系统会在进程创建、删除和上下文切换时参与其中，确保硬件 MMU 在每种情况下都使用正确的页表进行转换。

近年来最大的变化可能就是从 32 位 x86 迁移到 64 位 x86（如上文所述）。正如在 VAX/VMS 系统中看到的那样，32 位地址空间已经存在了很长时间，随着技术的变化，它们终于开始成为程序的真正限制。虚拟内存使系统编程变得容易，但由于现代系统包含许多 GB 内存，32 位已不足以引用每个内存。因此，下一次飞跃成为必要。

迁移到 64 位地址会以预期的方式影响 x86 中的页表结构。因为 x86 使用的是多级页表，而当前的 64 位系统使用的是四级页表。不过，虚拟地址空间的全部 64 位尚未使用，而仅使用了最下面的 48 位。因此，虚拟地址可以这样理解：

如图所示，虚拟地址的前 16 位未使用（因此在转换中不起作用），后 12 位（由于 4 KB 页面大小）用作偏移量（因此直接使用，没有转换），留下虚拟地址的中间36位参与转换。地址的 P1 部分用于索引最顶层的页目录，并且从那里开始进行转换，一次一层，直到页表的实际页被 P4 索引，产生所需的页表条目。

随着系统内存变得更大，这个庞大的地址空间的更多部分将被启用，从而导致五级和最终六级页表树结构。想象一下：一个简单的页表查找需要六级转换，只是为了找出某个数据在内存中的位置。

3.3 大页面支持

Intel x86 允许使用多种页面大小，而不仅仅是标准的 4 KB 页面。具体来说，最近的设计在硬件中支持 2 MB 甚至 1 GB 页面。因此，随着时间的推移，Linux 已经发展到允许应用程序利用这些大页面。正如前面所暗示的，使用大页面会带来很多好处。正如 VAX/VMS 中所见，这样做可以减少页表中所需的映射数量；页面越大，映射越少。然而，较少的页表条目并不是大页面背后的驱动力；相反，它是更好的 TLB 行为和相关的性能提升。

当进程主动使用大量内存时，它会很快用转换填满 TLB。如果这些转换针对 4 KB 页面，则只能访问少量的总内存，而不会导致 TLB 未命中。其结果是，对于在具有许多GB内存的机器上运行的现代“大内存”工作负载来说，会带来显著的性能成本；最近的研究表明，一些应用程序将其周期的10%用于服务TLB未命中。

大页面允许进程通过使用 TLB 中较少的槽来访问大片内存而不会发生 TLB 未命中，因此这是主要优点。然而，大页面还有其他好处：TLB 未命中路径较短，这意味着当发生 TLB 未命中时，可以更快地对其进行处理。此外，分配可以非常快（在某些情况下），这是一个很小但有时很重要的好处。

Linux 对大页面的支持的一个有趣的方面是它是如何逐步实现的。起初，Linux 开发人员知道这种支持仅对少数应用程序很重要，例如具有严格性能要求的大型数据库。因此，决定允许应用程序显式请求大页面内存分配（通过 mmap() 或 shmget() 调用）。这样，大多数应用程序将不受影响（并且继续仅使用 4 KB 页面；一些要求较高的应用程序将不得不更改为使用这些接口，但对它们来说这是值得的。

最近，由于许多应用程序对更好的 TLB 行为的需求更加普遍，Linux 开发人员添加了透明大页面支持。启用此功能后，操作系统会自动寻找机会分配大页面（通常为 2 MB，但在某些系统上为 1 GB），而无需修改应用程序。

大页面并非没有代价。最大的潜在成本是内部碎片，即页面很大但很少使用。这种形式的浪费可能会用大量但很少使用的页面填充内存。交换（如果启用）也不能很好地处理大页面，有时会大大增加系统的 I/O 量。分配的开销也可能很糟糕（在某些其他情况下）。总的来说，有一件事是明确的：多年来为系统提供良好服务的 4 KB 页面大小不再像以前那样是通用解决方案；不断增长的内存大小要求我们将大页面和其他解决方案视为虚拟内存系统必要发展的一部分。 Linux 对这种基于硬件的技术的缓慢采用证明了即将发生的变化。

3.4 页面缓存

为了降低访问持久存储的成本，大多数系统使用积极的缓存子系统将常用的数据项保留在内存中。在这方面，Linux 与传统操作系统没有什么不同。

Linux 页面缓存是统一的，将来自三个主要来源的页面保留在内存中：内存映射文件、来自设备的文件数据和元数据（通常通过直接对文件系统进行 read() 和 write() 调用来访问）以及堆和栈组成每个进程的页面（有时称为匿名内存，因为它下面没有命名文件，而是交换空间）。这些实体保存在页面缓存哈希表中，以便在需要所述数据时可以快速查找。

内存映射的普遍性

内存映射早于 Linux 出现了好几年，并在 Linux 和其他现代系统中的许多地方使用。这个想法很简单：通过在已经打开的文件描述符上调用 mmap()，进程将返回一个指向文件内容似乎所在的虚拟内存区域开头的指针。然后，通过使用该指针，进程可以通过简单的指针解引用来访问文件的任何部分。

对内存映射文件中尚未进入内存的部分的访问会触发页面错误，此时操作系统将分页相关数据，并通过相应地更新进程的页表来使其可访问（即，请求分页） ）。

每个常规 Linux 进程都使用内存映射文件，即使 main() 中的代码也不会直接调用 mmap()，因为 Linux 将代码从可执行文件和共享库代码加载到内存中。下面是 pmap 命令行工具的（高度缩写）输出，它显示了哪些不同的映射构成了正在运行的程序（shell，在本例中为 tcsh）的虚拟地址空间。输出显示四列：映射的虚拟地址、其大小、区域的保护位以及映射源：

映射的虚拟地址	大小	区域的保护位	映射源
0000000000400000	372K	r-x–	tcsh
00000000019d5000	1780K	rw—	[anon]
00007f4e7cf06000	1792K	r-x–	libc-2.23.so
00007f4e7d2d0000	36K	r-x–	libcrypt-2.23.so
00007f4e7d508000	148K	r-x–	libtinfo.so.5.9
00007f4e7d731000	152K	r-x–	ld-2.23.so
00007f4e7d932000	16K	rw—	[stack]

正如你可以看到的输出中，来自 tcsh 二进制文件的代码以及来自 libc、libcrypt、libtinfo 的代码以及来自动态链接器本身 (ld.so) 的代码都映射到地址空间。还存在两个匿名区域：堆（第二个条目，标记为 anon）和栈（标记为 stack）。内存映射文件为操作系统构建现代地址空间提供了一种简单有效的方法

页面缓存会跟踪条目是否干净（读取但未更新）或脏（又称修改）。脏数据由后台线程（称为 pdflush）定期写入后备存储（即，写入文件数据的特定文件，或交换匿名区域的空间），从而确保修改后的数据最终被写回持久存储。此后台活动要么在特定时间段后发生，要么在太多页面被视为脏页时发生（均为可配置参数）。

在某些情况下，系统运行时内存不足，Linux 必须决定从内存中剔除哪些页面以释放空间。为此，Linux 使用 2Q 替换的改进形式，我们在此进行描述。

基本思想很简单：标准 LRU 替换是有效的，但可能会被某些常见的访问模式颠覆。例如，如果一个进程重复访问一个大文件（尤其是接近内存大小或更大的文件），LRU 会将所有其他文件踢出内存。更糟糕的是：将该文件的部分内容保留在内存中没有用，因为它们在被踢出内存之前永远不会被重新引用。

Linux 版本的 2Q 替换算法通过保留两个列表并在它们之间划分内存来解决这个问题。第一次访问时，一个页面被放入一个队列（原论文中称为A1，但Linux中为非活动列表）；当它被重新引用时，该页面会被提升到另一个队列（原来称为Aq，但在Linux中称为活动列表）。当需要进行替换时，从非活动列表中取出替换候选者。 Linux 还定期将页面从活动列表底部移动到非活动列表，使活动列表保持在总页面缓存大小的三分之二左右。

理想情况下，Linux 会以完美的 LRU 顺序管理这些列表，但是，正如前面章节中所讨论的，这样做的成本很高。因此，与许多操作系统一样，使用 LRU 的近似值（类似于时钟替换）。

这种 2Q 方法的行为通常与 LRU 非常相似，但在处理循环访问大文件的情况时，其显著特点是将循环访问的页面限制在非活动列表中。由于这些页面在被踢出内存之前从未被重新引用过，因此它们不会冲掉活动列表中的其他有用页面。

3.5 安全和缓冲区溢出

现代 VM 系统（Linux、Solaris 或 BSD 变体之一）与古代 VM 系统（VAX/VMS）之间的最大区别可能是现代对安全性的重视。保护一直是操作系统的一个严重问题，但随着机器的互联程度比以往任何时候都更加紧密，开发人员实施了各种防御对策来阻止那些狡猾的黑客获得系统控制权也就不足为奇了。

缓冲区溢出攻击是一种主要威胁，它可以针对普通用户程序甚至内核本身。这些攻击的目的是找到目标系统中的错误，使攻击者可以将任意数据注入目标的地址空间。有时会出现此类漏洞，因为开发人员（错误地）假设输入不会太长，因此（可信地）将输入复制到缓冲区中；因为输入实际上太长，所以它会溢出缓冲区，从而覆盖目标的内存。像下面这样无辜的代码可能是问题的根源：

1
2
3
4

int some_function(char *input) {
	char dest_buffer[100];
	strcpy(dest_buffer, input); // oops, unbounded copy!
}

在许多情况下，这种溢出并不会造成灾难性后果，例如，无意地向用户程序甚至操作系统提供不良输入可能会导致系统崩溃，但不会更糟。然而，恶意程序员可以精心设计使缓冲区溢出的输入，以便将自己的代码注入目标系统，从而接管系统并为所欲为。如果攻击网络连接的用户程序成功，攻击者就可以在被攻击的系统上运行任意计算，甚至出租计算资源；如果攻击操作系统本身成功，攻击者就可以访问更多资源，这就是所谓的权限升级（即用户代码获得内核访问权限）。

防止缓冲区溢出的第一道也是最简单的一道防线就是防止在地址空间的特定区域（如栈内）执行任何代码。AMD 在其 x86 版本中引入的 NX 位（No-eXecute 的缩写）（英特尔版本中也有类似的 XD 位）就是这样一种防御措施；它只需阻止在相应页表条目中设置了该位的任何页面的执行。这种方法可以防止攻击者注入目标栈的代码被执行，从而减轻了问题。

然而，聪明的攻击者是……聪明的，即使攻击者不能显示添加注入的代码，恶意代码也能执行任意代码序列。这种想法以其最普遍的形式被称为返回导向编程（return-oriented programming, ROP）[S07]，它确实非常出色。ROP 背后的原理是，任何程序的地址空间中都有大量的代码位（用 ROP 术语来说就是小工具），尤其是与庞大的 C 库链接的 C 程序。因此，攻击者可以覆盖栈，使当前执行函数中的返回地址指向所需的恶意指令（或一系列指令），然后再返回指令。通过串联大量小工具（即确保每次返回都跳转到下一个小工具），攻击者可以执行任意代码。

为了抵御 ROP（包括其早期形式，返回到库攻击（return-to-libc 攻击）），Linux（和其他系统）增加了另一种防御手段，即地址空间布局随机化（ASLR）。操作系统不是将代码、栈和堆放在虚拟地址空间内的固定位置，而是将它们的位置随机化，从而使实现这类攻击所需的复杂代码序列变得相当具有挑战性。因此，针对易受攻击的用户程序的大多数攻击都会导致程序崩溃，但无法控制运行中的程序。

有趣的是，在实践中可以很容易地观察到这种随机性。下面是一段在现代 Linux 系统上演示的代码：

1
2
3
4
5

int main(int argc, char *argv[]) {
	int stack = 0;
	printf("%p\n", &stack);
	return 0;
}

这段代码只是打印出堆栈中变量的（虚拟）地址。在较早的非 ASLR 系统中，该值每次都是相同的。但如下所示，每次运行时，该值都会发生变化：

1
2
3
4
5
6

> ./random
0x7ffd3e55d2b4
> ./random
0x7ffe1033b8f4
> ./random
0x7ffe45522e94

ASLR 对于用户级程序来说是一种非常有用的防御手段，因此它也被纳入了内核，并被称为内核地址空间布局随机化（KASLR）。然而，事实证明，内核可能有更大的问题需要处理，正如我们接下来要讨论的那样。

3.6 其他安全问题：熔断漏洞和幽灵漏洞

系统安全世界已经被两个新的相关攻击颠覆了。第一个叫做 “熔毁”（Meltdown），第二个叫做 “幽灵”（Spectre）。它们是由四组不同的研究人员/工程师在差不多同一时间发现的，并引发了对计算机硬件和上述操作系统所提供的基本保护措施的深刻质疑。有关每种攻击的详细描述，请参见 meltdownattack.com 和 spectreattack.com。幽灵被认为是这两种攻击中问题较多的一种。

这些攻击所利用的一般弱点是，现代系统中的 CPU 会在幕后执行各种疯狂的技巧来提高性能。其中一类技术是问题的核心，被称为 “预测执行”，即 CPU 猜测哪些指令将在未来执行，并提前开始执行。如果猜测正确，程序运行速度就会加快；如果猜测不正确，CPU就会撤消这些指令对架构状态（如寄存器）的影响，并再次尝试执行，这一次会沿着正确的路径运行。

预测的问题在于，它往往会在系统的各个部分（如处理器缓存、分支预测器等）留下执行痕迹。因此，问题就出现了：正如攻击事件的作者所展示的，这种状态会使内存内容变得脆弱，甚至是我们认为受到 MMU 保护的内存。

因此，加强内核保护的一个途径就是尽可能地将内核地址空间从每个用户进程中移除，转而为大多数内核数据建立一个独立的内核页表（称为内核页表隔离，或 KPTI）[G+17]。这样，内核的代码和数据结构就不再映射到每个进程中，而是只保留最基本的部分；当切换到内核时，就需要切换到内核页表。这样做提高了安全性，避免了一些攻击向量，但也付出了代价：性能。切换页表的代价很高。安全的代价：方便和性能。

不幸的是，KPTI 并不能解决上述所有安全问题，只能解决部分问题。而简单的解决方案，如关闭预测功能，也没有多大意义，因为系统运行速度会降低数千倍。