FreeBSD虚拟内存VM系统设计原理

1、FreeBSD虚拟内存 VM 系统设计原理来源：版权说明：这篇文章原载于2000年1月的DaemonNews。这份版本可能包括了Matt以及其他作者的更新，以反映FreeBSD VM实现的进展。这个标题实在是一个很自负的说法，我的意思是，我正试图描述整个FreeBSD VM系统，以一种让多数人都能够接受的方式。在过去的一年中，我集中精力于FreeBSD的主要内核子系统中的大量模块，特别是VM和磁盘交换(Swap)子系统，以及相关的NFS代码。我只是重写了所有代码中很少的部分。在VM领域，我做的最主要的重写是针对磁盘交换部分的代码进行的。我的绝大部分工作是清理和维护，其中包括适度的代码重写，而没

2、有对VM子系统中的算法进行大规模的调整。VM子系统的主要理论基础没有发生变化，而绝大多数与VM相关的功绩应该归于John Dyson和David Greenman。与Kirk这样有资历的学者不同，我并不想尝试为每一个特性标记特定的人名，因为我经常把他们搞错。1.入门在开始介绍实际的设计之前，让我们来花些时间来介绍维护，并让那些存在已久的代码基础(codebase)进行现代化的必要性。在编程者的世界中，算法总是趋于比代码更为重要。同时，作为BSD的学术传统的一部分，在开始时就对算法设计加以特别的关注也恰好符合这一点。在设计上给予特别的关注的结果通常就是一个干净而灵活的代码基础，它能够被很容易地修

3、改、扩展，或随着时间的推移被替换掉。尽管BSD被某些人认为是一个古旧的操作系统，我们这些为之工作的人则认为它更多地是一个成熟的代码基础，其上的众多组件被修改、扩展甚至替换为现代化的代码。它正在进化，而且，无论代码中的某些部分多么地古老，FreeBSD总在接受新鲜血液。这是FreeBSD的一项重要特点，而许多人往往忽视了它。程序员能够犯下的最大错误是不肯学习历史，而这是许多其他现代操作系统中非常常见的问题。NT是一个最好的例子，而其结果是相当可怕的。Linux也不同程度地犯下了许多类似的错误-这些错误足够在BSD开发者中间，每隔一段时间就流传一次笑话。Linux的问题可以简单地归结为，缺乏可以用

4、来比较思想的经验和历史，在不断的代码开发过程中，Linux团队可以和BSD团队一样快捷地找到问题所在。而NT的开发者，另一方面，重复地犯下Unix几十年前就已经解决掉的错误，并且花上几年来修复它们，并且一而再、再而三地这样做。他们最严重的问题是not designed here(此处没有进行设计)和we are always right because our marketing department says so(我们永远是对的，因为我们的市场部门这样说)。我认为不愿学习历史的人是不能被原谅的。许多FreeBSD设计中非常明显地复杂的部分，特别是在VM/Swap子系统中的那些，是在不同条件

5、下不得不解决的那些性能问题的直接结果。这些问题并不是由糟糕的算法设计造成的，它们来自实际的环境。在平台之间的直接比较中，这些问题由于系统资源受到重压而变得非常明显。在我描述FreeBSD的VM/Swap子系统的同时，读者应始终在头脑中保持两个重要的概念。首先，高性能的设计的重要方面是我们常说的优化关键路径。这一原则通常的结果是代码的膨胀，因为它能够让关键路径的代码的性能变得更好。第二，坚固的、范型化的设计在长时间的运行中胜过那些深度最优化的设计。尽管范型化的设计与那些经过深度优化的设计相比，前者的性能在最初实现中可能更差，但范型化设计能够更容易地适应变化的条件，而过分深度优化的设计则无法适应，

