FreeBSD 虚拟机系统的设计元素

在继续讨论实际设计之前，让我们花一点时间讨论维护和现代化任何长期存在的代码库的必要性。在编程世界中，算法往往比代码更重要，正是由于 BSD 的学术渊源，从一开始就非常重视算法设计。更多地关注设计通常会导致一个干净灵活的代码库，可以相当容易地进行修改、扩展或替换。虽然有些人认为 BSD 是一个“古老”的操作系统，但我们这些在上面工作的人倾向于将其视为一个“成熟”的代码库，其各个组件经过修改、扩展或用现代代码替换。它已经发展，无论某些代码有多旧，FreeBSD 都处于技术前沿。这是一个重要的区别，不幸的是很多人没有意识到。程序员可能犯的最大错误是不从历史中吸取教训，而这正是许多其他现代操作系统所犯的错误。Windows NT® 是最好的例子，其后果是灾难性的。Linux 在某种程度上也犯了这个错误——足以让我们 BSD 人偶尔对此开开玩笑。Linux 的问题仅仅是缺乏经验和历史来对比想法，而 Linux 社区正在像 BSD 社区一样迅速解决这个问题——通过持续的代码开发。另一方面，Windows NT® 人反复犯着 UNIX® 几十年前解决的同样的错误，然后花费数年时间来修复它们。一次又一次。他们严重患有“不是在这里设计的”和“我们总是对的，因为我们的营销部门这么说”的毛病。我对任何不能从历史中学习的人都没有耐心。

FreeBSD 设计的许多明显复杂性，尤其是在虚拟内存/交换子系统中，是由于必须解决在各种条件下出现的严重性能问题而直接导致的。这些问题不是由于糟糕的算法设计，而是源于环境因素。在任何平台之间的直接比较中，当系统资源开始承受压力时，这些问题变得最为明显。当我描述 FreeBSD 的虚拟内存/交换子系统时，读者应该始终牢记两点

因此，任何将在未来几年内存活并可维护的代码库都必须从一开始就设计得当，即使这会牺牲一些性能。20 年前，人们仍在争论用汇编语言编程比用高级语言编程更好，因为它生成的代码速度快十倍。如今，该论点的谬误显而易见——算法设计和代码泛化的并行性也一样。

描述 FreeBSD 虚拟内存系统的最佳方法是从用户级进程的角度来看待它。每个用户进程都看到一个单个的、私有的、连续的虚拟内存地址空间，其中包含几种类型的内存对象。这些对象具有不同的特性。程序代码和程序数据实际上是一个单个的内存映射文件（正在运行的二进制文件），但程序代码是只读的，而程序数据是写时复制的。程序 BSS 只是分配的内存，并在需要时填充零，称为按需零页填充。任意文件也可以映射到地址空间中，这就是共享库机制的工作方式。此类映射可能需要修改才能保持对进行映射的进程的私有性。fork 系统调用在现有复杂性的基础上为虚拟内存管理问题增加了一个全新的维度。

程序二进制数据页（一个基本的写时复制页）说明了这种复杂性。程序二进制文件包含一个预初始化的数据段，该数据段最初直接从程序文件中映射。当程序加载到进程的虚拟内存空间时，此区域最初是内存映射的，并由程序二进制文件本身支持，允许虚拟内存系统释放/重用页面，然后从二进制文件中重新加载它。但是，一旦进程修改了此数据，虚拟内存系统必须为此进程创建该页面的私有副本。由于私有副本已被修改，因此虚拟内存系统可能不再释放它，因为不再有任何方法可以稍后恢复它。

您会立即注意到，最初简单的文件映射变得更加复杂了。可以按页面为基础修改数据，而文件映射则同时包含许多页面。当进程分叉时，复杂性进一步增加。当进程分叉时，结果是两个进程——每个进程都有自己的私有地址空间，包括原始进程在调用 fork() 之前进行的任何修改。对于虚拟内存系统来说，在 fork() 时创建数据的完整副本是愚蠢的，因为很有可能这两个进程中至少有一个从那时起只需要读取该页面，从而允许继续使用原始页面。私有页面再次变为写时复制，因为每个进程（父进程和子进程）都希望它们自己的分叉后修改对自身保持私有，并且不影响另一个进程。

FreeBSD 使用分层的虚拟内存对象模型来管理所有这些。原始二进制程序文件最终成为最低的虚拟内存对象层。在它的上面会推送一个写时复制层，以保存必须从原始文件中复制的那些页面。如果程序修改了属于原始文件的数据页面，虚拟内存系统会发生故障并在上层创建该页面的副本。当进程分叉时，会推送其他虚拟内存对象层。通过一个相当基本的示例，这可能会更有意义。fork() 是任何 *BSD 系统的常见操作，因此此示例将考虑一个启动并分叉的程序。当进程启动时，虚拟内存系统创建一个对象层，我们称之为 A

