FreeBSD 虚拟内存系统设计要素
最后更新于
最后更新于
原文：
Matthew Dillon []
这个标题其实只是一个花哨的说法，意味着我将尝试描述整个虚拟内存（VM）体系结构，希望能让每个人都能跟得上。过去一年，我专注于 FreeBSD 中的几个主要内核子系统，其中虚拟内存（VM）和交换（Swap）子系统是最有趣的，NFS 则是“必要的琐事”。我只重写了其中的一小部分代码。在 VM 领域，我唯一的重大重写是交换子系统。我的大部分工作是清理和维护，进行了一些中等程度的代码重写，但在 VM 子系统中并没有进行重大算法调整。VM 子系统的理论基础大部分保持不变，近几年现代化工作的大部分功劳归功于 John Dyson 和 David Greenman。我不是像 Kirk 那样的历史学家，所以不会试图给各种功能打上人物的名字标签，因为我肯定会搞错。
在进入实际设计之前，我们先花点时间讨论一下维护和现代化任何长久存在的代码库的必要性。在编程界，算法往往比代码更为重要，正是由于 BSD 的学术背景，从一开始就对算法设计给予了大量关注。对设计的关注通常会导致一个干净且灵活的代码库，这样的代码库可以随着时间的推移较为容易地修改、扩展或替换。虽然一些人认为 BSD 是一个“老”操作系统，但我们那些在其上工作的人，更倾向于将其视为一个“成熟”的代码库，里面的各种组件被现代化的代码修改、扩展或替换。它已经进化了，而 FreeBSD 无论代码有多老，都处在前沿。这是一个非常重要的区别，而不幸的是，这一点常常被许多人忽略。程序员可能犯的最大错误就是不从历史中学习，而这正是许多其他现代操作系统犯下的错误。Windows NT® 就是一个最好的例子，其后果是灾难性的。Linux 在某种程度上也犯了这个错误——足够多的情况让我们 BSD 人时不时地开一些小玩笑。Linux 的问题其实就是缺乏经验和历史来对比思想，这是一个问题，但 Linux 社区正迅速地解决这个问题，和 BSD 社区解决问题的方式一样——通过持续的代码开发。Windows NT® 的人则不断犯同样的错误，而这些错误在 UNIX® 中早已被解决，他们却要花费数年时间来修复。一遍又一遍。他们有着严重的“非我设计”病和“我们总是对，因为我们的营销部门这么说”这种心态。我对那些无法从历史中学习的人几乎没有容忍度。
FreeBSD 设计中，特别是在 VM/Swap 子系统中的复杂性，很多时候直接源于在各种条件下解决性能问题的需要。这些问题并非由于算法设计不佳，而是由环境因素引起的。在平台之间的直接对比中，当系统资源开始被施压时，这些问题就变得尤为明显。在我描述 FreeBSD 的 VM/Swap 子系统时，读者应该始终牢记两个要点：
性能设计中最重要的方面是“优化关键路径”。性能优化往往会让代码稍微膨胀，以便让关键路径的性能更好。
一个坚实的、通用的设计在长期来看优于一个高度优化的设计。虽然通用设计在最初实现时可能比高度优化的设计慢，但通用设计通常更容易适应变化的条件，而高度优化的设计最终可能需要被丢弃。
任何能够存活并且可以维护多年的代码库，必须从一开始就设计得当，即使这意味着牺牲一些性能。二十年前，人们仍然争论用汇编语言编程比用高级语言编程好，因为前者生成的代码速度是后者的十倍。今天，这个论点的错误已经显而易见——而且这种错误与算法设计和代码通用化之间的相似之处也不言而喻。
描述 FreeBSD VM 系统的最佳方式是从用户级进程的角度来看。每个用户进程看到的是一个单一的、私有的、连续的虚拟内存（VM）地址空间，其中包含几种类型的内存对象。这些对象有各种特征。程序代码和程序数据实际上是一个单一的内存映射文件（运行的二进制文件），但程序代码是只读的，而程序数据是写时复制（copy-on-write）的。程序的 BSS 部分只是按需分配并填充为零的内存，称为按需零页填充（demand zero page fill）。任意文件也可以被内存映射到地址空间，这也是共享库机制的工作方式。这样的映射可能需要修改，以保持对进程私有。fork 系统调用在现有复杂度的基础上，进一步增加了 VM 管理的复杂性。
一个程序二进制数据页（它是一个基本的写时复制页）说明了这种复杂性。一个程序二进制文件包含一个预初始化的数据段，这个段最初是直接从程序文件中映射的。当程序被加载到进程的 VM 空间时，这个区域最初是内存映射的，并且由程序二进制文件本身提供支持，允许 VM 系统在之后释放/重用该页，并从二进制文件中重新加载它。然而，待进程修改了这段数据，VM 系统就必须为该进程制作该页的私有副本。由于私有副本已被修改，VM 系统就不能再释放它，因为无法再从原来的二进制文件中恢复它。
你会立即注意到，原本一个简单的文件映射已经变得复杂得多。数据可能是按页修改的，而文件映射是一次性涵盖多页的。当进程执行 fork 时，复杂性进一步增加。当进程 fork 时，结果是两个进程——每个进程都有自己的私有地址空间，包括原始进程在调用 fork() 前所做的任何修改。VM 系统在 fork() 时完全复制数据是不明智的，因为很可能至少有一个进程从此以后只会读取该页，而允许原始页继续使用。原本是私有的页被重新标记为写时复制（copy-on-write），因为每个进程（父进程和子进程）都期望它们自己对 fork 后的修改保持私有，不影响另一个进程。
FreeBSD 用分层的 VM 对象模型来管理这一切。原始的二进制程序文件最终会成为最低层的 VM 对象。在它上面会有一个写时复制层，用来保存那些必须从原始文件复制出来的页。如果程序修改了属于原始文件的数据页，VM 系统会发生一个故障，并在更高层次上复制该页。当进程 fork 时，会推送额外的 VM 对象层。这可能通过一个相对简单的例子来理解。fork() 是所有 *BSD 系统中常见的操作，因此这个例子考虑了一个启动并执行 fork 的程序。当进程启动时，VM 系统创建了一个对象层，我们称之为 A：
A 代表文件——这些页可能根据需要从文件的物理介质中被分页进来和分页出去。对于程序来说，从磁盘分页进是合理的，但我们不希望将其分页出去并覆盖可执行文件。因此，VM 系统创建了第二层 B，这一层将由交换空间（swap space）提供物理支持：
在首次写入该页之后，B 中创建了一个新页，并且其内容从 A 初始化。B 中的所有页都可以被分页进出交换设备。当程序执行 fork() 时，VM 系统会创建两个新的对象层——C1（父进程）和 C2（子进程）——这些层位于 B 之上：
在这个例子中，假设 B 中的一个页被原始父进程修改。进程会发生一个写时复制故障，并在 C1 中复制该页，保持 B 中的原始页不变。现在，假设同一个页在 B 中被子进程修改。进程会发生一个写时复制故障，并在 C2 中复制该页。B 中的原始页现在被完全隐藏，因为 C1 和 C2 都有一份副本，而 B 理论上可以被销毁，如果它不代表一个“真实”的文件；然而，这种优化并不简单，因为它是细粒度的。FreeBSD 并没有进行这种优化。现在，假设（如通常情况那样）子进程执行了 exec()。它的当前地址空间通常会被一个新地址空间替代，该地址空间代表一个新的文件。在这种情况下，C2 层被销毁：
在这种情况下，B 的子进程数量降至 1，所有对 B 的访问现在都通过 C1。这样，B 和 C1 就可以合并在一起。B 中的所有与 C1 共同存在的页在合并过程中会从 B 中删除。因此，尽管前一步的优化没有做出，我们可以在进程退出或执行 exec() 时回收死掉的页。
这个模型会产生一些潜在问题。第一个问题是，你可能会遇到相对深的 VM 对象层次堆栈，这可能会在发生故障时消耗扫描时间和内存。深层堆栈通常发生在进程执行 fork 后又继续 fork（无论是父进程还是子进程）。第二个问题是，你可能会在 VM 对象的深层堆栈中遇到死页，即那些无法访问的页面。在我们最后的例子中，如果父进程和子进程修改了同一个页，它们各自得到自己私有的副本，而 B 中的原始页就不再能被任何人访问。那页就可以从 B 中释放。
FreeBSD 通过一种特殊优化解决了深层堆栈问题，称为“完全被遮蔽情况”（All Shadowed Case）。如果 C1 或 C2 执行足够多的写时复制故障，完全遮蔽了 B 中的所有页，就会发生这种情况。假设 C1 达成了这一点。此时，C1 就可以完全绕过 B，因此，不再是 C1→B→A 和 C2→B→A，而是 C1→A 和 C2→B→A。但看看发生了什么——现在 B 只有一个引用（C2），所以我们可以合并 B 和 C2。最终结果是 B 被完全删除，变成了 C1→A 和 C2→A。通常情况下，B 会包含大量的页，C1 或 C2 并不容易完全遮蔽它。然而，如果我们再次执行 fork 创建一组 D 层，那么 D 层中的一个层就更有可能完全遮蔽 C1 或 C2 所表示的较小数据集。在图中的任何节点进行这种优化都有效，因此即使在一个频繁执行 fork 的机器上，VM 对象堆栈也通常不会变得太深。无论是父进程还是子进程，在执行 fork 或子进程级联 fork 时，情况都一样。
死页问题仍然存在，特别是当 C1 或 C2 没有完全遮蔽 B 时。由于我们的其他优化，这种情况不再是一个大问题，我们允许这些死页存在。如果系统内存不足，它会将这些页交换出去，占用一点交换空间，但这就是问题的全部。
VM 对象模型的优点是 fork() 非常快速，因为不需要实际复制数据。缺点是，你可能会构建一个相对复杂的 VM 对象层，这会稍微减慢页面故障处理速度，并且需要消耗内存来管理 VM 对象结构。FreeBSD 所做的优化已将这些问题减轻到可以忽略的程度，因此没有实际的缺点。
私有数据页最初要么是写时复制页，要么是零填充页。当发生修改并因此需要复制时，原始的后备对象（通常是文件）就无法再用于保存该页的副本，以便当 VM 系统需要将其重新用于其他目的时使用。这时，SWAP 就派上了用场。SWAP 被分配用于为没有其他后备存储的内存提供后备存储。FreeBSD 仅在实际需要时才为 VM 对象分配交换管理结构。然而，交换管理结构在历史上一直存在问题：
在 FreeBSD 3.X 版本中，交换管理结构预分配了一个数组，涵盖了所有需要交换后备存储的对象——即使只有该对象的少数几个页面是交换后备的。这在映射了大对象或进程具有较大 RSS（常驻集大小）时会导致内核内存碎片问题。
为了跟踪交换空间，内核内存中会保存一个“空洞列表”，这通常也会严重碎片化。由于“空洞列表”是线性列表，交换分配和释放的性能是非最优的 O(n)-每页操作。
交换释放过程中需要进行内核内存分配，这会引发低内存死锁问题。
由于交错算法（interleaving algorithm）所产生的空洞，这个问题会变得更加严重。
此外，交换块映射可能会很容易地变得碎片化，导致非连续的分配。
交换操作时，还必须动态分配内核内存用于额外的交换管理结构。
从这个列表可以看出，确实有很多改进空间。对于 FreeBSD 4.X，我对交换子系统进行了完全重写：
交换管理结构通过哈希表进行分配，而不是通过线性数组进行分配，这使得它们具有固定的分配大小，并且粒度更加细化。
不再使用线性链表来跟踪交换空间预留，现在它使用交换块的位图，位图排列成一棵基数树结构，并且在基数节点结构中有空闲空间的提示。这实际上使得交换分配和释放的操作变成了 O(1) 操作。
整个基数树位图也会预分配，以避免在低内存交换操作中分配内核内存。毕竟，系统通常在低内存时进行交换，所以我们应该避免在这些时刻分配内核内存，以避免潜在的死锁问题。
为了减少碎片化，基数树能够一次分配大块连续空间，跳过较小的碎片块。
我并没有采取最终的步骤来实现一个“分配提示指针”（allocating hint pointer），该指针将在分配过程中遍历部分交换区，以进一步保证连续的分配，或者至少保证引用的局部性，但我确保了这种添加是可以完成的。
由于 VM 系统使用所有可用的内存进行磁盘缓存，因此通常很少有真正空闲的页面。VM 系统依赖于能够正确选择未使用的页面，以便重新用于新的分配。选择最优的页面进行释放可能是任何 VM 系统最重要的功能之一，因为如果做出错误的选择，VM 系统可能被迫不必要地从磁盘重新读取页面，从而严重降低系统性能。
我们愿意在关键路径上忍受多少开销，以避免释放错误的页面？每一个错误的选择都会消耗数十万的 CPU 周期，并导致受影响进程明显的停顿，因此我们愿意承受相当大的开销，以确保选择的是正确的页面。这也是 FreeBSD 在内存资源紧张时通常优于其他系统的原因。
空闲页面的确定算法是建立在内存页面使用历史的基础上。为了获取这一历史，系统利用了大多数硬件页面表具有的页面使用位功能。
无论如何，页面使用位会被清除，稍后 VM 系统再次遇到该页面时，发现页面使用位已被设置。这表明该页面仍在被积极使用。如果位仍然清除，则表示该页面没有被积极使用。通过定期测试这个位，物理页面的使用历史（以计数器的形式）就被开发出来。当 VM 系统稍后需要释放一些页面时，检查这个历史成为确定最佳候选页面进行重用的关键。
对于那些没有此功能的平台，系统实际上会模拟一个页面使用位。它会取消映射或保护页面，如果页面再次被访问，则强制发生页面错误。当页面错误发生时，系统简单地标记页面为已使用，并取消保护该页面，以便它可以被使用。虽然仅仅为了确定页面是否被使用而强行触发页面错误看似是一项昂贵的操作，但它比将页面重用为其他用途后发现进程需要该页面并且不得不重新从磁盘获取要便宜得多。
FreeBSD 使用多个页面队列来进一步细化页面重用的选择，并确定何时必须将脏页面刷新到其后备存储。由于 FreeBSD 下的页面表是动态实体，因此从任何使用该页面的进程的地址空间中取消映射页面几乎不需要任何成本。当基于页面使用计数器选择了一个页面候选时，这正是系统所做的。系统必须区分可以理论上随时释放的干净页面和必须先写入其后备存储才能重新使用的脏页面。当找到一个页面候选时，如果该页面是脏的，则将其移到非活动队列；如果是干净的，则将其移到缓存队列。基于脏页面与干净页面的比例，系统会决定何时必须将非活动队列中的脏页面刷新到磁盘。待完成刷新，这些页面将从非活动队列移到缓存队列。此时，缓存队列中的页面仍然可以通过 VM 错误重新激活，且成本相对较低。然而，缓存队列中的页面被认为是“立即可释放的”，并将在系统需要分配新内存时以 LRU（最少最近使用）方式重用。
需要注意的是，FreeBSD VM 系统试图将干净页面与脏页面分开，专门避免不必要的脏页面刷新（这样可以节省 I/O 带宽），并且不会在内存子系统未受到压力时随意移动页面在各个页面队列之间。这就是为什么在执行 systat -vm 命令时，有些系统会看到非常低的缓存队列计数和高的活动队列计数。当 VM 系统的压力增大时，它会更加努力地保持各种页面队列在被认为最有效的水平。
有一个城市传说流传多年，称 Linux 在避免交换页面方面做得比 FreeBSD 更好，但实际上并非如此。实际上发生的情况是，FreeBSD 在主动将未使用的页面换出以腾出更多磁盘缓存空间，而 Linux 则保持未使用的页面在内存中，从而为缓存和进程页面留下了更少的内存。我不知道今天是否仍然如此。
发生的大部分页面错误都是零填充错误。通过观察 vmstat -s 输出，你通常可以看到这一点。当进程访问其 BSS 区域中的页面时，就会发生这种情况。BSS 区域期望最初为零，但 VM 系统直到进程实际访问它时才会分配内存。当发生错误时，VM 系统不仅需要分配一个新页面，还需要将其填充为零。为了优化零填充操作，VM 系统能够预先将页面填充为零并标记为已零填充，并且在发生零填充错误时请求已零填充的页面。零填充操作发生在 CPU 空闲时，但系统预零填充的页面数量有限，以避免破坏内存缓存。这是一个典型的例子，展示了为了优化关键路径而向 VM 系统中增加复杂性的情况。
页表优化是 FreeBSD VM 设计中最具争议的部分，它们随着 mmap() 的广泛使用而显现出一些压力。我认为这实际上是大多数 BSD 系统的特点，尽管我不确定它是何时首次引入的。这里有两项主要优化。首先，硬件页表不包含持久状态，而是可以随时丢弃，只需少量的管理开销。其次，系统中每个活动的页表项都具有一个管理的 pv_entry 结构，该结构与 vm_page 结构相绑定。FreeBSD 可以直接遍历已知存在的映射，而 Linux 必须检查所有 可能 包含特定映射的页表，看看它是否存在，这在某些情况下可能导致 O(n^2) 的开销。正因为如此，FreeBSD 在内存受到压力时往往能够做出更好的页面重用或交换选择，从而在负载下提供更好的性能。然而，FreeBSD 需要内核调优来适应大型共享地址空间的情况，例如在新闻系统中可能会发生的情况，因为它可能会耗尽 pv_entry 结构。
Linux 和 FreeBSD 都在这个领域需要改进。FreeBSD 尝试最大化潜在稀疏活动映射模型的优势（例如并非所有进程都需要映射共享库的所有页面），而 Linux 则在简化算法方面做出了努力。FreeBSD 在这里通常具有性能优势，代价是浪费了一些额外的内存，但 FreeBSD 在处理一个大文件被大量进程共享的情况下表现不佳。另一方面，Linux 在处理许多进程稀疏映射同一共享库的情况时表现不佳，而且在决定页面是否可以重用时也未必优化。
最后，我们来讨论页面着色优化。页面着色是一种性能优化，旨在确保对虚拟内存中连续页面的访问最大程度地利用处理器缓存。在古老的时代（即10多年前），处理器缓存通常是映射虚拟内存而非物理内存的。这导致了许多问题，包括在某些情况下必须在每次上下文切换时清空缓存，并且缓存中存在数据别名问题。现代处理器缓存精确地映射物理内存来解决这些问题。这意味着进程地址空间中的两个相邻页面可能并不对应于缓存中的两个相邻页面。实际上，如果不小心，虚拟内存中的相邻页面可能会映射到处理器缓存中的同一页面，从而导致缓存中的数据被提前丢弃，降低 CPU 性能。即便是多路集合相联缓存（尽管效果有所减轻），也会出现这种情况。
FreeBSD 的内存分配代码实现了页面着色优化，意味着内存分配代码将尝试从缓存的角度寻找连续的空闲页面。例如，如果物理内存的第 16 页分配给进程的第 0 页虚拟内存，并且缓存能够容纳 4 页，页面着色代码就不会将物理内存的第 20 页分配给进程的第 1 页虚拟内存。相反，它会分配物理内存的第 21 页。页面着色代码会尽量避免分配第 20 页，因为这会与第 16 页映射到相同的缓存内存，导致缓存不最优。正如你可以想象的那样，这段代码为 VM 内存分配子系统增加了显著的复杂性，但结果是非常值得的。页面着色使得虚拟内存在缓存性能方面与物理内存一样具有确定性。
现代操作系统中的虚拟内存必须高效地处理许多不同的问题，并支持多种使用模式。BSD 系统历来采用的模块化和算法化方法使得我们可以研究并理解当前的实现，并且相对容易地替换掉代码的大部分部分。近年来，FreeBSD 的虚拟内存系统有了许多改进，相关工作仍在继续进行。
FreeBSD 使用固定的交换交错，默认值为 4。这意味着 FreeBSD 为四个交换区域保留空间，即使你只有一个、两个或三个交换区域。由于交换是交错的，如果你实际上没有四个交换区域，那么表示“这四个交换区域”的线性地址空间就会发生碎片化。例如，如果你有两个交换区域 A 和 B，FreeBSD 对这两个交换区域的地址空间表示将以 16 页为一个块进行交错：
FreeBSD 3.X 使用“连续空闲区域列表”方法来管理空闲交换区域。这个方法的思路是，较大的空闲线性空间可以通过单个列表节点（kern/subr_rlist.c）来表示。但由于碎片化，连续列表最终会变得非常碎片化。在上面的例子中，完全未使用的交换空间将会将 A 和 B 显示为“空闲”，而 C 和 D 显示为“全部分配”。每个 A-B 序列都需要一个列表节点来进行管理，因为 C 和 D 是空洞，不能与下一个 A-B 序列合并。
为什么我们要交错交换空间，而不是直接把交换区域附加到末尾然后做一些更复杂的处理？原因是，在分配线性地址空间时，自动将其交错到多个磁盘上，比尝试将这种复杂性放到其他地方要容易得多。
碎片化会导致其他问题。由于 3.X 系统下它是一个线性列表，而且具有大量固有的碎片化，交换的分配和释放变成了 O(N) 的算法，而不是 O(1) 的算法。再加上一些其他因素（如频繁交换），你就会进入 O(N^2) 和 O(N^3) 级别的开销，这会非常糟糕。在低内存情况下，3.X 系统可能还需要在交换操作过程中分配 KVM 来创建新的列表节点，这可能会导致死锁。
在 4.X 版本中，我们不再使用连续列表，而是使用基数树和交换块的位图来代替范围列表节点。我们虽然在开始时就预分配了所有位图所需的空间，但由于使用了位图（一位代表一个块），而不是使用节点的链表，这样反而节省了更多内存。通过使用基数树而不是线性列表，即使树发生碎片化，性能几乎可以达到 O(1)。
systat -vm 中看到低缓存队列计数和高活动队列计数的情况有什么关系？systat 的统计数据会将活动页和脏页一起算入活动队列计数吗？是的，这是令人困惑的。关系在于“目标”与“现实”。我们的目标是将页面分开，但现实情况是，如果系统不在内存紧张的状态下，我们其实不需要特别去分开它们。
这意味着，当系统不受压力时，FreeBSD 不会努力将脏页（非活动队列）和干净页（缓存队列）分开，也不会试图将页从活动队列移动到非活动队列，即使这些页没有被使用。
一个 COW 页面错误可以是零填充的，也可以是程序数据的。无论哪种情况，机制都是一样的，因为支持程序数据的页面几乎可以肯定已经在缓存中。我确实将这两者放在一起讨论。FreeBSD 不会对程序数据或零填充进行预 COW，但它确实会对已经在缓存中的页面进行预映射。
pv_entry 和 vm_page 的细节（或者是否应该是 vm_pmap，如 McKusick、Bostic、Karel 和 Quarterman 在 4.4 版的第 180-181 页所述）？具体来说，什么样的操作/反应会要求扫描这些映射？一个 vm_page 代表一个（对象，索引号）元组。一个 pv_entry 代表一个硬件页面表项（pte）。例如，如果有五个进程共享同一个物理页面，其中三个进程的页面表实际上映射了该页面，那么这个页面将由一个 vm_page 结构和三个 pv_entry 结构来表示。
pv_entry 结构只代表 MMU 映射的页面（一个 pv_entry 代表一个 pte）。这意味着当我们需要删除一个 vm_page 的所有硬件引用（例如为了重用该页面、将其换出、清空、标记为脏页等）时，我们可以通过扫描与该 vm_page 关联的 pv_entry 链表来删除或修改它们在页面表中的 pte。
在 Linux 中，没有这样的链表。要删除一个 vm_page 的所有硬件页面表映射，Linux 必须索引到每个可能映射该页面的 VM 对象中。例如，如果有 50 个进程都映射了同一个共享库，而你想删除该库中的 X 页面，那么即使只有 10 个进程真正映射了该页面，Linux 也需要索引到这 50 个进程的页面表。因此，Linux 在简化设计的同时牺牲了性能。很多在 FreeBSD 中是 O(1) 或小 N 的虚拟内存算法，在 Linux 中则可能变成 O(N)、O(N^2) 或更差。由于表示一个特定页面的 pte 通常在所有映射了该页面的页面表中位于相同的偏移量，通过减少对页面表的访问（只针对需要修改的 pte）常常能够避免冲掉该偏移量所在的 L1 缓存行，从而提高性能。
FreeBSD 通过增加复杂性（pv_entry 机制）来提高性能（将页面表的访问限制在 仅 需要修改的 pte 上）。
然而，FreeBSD 在这方面存在扩展性问题，Linux 不存在。即使有充足的空闲内存，当数据被大量共享时，FreeBSD 也会面临 pv_entry 结构的数量限制。在这种情况下，即使有足够的内存，仍然可能耗尽 pv_entry 结构。这可以通过在内核配置中增加 pv_entry 结构的数量来解决，但我们仍然需要找到更好的方法。
关于页面表的内存开销与 pv_entry 方案的比较：Linux 使用“不丢弃”的“永久”页面表，但不需要为每个可能映射的 pte 配置一个 pv_entry。FreeBSD 使用“丢弃式”页面表，但为每个实际映射的 pte 添加一个 pv_entry 结构。我认为内存利用率最终差不多，这使得 FreeBSD 在算法上具有优势，因为它能够以非常低的开销随时丢弃页面表。
你知道 L1 硬件内存缓存是如何工作的吗？我来解释一下：假设一台机器有 16MB 的主内存，但只有 128K 的 L1 缓存。通常，这个缓存的工作方式是，每个 128K 的主内存块使用相同的 128K 缓存。如果你访问主内存中的 0 偏移地址，然后访问主内存中的 128K 偏移地址，你可能会丢弃从 0 偏移地址读取的数据！
现在，我简化了很多。刚才描述的是所谓的“直接映射”硬件内存缓存。大多数现代缓存是所谓的 2 路组相联缓存或 4 路组相联缓存。组相联方式允许你访问最多 N 个不同的内存区域，这些区域可以共享同一个缓存而不破坏先前缓存的数据。但最多只有 N 个。
因此，如果我有一个 4 路组相联缓存，我可以访问 0 偏移地址、128K 偏移地址、256K 偏移地址和 384K 偏移地址，并且仍然能够再次访问 0 偏移地址并从 L1 缓存中获取。如果我接着访问 512K 偏移地址，然而，缓存中将丢弃四个已缓存的数据对象中的一个。
这非常重要……极其重要，因为处理器的大部分内存访问必须能够从 L1 缓存中获取，因为 L1 缓存以处理器频率运行。只要发生 L1 缓存未命中的情况，必须去 L2 缓存或主内存读取数据，处理器就会停滞，并且可能会浪费数百条指令的时间，等待从主内存读取数据的完成。与现代处理器核心的速度相比，主内存（你在计算机中装的动态 RAM）是 慢 的。
好了，现在说说页面着色：所有现代内存缓存都是所谓的 物理 缓存。它们缓存的是物理内存地址，而不是虚拟内存地址。这使得缓存能够在进程上下文切换时保持不变，这是非常重要的。
但是，在 UNIX® 世界中，你处理的是虚拟地址空间，而不是物理地址空间。你写的任何程序都会看到它被分配的虚拟地址空间。实际上，支持该虚拟地址空间的 物理 页面不一定是物理连续的！事实上，你可能有两个在进程地址空间中相邻的页面，它们可能会位于 物理 内存的 0 偏移地址和 128K 偏移地址。
程序通常假设两个相邻的页面会被最优地缓存。也就是说，你可以在两个页面中访问数据对象，而不会相互覆盖彼此的缓存条目。但这只有在虚拟地址空间下的物理页面是连续的情况下才成立（就缓存而言）。
这就是页面着色的作用。页面着色并不是将 随机 物理页面分配给虚拟地址，这可能会导致不理想的缓存性能，而是将 合理连续 的物理页面分配给虚拟地址。这样，程序可以假设底层硬件缓存的特性与程序直接在物理地址空间中运行时的表现相同。
请注意，我使用了“合理连续”而不是“连续”。从 128K 直接映射缓存的角度来看，物理地址 0 与物理地址 128K 是相同的。因此，你虚拟地址空间中的两个相邻页面，可能会位于物理内存的 128K 偏移地址和 132K 偏移地址，但也很容易位于物理内存的 128K 偏移地址和 4K 偏移地址，并且仍然保持相同的缓存性能特性。所以，页面着色 不 必须将真正连续的物理内存页面分配给连续的虚拟内存页面，它只需要确保从缓存性能和操作的角度来看，分配的页面是连续的。
发生 VM 错误并不昂贵，如果底层页面已经在内存中并且可以直接映射到进程中。但如果这些错误频繁发生，就可能变得非常昂贵。一个典型的例子是反复运行类似 或 这样的程序。如果程序二进制文件已经映射到内存中，但没有映射到页表中，那么程序每次运行时都需要发生错误，访问程序将访问的所有页面。对于这些已经在 VM 缓存中的页面，这是不必要的，因此 FreeBSD 会尝试预先填充进程的页表，将这些已存在于 VM 缓存中的页面映射到页表中。FreeBSD 目前还没有做的是在 exec 时预复制某些页面。例如，当你在运行 vmstat 1 时运行 程序时，你会注意到即使是反复运行，也总会发生一定数量的页面错误。这些是零填充错误，而不是程序代码错误（这些已经预错误过）。在执行 exec 或 fork 时预复制页面是一个可以进一步研究的领域。
vmstat 1 示例中，是否不会有一些页面错误是数据页面错误（从可执行文件到私有页面的 COW）？也就是说，我期望页面错误既有零填充的，也有程序数据的。还是你在暗示 FreeBSD 确实对程序数据进行了预 COW？