6、以至于不得不丢弃。任何得以幸存，并在几年后能够被维护的代码基础，因此都必须从一开始就进行正确的设计，即使它的代价是少量性能上的衰退。20年前，人们曾认为使用汇编语言要好于高级语言，因为它能够产生快10倍以上的代码；而今天，上述论点的错误是非常明显的，因为算法设计和编译技术的发展已经大大降低了高级语言与汇编语言的差距。2.VM对象开始描述FreeBSD VM系统的最好方法是从用户级进程的方面去观察它。每一个用户进程可以看到一个单独的、私有的、连续的虚拟内存地址空间，包括多种类型的内存对象。这些对象有不同的特征。程序代码和数据被保存在一个单独的内存映射文件(将要执行的二进制文件)中，但程序代码是只

7、读的，而数据则是写时复制的。程序BSS是分配的内存，而在需要时它们将被清零，这也被称作按需填零页。同时，任何文件都可以被映射到内存地址空间，这也是共享库(shared library,Windows上的动态连接库与它类似，译注)的工作机制。这类映射可以要求其上的修改对进程私有。fork系统调用则是VM管理问题中更为复杂的一个。从程序的二进制数据页(基本上是写时复制页)可以看出上述问题的复杂性。程序的二进制代码包括了预先初始化的数据部分，它们在初始时，从程序文件直接映射出来。当程序被加载到一个进程VM空间时，这一区域被进行内存映射，随后由程序代码本身进行维护，让VM系统来释放/重用这些页，或者从

8、程序文件中重新加载它们。但是，当进程修改这些数据时，VM系统必须为进程作一份私有的副本。由于私有副本已经被改变，VM系统就不能再释放他们，因为如果这样的话，就没有办法把它们重新恢复了。你马上会注意到，原本简单的文件映射变得复杂了许多。数据可能被一页一页地修改，而文件映射只是一次包含了许多页。在进程fork时，产生的两个进程-每一个都拥有私有的地址空间-都必须包括原先进程在调用fork()之前的所有修改。让VM系统一次制作所有数据的副本是愚蠢的，因为很可能两个进程中至少有一个只需要读它们所在的页，这使得原先的页仍然可以被继续使用。私有的页被再次标记为写时复制，因为每个进程(无论是父进程还是子进程

9、)都与其他们自己的、在fork之后的修改仍然是私有的，而不会影响另一个进程。FreeBSD采用一种分层的VM对象模型来管理所有这些对象。最初的程序二进制文件作为VM对象层中的最低部分。写时复制层随后被放到它顶上，以保持那些页在需要时所产生的副本。如果程序修改了属于原始文件的数据页，VM系统将获得一个中断(fault)，并在更高的这层复制那一页。当进程fork时，将产生附加的VM对象层。通过一个很基本的例子可以得到更多的感性认识。fork是所有*BSD系统的一个公共的操作，因此这一事例将考虑一个程序开始，然后fork。当进程开始时，VM系统创建一个对象层，我们称之为A：A表示文件-页面可以在需要

10、时从文件的物理介质中换入(page in)和换出(page out)。从磁盘上换入一部分数据对程序来说是很正常的，但我们并不希望页面被换出并覆盖原始的可执行文件。VM系统因此建立一个新的层，B，它将由交换空间进行物理的维护。其后第一次页面写入将导致B中创建一个新的页，它的内容将根据A中的对应页初始化。所有B中的页可以与交换设备换入和换出。当程序fork时，VM系统创建两个新的对象层，父进程的C1和子进程的C2，这两层都在B上：在这个例子中，一个B中的页由父进程进行了修改，进程将得到一个写时复制中断，并复制C1中的页，而B中的页不会被触及。现在，子进程也修改了一些数据，于是在C2中发生了类似的事

11、情。现在，B中的原始页对于C1,C2都不再可见，因为C1和C2都拥有了一份私有的、修改过的副本；此外，如果B层并不表示一个实在的文件的话，它在理论上就可以释放掉了。然而，释放B层中的个别块这类优化的价值不高，因为它过于琐碎，而且是如此的精细。FreeBSD并不进行这类优化。现在，假定(就像通常的情况那样)，子进程调用了exec()，那么当前地址空间就被一个新的文件所表示的空间所代替。在这种情况中，C2层被释放：在这种情况下，B的子节点个数下降到1，于是所有对B的访问将直接通过C1完成。这意味着B和C1可以被折叠到一起。任何在B和C1中都存在的页在折叠过程中都将从B中删除。因而，尽管这一油花在前