A 表示文件——页面可以根据需要在文件的物理介质中分页进出。从磁盘分页进入对于程序来说是合理的，但我们真的不想分页出去并覆盖可执行文件。因此，虚拟内存系统创建第二个层 B，它将由交换空间物理支持

在第一次写入此后的页面时，在 B 中创建一个新页面，并将其内容从 A 初始化。B 中的所有页面都可以分页进入或分页到交换设备。当程序分叉时，虚拟内存系统创建两个新的对象层——C1 用于父进程，C2 用于子进程——它们位于 B 的顶部

在这种情况下，假设B中的一个页面被原始父进程修改。该进程将发生写时复制错误并复制C1中的页面，同时保持B中的原始页面不变。现在，假设B中的同一个页面被子进程修改。该进程将发生写时复制错误并复制C2中的页面。由于C1和C2都拥有副本，因此B中的原始页面现在完全隐藏，如果B不代表“真实”文件，则理论上可以销毁它；但是，由于这种优化非常细粒度，因此并不容易实现。FreeBSD没有进行此优化。现在，假设（通常情况下）子进程执行了exec()。它的当前地址空间通常会被表示新文件的新地址空间替换。在这种情况下，C2层会被销毁。

在这种情况下，B的子进程数量减少到一个，并且对B的所有访问现在都通过C1进行。这意味着B和C1可以合并在一起。在合并期间，B中也存在于C1中的任何页面都将从B中删除。因此，即使无法进行上一步中的优化，我们也可以在任一进程退出或exec()时恢复已删除的页面。

这种模型产生了一些潜在的问题。首先，您可能会得到一个相对较深的层叠式VM对象栈，这在发生错误时会增加扫描时间和内存消耗。当进程分叉然后再次分叉（父进程或子进程）时，可能会发生深度分层。第二个问题是，您可能会得到深藏在VM对象栈中的已删除且无法访问的页面。在我们最后一个示例中，如果父进程和子进程都修改了同一个页面，则它们都会获得该页面的私有副本，并且B中的原始页面将不再可供任何人访问。B中的该页面可以被释放。

FreeBSD使用一种称为“全阴影案例”的特殊优化来解决深度分层问题。如果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都无法完全隐藏它。但是，如果我们再次分叉并创建一组D层，则其中一层最终能够完全隐藏C1或C2表示的较小的数据集的可能性要大得多。相同的优化将在图中的任何点起作用，其最终结果是，即使在高度分叉的机器上，VM对象栈的深度也往往不会超过4。这对于父进程和子进程都是正确的，无论父进程是否正在进行分叉，或者子进程是否级联分叉。

在C1或C2未完全隐藏B的情况下，已删除页面问题仍然存在。由于我们的其他优化，这种情况不会构成太大问题，我们只需允许页面处于已删除状态。如果系统内存不足，它会将这些页面交换出去，消耗少量交换空间，仅此而已。

VM对象模型的优点是fork()非常快，因为不需要进行真正的數據复制。缺点是您可以构建一个相对复杂的VM对象分层，这会稍微减慢页面错误处理速度，并且您需要花费内存来管理VM对象结构。FreeBSD进行的优化证明可以充分减少这些问题，因此可以忽略它们，不会留下任何真正的缺点。

私有数据页面最初是写时复制页面或零填充页面。当进行更改（因此进行复制）时，原始备份对象（通常是文件）在VM系统需要将其重新用于其他目的时，将无法再用于保存页面的副本。这就是SWAP发挥作用的地方。分配SWAP来创建没有其他备份存储的内存的备份存储。FreeBSD仅在实际需要时才为VM对象分配交换管理结构。但是，交换管理结构在历史上一直存在问题。

从该列表可以看出，有很大的改进空间。对于FreeBSD 4.X，我完全重写了交换子系统。

我没有采取最后一步，即使用“分配提示指针”在分配过程中遍历交换的一部分，以进一步保证连续分配或至少是引用局部性，但我确保可以添加此功能。

由于VM系统使用所有可用内存进行磁盘缓存，因此通常只有很少的真正空闲页面。VM系统依赖于能够正确选择未使用的页面以将其重新用于新的分配。选择要释放的最优页面可能是任何VM系统可以执行的单个最重要的功能，因为如果它做出了错误的选择，VM系统可能被迫不必要地从磁盘检索页面，从而严重降低系统性能。

我们愿意在关键路径中承受多少开销以避免释放错误的页面？我们做出的每个错误选择都会花费我们数十万个CPU周期，并导致受影响进程的明显停顿，因此我们愿意承受大量的开销以确保选择了正确的页面。这就是为什么当内存资源变得紧张时，FreeBSD往往优于其他系统。

空闲页面确定算法建立在内存页面使用历史记录的基础上。为了获取此历史记录，系统利用大多数硬件页表具有的页面使用位功能。