12、一步骤中不被完成，但我们仍然可以在exec()或exit时恢复那些不再使用的页。这一模型造成了一系列潜在的问题。首先，你可能会得到一个相对深的VM对象层栈，当产生中断时，这将造成扫描时间的增加，并浪费内存。深的层在进程fork并再次fork的时候(无论父进程还是子进程)产生。其次，那些不可能再次被访问的页可能逐步在VM对象栈中积累。我们的最后一个例子将是，当父进程和子进程都修改了同一页，它们都拥有了那一页的私有副本，而B中的原始页将不可能被访问到时，B中的这一页将被释放。FreeBSD通过一种被称作全覆盖特例的特殊优化来解决深层问题。这一情况发生于，当C1或C2产生了足够的写时复制中断，并完全

13、包含了B中的所有页面时。以C1达到这一情况为例。C1现在可以完全绕过B，因此，我们不再采用C1BA和C2BA的访问方式，相反，我们将采用C1A和C2BA。不过，另一方面，我们观察到现在B只有1个引用(C2)，因此我们可以将B与C2折叠到一起。最终的结果是，B可以被整个删除，因而我们有C1A和C2A。通常情况下，B将包括大量的页面，而无论是C1还是C2都不能完全地盖住它。如果此时我们再次fork，并创建一组D层，那么，就非常有可能D层最终完全覆盖C1或C2中远小的数据集。同样的优化将在图中的任意一点工作，而最终结果将是即使在经常进行fork的机器上，VM对象栈也基本上不会超过4层。无论父进程和子

14、进程是否进行fork，无论子进程是否进行层叠的fork，上述结论都是正确的。某些不可能被访问的页面可能依然存在，如果C1和C2都不能完全覆盖B。由于我们的其他优化，这已经不知造成问题，因此我们将允许这样的页面存在。如果系统内存不足，则这些页面将被换出，消耗一些交换空间，但不会包括其他的工作了。VM对象模型的好处是fork()非常快，因为并不需要实际进行写操作。缺点是VM对象层相对复杂，这略微减慢了缺页中断的处理，而且，需要额外的内存来管理VM对象结构。FreeBSD的优化证明这些问题完全可以被忽略，从而实际上不存在什么缺陷。3.交换层私有的数据页在开始时，要么是写时复制页，要么是按需清零页。当

15、发生修改，并因此进行赋值时，页背后的对象(通常是一个文件)将不能再被作为VM系统需要重用一页时页的可靠副本。这时将用到交换区(swap)。交换区被分配作为内存的一个辅助存储区，它不能被用作其他目的。FreeBSD只有在真的需要时才分配交换管理结构。但是，交换管理结构在历史上是存在问题的。在FreeBSD 3.X中，交换管理结构预先分配一个数组，它包括了需要较缓存储的整个对象-哪怕那个对象中只有很少的页是基于交换区的。当映射大的对象，或者一个有大的运行尺寸(RSS)的进程fork时，这会造成内核内存碎片问题。此外，为了保持对交换空间的追踪，内核内存中将保存一个空洞表，这也趋于严重地产生碎片。由于

16、洞表是一个线性表，交换分配和释放性能不是最优的，每页O(n)。此外，它也要求在交换区释放进程时进行内核内存分配，而这将造成内存不足时的死锁。由于采用的交错算法，由空洞产生的问题变得更为严重。同时，在非连续地分配内存时，交换区块映射很快就会变得充满碎片。内核内存也必须在发生换出(s)时很快地分配交换区管理结构。显然，这些都有很大的改善余地。在FreeBSD 4.X中，我整个地重写了交换子系统。通过这次重写，交换区结构被通过一个散列表(hash table)而不再通过线性数组来分配，这带来了固定的分配尺寸和更好的粒度控制。取代原先使用线性链表来追踪预留交换空间的是，现在的系统使用一个包含空闲区域线

17、索的采用基数树结构(radix tree structure)组织的块的位映射表(bitmap)。这有效地使交换区的分配和释放成为一个O(1)的操作。整个基数树位映射表也是预先分配的，这防止了在内存不足时的交换操作中分配新的内核内存。毕竟，在内存不足时系统将趋于使用交换区，而我们应该避免在此时分配内存，以预防出现死锁。最后，为了减少碎片，基数树适合于一次分配大的连续快，而跳过小的碎片组。我还没有完成增加分配线索指针的最后步骤，它能够让以后的分配更容易得到连续的空间，或至少保证引用的局部性，但我保证类似的修改能够完成。4.何时释放一页由于VM系统使用所有可用的内存作为磁盘缓存，因此通常很少有真正

18、空闲的页。VM系统的正常运转依赖于正确地选择没有在用的页，并为新的分配重用它们的能力。选择好的页面淘汰算法可能是VM系统中唯一的一项最重要的功能，因为如果它的选择不好，那么VM系统可能不得不再次完成从磁盘获得页的工作，这将严重降低系统性能。我们究竟希望在关键路径中承受多少开销，以防止释放掉不该释放的页?每一次错误的选择都将耗去成百上千的CPU周期，以及相关进程的可以被察觉的停顿，因此我们希望容忍大量的开销，以确保选择了正确的那页。这是为什么在内存资源承受重压时，为什么FreeBSD总趋向于提供更好的性能的主要原因。页面淘汰算法建立在过去内存页的使用历史上。为了获得这一历史资料，系统得益于绝大多

19、数硬件页表中提供的页在用位。在任何情况下，页在用位总是在VM系统在该位置位后的某一时刻被复位。它表示页仍然被活跃地使用着。如果VM系统遍历页表时页的这个位处于复位状态，则标识它没有被活跃地使用。通过周期性地检测这个位，使用历史(以计数器为形式)就能够被获得。当VM系统随后需要释放一些页时，这个历史将成为检测最佳候选页的基石。如果系统中没有页在用位怎么办?对于那些不提供这一特性的平台来说，系统实际上模拟一个页在用位。它解除映射或保护页，从而在页再次被访问时强制产生一个中断。当中断发生时，系统简单地标记页在用，并解除保护从而让页可以被使用。由于如此仅仅检测页是否在用的代价过于昂贵，因此这一技术通常

20、用来查找进程需要某一页时必须交换的页。FreeBSD使用一系列页队列，以更好地校正对页的选择，同时确认何时改过的页应被换出到备用存储器中。由于页表在FreeBSD中是动态的实体，因此，从使用页的进程中解除一页的映射没有任何代价。当候选页被通过页使用计数器选出时，这部分的工作也就完成了。系统必须区分那些干净的(clean)页和改过的(dirty)页，干净的页可以在任何时候被释放，而改过的页则必须首先写盘。当候选页被发现时，如果它被改过，则放进非活跃(inactive)队列；如果它是干净的，则直接放入缓存队列。一个基于改过和干净页比例的独立的算法决定何时非活跃队列中改过的页必须被写盘。一旦这些都完

21、成了，已经写盘的页就从非活跃队列挪到缓存队列。此时，在缓存队列中的页仍然可以通过一次VM中断以相对较低的代价重新激活。不过，在缓存队列中的页都被认为是可以马上释放的，并将按照LRU(最近最少用到)的规则在系统需要分配新的内存时被替换掉。注意，FreeBSD VM系统尝试将干净和改过的页分开这一点非常重要，原因非常简单-避免进行不需要的写入操作(这将消耗I/O带宽)，当内存子系统不承受重压时，它也不在不同的页队列之间无理由地移动页。这是为什么你在一些系统上使用systat-vm命令时看到很低的缓存队列计数和很高的活动队列计数的原因。当VM系统承受重压时，它将进行努力以维持不同的页面队列在一个被证