在任何情况下，页面使用位都会被清除，并且在稍后的某个时间点，VM系统再次遇到该页面并发现页面使用位已被设置。这表示该页面仍在被积极使用。如果该位仍然是清除的，则表示该页面没有被积极使用。通过定期测试此位，可以开发物理页面的使用历史记录（以计数器的形式）。当VM系统稍后需要释放一些页面时，检查此历史记录成为确定最佳候选页面以重用的基石。

对于那些没有此功能的平台，系统实际上会模拟页面使用位。它取消映射或保护页面，如果再次访问页面则强制发生页面错误。当发生页面错误时，系统只需将页面标记为已使用并取消保护页面，以便可以使用它。虽然仅仅为了确定页面是否正在使用而发生此类页面错误似乎是一个代价高昂的主张，但它比将页面重新用于其他目的，结果发现进程需要它并且必须转到磁盘的成本要低得多。

FreeBSD使用多个页面队列来进一步优化要重用的页面的选择，以及确定何时必须将脏页面刷新到其备份存储。由于页表在FreeBSD下是动态实体，因此从使用它的任何进程的地址空间中取消映射页面几乎不花费任何代价。当根据页面使用计数器选择页面候选者时，这正是所做的操作。系统必须区分理论上可以随时释放的干净页面和必须先写入其备份存储才能可重用的脏页面。找到页面候选者后，如果它是脏的，则将其移动到非活动队列，如果它是干净的，则将其移动到缓存队列。一个单独的算法基于脏页面与干净页面的比率来确定必须何时将非活动队列中的脏页面刷新到磁盘。完成此操作后，已刷新的页面将从非活动队列移动到缓存队列。此时，缓存队列中的页面仍然可以通过VM错误以相对较低的成本重新激活。但是，缓存队列中的页面被认为是“可以立即释放的”，并且当系统需要分配新内存时，将以LRU（最近最少使用）的方式重新使用它们。

需要注意的是，FreeBSD VM系统试图分离干净页面和脏页面，其明确的原因是避免不必要地刷新脏页面（这会占用I/O带宽），也不会在内存子系统没有压力时随意地在各个页面队列之间移动页面。这就是为什么在执行systat -vm命令时，您会看到某些系统的缓存队列计数非常低，而活动队列计数很高。随着VM系统变得更加紧张，它会付出更大的努力来将各个页面队列维持在确定最有效的级别。

多年来一直流传着一个都市传说，认为Linux在避免换出方面比FreeBSD做得更好，但实际上并非如此。真正发生的情况是，FreeBSD会主动将未使用的页面换出以腾出空间用于更多磁盘缓存，而Linux则将未使用的页面保留在核心内存中，从而减少了可用于缓存和进程页面的内存。我不知道今天是否仍然如此。

如果底层页面已存在于核心内存中并且可以简单地映射到进程中，那么发生虚拟内存错误并不昂贵，但如果定期发生大量虚拟内存错误，则可能会变得昂贵。一个很好的例子是反复运行像ls(1)或ps(1)这样的程序。如果程序二进制文件已映射到内存但未映射到页表中，则每次运行程序时都必须将程序将访问的所有页面都取错误。当相关页面已存在于虚拟内存缓存中时，这是不必要的，因此FreeBSD将尝试使用这些已存在于虚拟内存缓存中的页面预填充进程的页表。FreeBSD尚不支持的一件事是在exec时预先执行写时复制某些页面。例如，如果在运行vmstat 1时运行ls(1)程序，您会注意到它总是会发生一定数量的页面错误，即使您反复运行它也是如此。这些是零填充错误，而不是程序代码错误（这些错误已预先取错误）。在exec或fork时预先复制页面是一个需要更多研究的领域。

发生的大部分页面错误都是零填充错误。您通常可以通过观察vmstat -s输出看到这一点。当进程访问其BSS区域中的页面时，就会发生这种情况。BSS区域预计最初为零，但虚拟内存系统在进程实际访问它之前根本不会分配任何内存。当发生错误时，虚拟内存系统不仅必须分配一个新页面，还必须将其清零。为了优化清零操作，虚拟内存系统能够预先清零页面并将其标记为已清零，并在发生零填充错误时请求预先清零的页面。只要CPU空闲，就会发生预先清零操作，但系统预先清零的页面数量受到限制，以避免清除内存缓存。这是一个很好的例子，说明了为了优化关键路径而增加了虚拟内存系统的复杂性。

页表优化构成了FreeBSD虚拟内存设计中最有争议的部分，并且随着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页相同的缓存内存，并导致非最佳缓存。正如您可以想象的那样，此代码增加了虚拟内存内存分配子系统的相当大的复杂性，但结果非常值得付出努力。在缓存性能方面，页面着色使虚拟内存与物理内存一样确定性。

现代操作系统中的虚拟内存必须有效地解决许多不同的问题，并适应许多不同的使用模式。BSD历来采用的模块化和算法方法使我们能够研究和理解当前的实现，以及相对干净地替换代码的大部分内容。在过去几年中，FreeBSD虚拟内存系统已经进行了许多改进，并且工作仍在继续。