22、明是最有效的级别运作。一个存留了几年的神话是，Linux在防止换出方面比FreeBSD更好，然而这是错误的。实际在FreeBSD中发生的事情是，它主动地换出不用的页，以给磁盘缓存提供更多的空间，而Linux则将不用的页保留在主存中，而给缓存和进程页剩下更少的内存。当然，我并不保证今天的Linux系统依然如此。5.中断前和清零优化发生一次VM中断的代价并不一定昂贵，如果相关的页已经在主存中，那么它可以被简单地映射到进程中。然而，如果把所有的工作一次完成就不一样了。比较常见的例子是类似ls(1)或ps(1)这样的程序一遍又一遍地执行。如果程序的二进制映像被映射到内存中，而没有映射进页表，那么所有被

23、程序访问的页将在每次运行程序时引发缺页中断。当请求的页已经在VM缓存中存在时，这显然不是必需的，因此FreeBSD将尝试从VM缓存中先行组装进程的页表。目前FreeBSD还没有做到的是在exec时进行写时预复制(pre-copy-on-write)。例如，当你在执行vmstat 1时运行ls(1)程序，就会注意到它总是引发特定数量的缺页中断，即使一次又一次地执行。此外还有填零中断，而不是程序代码中断(它预先产生中断)。将在exec或fork时复制的页的情况可能更容易研究。缺页中断中的很大一部分是填零中断。通常你可以通过vmstat-s的输出观察到这一点。在进程访问BSS区域时会发生这种中断。B

24、SS区域预期被填充零，但VM系统在进程实际访问它之前并不为它分配内存。当发生中断时，VM系统不仅需要分配新的页，而且它还必须被清零。为了优化清零操作，VM系统有能力对页进行预清零，并对它们进行标记，进而在发生清零中断时直接请求这些页。预清零在CPU空闲的任何时候，只要系统中的预清零页面不足时，通过减少内存缓存来完成。这是VM系统中优化关键路径时增加复杂度的很好的例子。6.页表的优化页表优化是FreeBSD VM设计中最有争议的部分，它们看来在大量使用mmap()时过于紧张。我认为这实际上是绝大多数BSD系统的一个特性，尽管我并不十分清楚它是何时被引入的。有两项主要的优化。首先是硬件页表不包含回

25、归状态，但可以被在任何时候丢弃，而只付出很小的管理代价。然后是，系统中每一个活动页表项有一个控制的pv_entry结构附着于vm_page结构上。FreeBSD能够简单地在这些映射上迭代，而在Linux中，则必须检查所有的页表，以检查某个制定的映射是否存在；在某些情况下，Linux的算法的开销是O(n2)级的。这是因为FreeBSD在内存承受重压时，趋向于更好地选择被重用或换出的页，这让它在高负荷下有更好的性能表现。然而，FreeBSD需要进行内核调节以适应类似新闻组(news)系统中所需要的大的共享地址空间，因为这类系统可能会耗尽pv_entry结构。在这一领域，Linux和FreeBSD都

26、需要进行更多的工作。FreeBSD试图尽可能地挖掘潜在的稀疏活动映射模型(作为例子，并非所有进程都需要映射同一共享库中的所有页)，而Linux则试图最简化它的算法。FreeBSD尽管浪费了一点额外的内存，但通常具有性能上的优势。不过，FreeBSD当大量文件成捆地被许多进程映射时则会出现性能衰退。另一方面，Linux，在许多进程稀疏地映射同一个共享库时查找将被淘汰的页时也经常发生性能衰退现象。7.页的着色(Page Coloring)在文章的结尾，我们来讨论一下关于页面着色问题的优化。页面着色是一种用来确保虚拟内存中连续页的访问能够最好地利用处理器缓存的性能优化技术。在过去(大约十几年前)，处

27、理器缓存曾尝试映射虚拟内存而非物理内存。这导致了大量问题，包括在特定情况下，每次上下文切换时都必须清空缓存，以及在缓存中的数据变形问题。现代的处理器采用映射物理内存的方法来解决这些问题。这意味着同一进程地址空间中的两个挨着的页可能并不对应着缓存中的两个挨着的页。实际上，如果你不是小心地处理这类页的话，那么同一页会很快耗尽处理器的缓存，这将导致应该被缓存地数据被过早地丢弃，从而降低CPU性能。即使在多路级相联缓存中也存在这种现象(尽管它的作用有所减轻)。FreeBSD的内存分配代码实现了页作色优化，这意味着内存分配代码将试图寻找那些从缓存看来邻接的空闲页。例如，如果物理内存中的页16被指定为进程

28、虚拟内存的页0，而缓存中能够保存4页，则页着色代码将不会把物理页20分配给进程虚存页1，取而代之的是，它将把页21分配给虚存页1。页着色代码尝试避免将物理页20指定给虚存页1的原因是，映射到与物理页16相同的缓存中将导致缓存性能衰退。可以想象，这部分代码显著地提高了VM内存分配子系统的复杂度，但其结果是非常合算的。页面着色使得VM内存在缓存性能上与物理内存相差无几。8.结论在现代操作系统中，虚拟内存部分必须有效地解决相当多的问题，并适应众多的使用模式。BSD历史上采用的模型和算法手段使得我们在研究和理解现在的实现的同时，能够相对干净地替换掉大量的代码。在过去几年中，FreeBSD VM系统中有

29、相当多的改进，目前改进工作仍在进行中。9.由Allen Briggs整理的附加问题与解答单元索引暂时略去1)9.1.在你的文章所里举的FreeBSD 3.X交换区排列问题中的交错算法是什么?FreeBSD使用固定的交换区交错因子，其默认值为4。这意味着FreeBSD将保留四个交换区域，即使你只用到了1，2或3个。由于交换区在线性地址空间中交错出现4个交换区域，因此当你并不是真的拥有4个交换区的时候将产生碎片。例如，如果你有两个交换区A,B，FreeBSD将以下面的方式表达交换区中的16个页的块：A BC DA BC DA BC DA BC DFreeBSD 3.X使用一种空闲区域顺序表的方法来

30、记录空闲的交换区。主要的想法是空闲的现行空间可以被一个单独的表节点(kern/subr_rlist.c)表示。然而，由于碎片，顺序表中的碎片的产生愈演愈烈。在上述例子中，完全为用地交换区中，A和B将表示为空闲，而C与D则被标记为已经分配。每一个A-B序列需要一个表项来记录，因为C和D是空洞，因此表节点不能和下一个A-B序列合并。为什么交错地使用交换空间，而不是把一个交换区用完再用另一个呢?因为这使得分配地址空间中的线性列容易了许多，而且其结果是自动地交叉使用多个磁盘，而不是在其他地方生硬地实现这一功能。碎片同时造成了其他问题。在3.X中的线性表上，包括许多内碎片，分配和释放交换空间需要O(N)

31、的算法，而不是O(1)的算法。由于同时出现的其他因素(例如大量的交换操作)，可能会付出O(N2)甚至O(N3)级别的开销，这是非常糟糕的事情。在3.X系统中，也需要在进行交换操作以创建新的表象时，也需要分配KVM，这可能导致内存不足时的死锁。在4.X中我们不再使用顺序表。取而代之的是一个基数树和一组交换块的位映射表，而不是可延伸的表节点。预分配位映射表所需的全部内存而不是创建一组链表。使用基数树代替顺序表的结果是接近O(1)的性能，无论树上的碎片有多少。9.2.我不明白这段：注意，FreeBSD VM系统尝试将干净和改过的页分开这一点非常重要，原因非常简单-避免进行不需要的写入操作(这将消耗I

32、/O带宽)，当内存子系统不承受重压时，它也不在不同的页队列之间无理由地移动页。这是为什么你在一些系统上使用systat-vm命令时看到很低的缓存队列计数和很高的活动队列计数的原因。区分干净的和改过(非活动)的页和在systat-vm中看到的较少的缓存队列计数，以及较高的活动队列计数之间有什么关系?systat是否将活动和改过页一同作为活动队列计数?是的，这确实让人感到困惑。二者之间的关系是，理想和现实之间的关系。我们的理想是将页面分开，但实际上如果我们没有在内存上进行处理，我们实际上并不需要那样做。这意味着，在系统没有承受重压时，FreeBSD将不费很大的力气来区分出改过的(在非活动队列)和干

33、净的(在缓存队列)中的页。没有重压时，它也不尝试将活动页去活(活动队列非活动队列)，即使它们没有被用到。9.3.在ls(1)/vmstat 1例子中，难道没有一些缺页中断是数据页导致的吗(从可执行文件到私有页的写时复制)?就是说，我应认为某些缺页中断是填零或程序数据造成的。或者，你在暗示FreeBSD确实对程序数据作预先的写时复制?写时复制中断在添零或访问程序数据时都可能发生。这一机制在两种情况中是一样的，因为几乎可以肯定程序数据已经在缓存中了。FreeBSD并不预先复制程序数据或填零，但它确实预先映射那些已经在缓存中的页。9.4.在页表优化一节中，是否可以给出关于pv_entry和vm_pa

34、ge的更多细节(或者，vm_page是否和McKusick,Bostic,Karel,Quarterman的4.4,cf.pp.180-181中的vm_pmap一样)?特别地，哪种操作/反应需要扫描映射?Linux在FreeBSD出现性能衰退的情形下做什么?(在大量进程之间共享同一个大文件的映射)?vm_page表示一个(object,index#)对。pv_entry表示一个硬件页表项(pte)。如果你有5个进程分享同一个物理页，其中3个进程的页表实际地映射那一页，那么这个页将由1个vm_page结构和3个pv_entry结构表示。pv_entry结构仅仅表示由MMU映射的页(一个pv_en

35、try表示一个pte)。这意味着我们需要删除到一个vm_page的所有硬件引用(从而为某些其他，例如换出，清除，修改以及类似的目的重用该页)。可以简单地扫描关联到vm_page上的pv_entry的链表，并删除或修改相关的pte。在Linux中没有类似的链表。为了删去所有的硬件页表映射，Linux必须在每一个可能映射了该页的VM对象上进行查找。例如，如果你有50个进程映射了同一个共享库，而像要释放掉该库的页X，那么你需要遍历50各进程的页表，即使只有10个真的映射了那一页。因此，Linux实际上牺牲了性能来获取设计的简单。许多在FreeBSD上是O(1)或O(N)的VM算法在Linux上将是O

36、(N)，O(N2)甚至更差。因为pte在对象中表达特定页趋于在所有的页表中偏移量一致，减少同一pte偏移中映射的访问次数通常能够防止过快地耗尽用于它的L1缓存线，这将带来更好的性能。FreeBSD增加了复杂性(在pv_entry模式中)，以换取更好的性能(通过把对页表的访问限制在那些pte之内)。然而，FreeBSD存在一个Linux上所没有的伸缩性难题。因为pv_entry结构的个数是有限的，因此，再进行大量的共享数据时，很可能会将它们耗尽。尽管可能仍然有许多物理内存，但你可能已经把pv_entry结构用光了。这个问题可以轻易地通过提高内核配置中的pv_entry数量来做到，但我们真的很需要更好的方法来解决它。我们来考虑一下页表和pv_entry格局中的内存消耗。Linux使用永久性的页表，他们不能被释放，但却不需要为每一个潜在映射的pte分配pv_entry。FreeBSD使用可丢弃的页表，但却为每一个实际映