玻尔百科在现代计算中，将程序的逻辑虚拟地址转换为物理内存位置的能力是一项基本要求。然而，向64位架构的迁移带来了一个巨大的挑战：一个简单的、扁平的地址映射表会变得异常庞大，其消耗的内存甚至会超过大多数系统所拥有的内存。本文旨在探讨应对这一危机的优雅解决方案：分层页表。我们将剖析这种分层的“目录的目录”结构如何克服扩展性问题，以及它引入了哪些新的权衡。读者将首先在 原理与机制 部分深入了解核心概念，理解分层结构如何利用内存稀疏性，但同时引入了“页表遍历”的性能开销。随后，应用与跨学科关联 部分将揭示这一数据结构如何成为操作系统、虚拟机监视器和硬件的通用工具，支持从高效创建进程到云虚拟化的一切功能。我们将从那个迫使我们进行巧妙设计的根本问题开始。
要领会分层页表的精妙之处，我们必须首先直面它旨在解决的问题。这是一个规模问题，一个关于简单、粗暴的想法如何在天文数字的重压下崩溃，从而迫使我们进行更巧妙思考的故事。
想象一下，你计算机的内存是一座广阔无垠的城市。一个程序想要访问某段数据，它拥有一个虚拟地址——可以将其看作一个逻辑地址，比如“文学区的第三栋房子”。而计算机的硬件，即内存控制器，只理解物理地址——即房子实际建造的地块，比如“主干道123号”。操作系统和硬件的工作就是维护一张地图，即页表，它将每一个可能的逻辑地址转换为其对应的物理位置。
最简单的地图是一张巨大的单列表格。对于每一个可能的虚拟“房子”（一个页面），表中都有一个条目告诉你它的物理位置（一个页框）。这就是单级页表。在32位计算时代，这样做虽然笨拙，但尚可管理。但随后，64位计算时代到来了。
一个64位地址不仅仅是32位地址的两倍大；它是指数级的增长。可能的地址数量是 。如果我们将这个巨大的地址空间划分为标准的 KiB（ 字节）页面，我们将得到 个可能的虚拟页面。如果我们的地图中每个条目仅占用 字节，那么这张地图本身就需要 字节的存储空间。这相当于32拍字节（Petabytes）。
这并非一个理论上的担忧；这个计算表明，为一个现代64位系统配备一个单一的、扁平的页表，其消耗的内存将超过地球上最大的超级计算机所拥有的内存。我们简单的地图变成了一个怪物，一个完全不切实际的庞然大物。暴力方法失败了。我们需要一个新的思路。
这个绝妙的解决方案就是分层。我们不再使用一张覆盖全世界的单一、庞大的地图，而是创建了一个类似全球地址的目录系统。一个64位虚拟地址不再被视为一个单一的数字，而是一系列索引。
想象一下，虚拟地址是 大洲-国家-州/省-城市-街道-门牌号。要找到物理位置，你不会去查一本世界大小的电话簿。相反：
大洲部分告诉你检查哪个条目。国家部分在那个目录中查找，它又指向正确的“州/省”目录。这就是分层页表的精髓。虚拟地址被分解成多个部分。在一个典型的4级方案中，它可能看起来像：1级索引 | 2级索引 | 3级索引 | 4级索引 | 页内偏移。每个索引用于导航“目录的目录”中的一个层级。
层级数 并非任意设定。它由系统的基本参数决定：虚拟地址宽度 、页面大小 ，以及每个层级用于索引的位数 。地址转换所需的总位数是虚拟地址宽度减去页内偏移所需的位数（）。 个层级中的每一级都消耗 位，因此整个结构必须覆盖 位。这为我们提供了一个极其简洁的公式来计算所需的最小深度：
这种分层结构是一台更复杂的机器。但我们得到了什么？乍一看，我们似乎让事情变得更糟了。
如果一个程序要使用其 地址空间中的每一个字节，我们仍然需要所有位于底层的“本地城市”目录。更糟糕的是，我们还需要所有中间目录——大洲、国家和州/省——来指向它们。仔细分析表明，对于一个完全映射的地址空间，分层页表实际上比那个已经不可能实现的扁平页表消耗更多的内存，这是由于所有这些中间目录表的开销所致。
那么魔力何在？魔力在于一个简单而深刻的观察：程序是稀疏的。一个典型的应用程序并不会使用整个64位地址空间。它使用一小块区域存放其代码，另一块存放其栈，还有几块用于其堆数据。广阔、空旷的虚拟地址海洋未被触及。
在我们的类比中，这就像只需要为两个城市（比如旧金山和东京）绘制地图。我们只需要为这两个城市创建并存储本地页表。我们不需要为伦敦、开罗或悉尼分配页表。高层表中的一个指针（例如，“大洲”目录中的“欧洲”条目）可以简单地被标记为无效，表示整个区域内没有映射任何内存。这个有效-无效位是让整个方案焕发生机的简单机制。
因此，分层页表的内存占用量与进程实际使用的内存量以及其使用分布的离散程度成正比，而不是与虚拟地址空间的大小成正比。对于一个内存占用很小的程序，分层页表会非常小。相比之下，扁平页表从一开始就需要其庞大无比的完整大小。我们甚至可以精确计算出盈亏平衡点——即对于一个稀疏进程，当映射的页面数量达到某个值时，分层方案会比扁平表更节省内存。
稀疏性的重要性可以通过考虑一种病态的访问模式来看出。如果一个程序接触的512个页面彼此非常接近，它们很可能都属于同一个“城市”目录，只需要一个较低级别的页表。但如果它接触的512个页面在虚拟地址空间中相距甚远，那么每个页面可能都需要自己的“州/省”甚至“国家”目录，导致页表的内存开销激增。
这种节省空间的优雅设计并非没有代价。在物理学和计算机科学中，总是存在权衡。我们为这种分层结构付出的代价是时间。
为了加速地址转换，处理器使用一个称为转译后备缓冲器 (Translation Lookaside Buffer, TLB) 的小型、极速缓存。它就像你的短期记忆，记住你最近执行的几次转换。如果转换信息在TLB中（TLB命中），过程几乎是瞬时的。
但如果它不在那里（TLB未命中）呢？对于简单的扁平页表，一次未命中需要访问一次主内存来查找条目。而对于我们的 级分层结构，处理器必须开始一段旅程。它必须从根目录开始，逐级跟踪指针，直到找到最终的转换关系。这个多步过程被称为页表遍历。
对于一个4级页表，一次TLB未命中会迫使硬件执行四次独立的内存读取，仅仅是为了找到转换关系。之后，它才能执行第五次内存访问，以获取你最初想要的数据。这些内存访问中的每一次都需要时间和消耗能量。更深的页表（为更大的地址空间所需）意味着更长、更昂贵的页表遍历。
如果在每次TLB未命中时都进行一次漫长的页表遍历，将会对性能造成毁灭性打击。现代系统采用两种主要策略来控制这种延迟。
第一种是利用缓存。页表条目（PTE）只是存储在内存中的数据。像任何其他最近访问过的数据一样，它们会被拉入CPU的通用缓存（L1、L2、L3）中。当页表遍历开始时，硬件首先检查这些缓存。如果在那里找到了所需的PTE，就是一次缓存命中，从而避免了一次缓慢的主内存访问。
这产生了一种强大的分摊效应。当你访问一个页面时，完整的遍历可能很慢，但它会将该路径上的PTE填充到缓存中。随后对一个附近页面的访问很可能会共享相同的高层目录。它的页表遍历将在缓存中找到这些高层PTE，从而使遍历过程快得多。最初的高昂成本被分摊到了许多后续的、成本更低的操作上。因此，一次页表遍历的预期时间不仅仅是 ，而是一个更复杂的函数，取决于在各个层级、各种缓存中的命中率。
第二种策略是一种架构上的捷径：大页。如果一个程序分配了一个大的、连续的内存块，比如2MB，该怎么办？系统可以使用一个单独的大页，而不是用512个独立的4KB页面来映射这个块（这需要在最后一级表中设置512个条目）。更高层级目录条目中的一个特殊位被设置，表示：“此条目不指向下一个目录；它直接指向一个大的2MB物理页框。”
这巧妙地缩短了页表遍历。对于那2MB的区域，页表实际上浅了一到两个层级。这减少了TLB未命中时所做的工作，降低了平均内存访问时间（AMAT），并提升了性能。
从一个不可能的、拍字节大小的巨型地图的暴政中，分层原则通过利用内存使用的稀疏性为我们提供了实用的解决方案。虽然这引入了一个新的挑战——页表遍历的延迟——但这个挑战又通过缓存和像大页这样针对特定问题的巧妙捷径等通用计算机科学技术得以解决。这种解决方案的层层演进，其中每个新想法都创造了一个需要管理的新权衡，揭示了现代计算机系统设计中固有的美感和统一性。
在理解了分层页表的原理之后，我们可能会倾向于将其视为一项巧妙但枯燥的工程设计，是现代计算机管道系统中一个必要的复杂部分。但这样做就只见树木，不见森林了。这种由转换表组成的树形结构的简单而优雅的思想，不仅仅是一个实现细节；它是一个基础性的概念，其影响波及深远，塑造了从单个处理器核心的原始速度到横跨大陆的庞大云架构的一切。这个故事讲述了一个单一结构如何提供一个多功能的画布，让操作系统和虚拟机监视器在其上绘制出抽象、效率和隔离的杰作。让我们踏上一段旅程，看看这个思想如何开花结果，催生出丰富多样的应用，揭示计算机系统美妙的统一性。
在最核心的层面上，页表结构与处理器的硬件处于一种持续而复杂的互动之中。它的设计直接影响性能，工程师们已经学会了如何以惊人的技巧来运用它。
最直接、最强大的性能优化之一是使用大页（通常称为“巨页”）。想象一个程序拥有一个非常大的代码或数据段，比如一个96 MiB的科学数据集或一个大型应用程序的可执行代码。使用标准的4 KiB页面来映射它，将需要数量惊人的页表条目，更关键的是，会对转译后备缓冲器（TLB）造成巨大压力。我们的程序在运行时，会不断地从TLB中逐出旧的转换条目以便为新的腾出空间，从而导致一场TLB未命中的风暴。每次未命中都会强制进行一次耗时的页表遍历。
但请注意分层结构的精妙之处。例如，一个二级页表条目可能指向一个覆盖2 MiB区域的一级页表。如果我们能简单地说，“这个二级条目将整个2 MiB区域映射到一个连续的物理内存块”，会怎么样呢？我们可以做到！通过设置条目中的一个特殊位，我们创建了一个大页。硬件理解这个信号，并在那里停止遍历，完全绕过最后一级页表。对于我们96 MiB的区域，这个技巧可以消除数以万计的低级页表条目，从而节省内存。更重要的是，它将TLB需要缓存的不同转换数量减少了512倍。结果是TLB未命中率急剧下降，使得处理器可以将时间用于执行指令，而不是在内存中追逐指针。这不仅仅是一个理论上的技巧；它对数据库、高性能计算以及任何处理海量数据集的应用程序都是至关重要的优化。
性能的故事还在深入，直至内存层次结构的核心：CPU缓存。页表遍历本身就是一种内存访问模式。当硬件遍历一个4级页表时，它会读取四个条目。这些读取操作会经过缓存。这会污染缓存，踢出有用的应用程序数据吗？还是其中另有玄机？
让我们跟随一个顺序访问内存的流式工作负载。对于每个新页面，它都会触发一次TLB未命中和一次页表遍历。最低级别的页表条目（我们称之为一级PTE）像数据本身一样被顺序访问。但更高级别的条目行为则不同。指向一整张一级条目的二级条目，在硬件需要移动到下一个二级条目之前，将被重用512次。而三级条目在整个1 GiB区域内的每次遍历中都会被重用！这创造了美妙的时间局部性。层次结构顶层的PTE是“热点”，几乎总是驻留在L1缓存中。单次遍历所需的PTE总集合——每个级别一个——形成一个“足迹”。如果缓存足够大，能够容纳这个足迹（例如，对于四级遍历需要四个缓存行），那么高层遍历基本上是免费的，每次都能在缓存中命中。但如果缓存哪怕只小一点点，就会产生一个“悬崖效应”：足迹被破坏，每一次PTE访问都可能未命中，导致性能急剧下降。这揭示了虚拟内存系统和缓存之间一种微妙的相互作用，其中分层结构创造了其自身可预测、可重用的访问模式。
如果说分层页表是一件乐器，那么操作系统（OS）就是演奏大师。操作系统利用这种结构来履行其最基本的职责：管理内存、共享资源以及在进程间实施隔离。
思考一下共享库的奇迹。在你的计算机上，可能同时运行着数十甚至数百个进程，而几乎所有进程都使用像libc这样的标准库。难道每个进程在物理内存中都有自己私有的库代码副本吗？那将是惊人的浪费。相反，操作系统利用了分层页表带来的一个巧妙技巧。它将包含库代码的相同物理页框映射到每个进程的地址空间中。它通过共享包含库页面实际转换的低级页表来实现这一点。每个进程仍然有自己独特的顶层页目录，但它们都包含一个指向同一个共享的库中间页表的条目。这种简单的指针共享节省了大量的内存。在一个有200个进程共享一个256 MiB库的场景中，这种技术远比像单一、全局的倒排页表这样的替代结构更节省内存。
操作系统的另一个伟大幻术是写时复制（Copy-On-Write, COW）。当你用[fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman)创建一个新进程时，操作系统需要给子进程一份父进程内存的完整副本。一种天真的实现是费力地复制每一页，对于一个大进程来说这可能需要几秒钟。分层页表提供了一个更为优雅的解决方案。操作系统只为子进程复制父进程的页表，并将所有底层页面标记为只读。现在，两个进程都运行着，共享相同的物理内存。没有任何东西被物理复制。魔法发生在第一次写操作时。当任一进程试图写入一个共享页面时，只读权限会触发一个到操作系统的故障。只有在这时，操作系统才会分配一个新的物理页框，复制单个出错页面的内容，并更新出错进程的页表条目，使其指向这个新的、具有写权限的私有副本。
在现代多核系统中，这个过程揭示了虚拟内存与硬件一致性之间的深层联系。当操作系统更新那个单一的页表条目时，运行来自同一进程的线程的其他CPU核心可能在其TLB中缓存了旧的、只读的转换。为了保持一致性，操作系统必须执行一次TLB击落（TLB shootdown），向所有其他相关核心发送处理器间中断，迫使它们使陈旧的条目失效。此操作的成本与涉及的核心数量成正比，这表明一个看似简单的内存管理任务，实际上是一个微型的分布式系统问题。
在像即时（JIT）编译器或高级恶意软件使用的自修改代码这样的特殊情况下，这种对仔细同步的需求甚至更为突出。为了安全地将一个页面从可写转换为可执行，必须遵循严格的操作顺序。操作系统必须首先更新内存中的PTE，以禁止写入并允许执行。然后，也只有在那时，它才能广播TLB击落。如果它在更新PTE之前使TLB失效，就会出现一个竞态条件：另一个核心可能会遭遇TLB未命中，并从内存中重新读取旧的、仍然可写的PTE，从而缓存了错误的权限，使整个操作失效。这种精巧的编排对于维护系统的完整性至关重要。
页表结构的影响超出了单台机器和单个操作系统。它们是整个虚拟化和云计算大厦赖以建立的基石。
你如何在一个虚拟机（VM）内运行一个完整的客户机操作系统？客户机操作系统认为它拥有自己的物理内存，但这个“客户机物理地址”（GPA）空间本身就是一个由虚拟机监视器（hypervisor）映射到主机真实物理内存（HPA）的虚拟构造。早期的虚拟机监视器使用一种纯软件技术，称为影子分页，其中虚拟机监视器为每个客户机进程创建一个“影子”页表，将客户机虚拟地址（GVA）直接映射到HPA。这涉及到捕获客户机对其自身页表所做的每一次更改，这既复杂又缓慢。
现代的解决方案由CPU中的硬件支持实现，称为嵌套分页（在Intel上称为EPT，在AMD上称为NPT）。在这里，硬件能够感知到两个层次的转换。当一个GVA发生TLB未命中时，硬件开始一次“二维”的页表遍历。首先，它开始遍历客户机的页表，将GVA转换为GPA。但是，它试图读取的每个客户机页表条目的地址都是一个GPA。所以，对于客户机遍历的每一步，硬件都必须暂停，并执行第二次完整的遍历，通过虚拟机监视器的嵌套页表，将该GPA转换为HPA。一旦它获得了客户机PTE的HPA，它就可以读取它并继续进行客户机级别的遍历。在整个客户机遍历完成后，它会产生最终数据的GPA，这需要最后一次通过嵌套页表的遍历来找到其最终的HPA。
性能代价是惊人的。一次未命中TLB的数据访问可能会引发一连串的内存访问。对于一个拥有4级客户机页表和4级嵌套页表的系统，一次TLB未命中可能会在页表遍历这一项上就变成 次内存访问！。这说明了虚拟化在硬件层面的巨大性能损失，并强调了为什么高TLB命中率对虚拟化工作负载至关重要。
不同虚拟化技术之间的这种权衡并非只是学术性的；它在云计算中具有现实世界的影响。在一个多租户的云环境中，提供商希望通过在单个服务器上打包尽可能多的虚拟机来最大化密度。每个虚拟机运行着许多进程，如果使用标准的分层页表，所有这些页表所消耗的内存可能成为一个显著的开销来源，限制了服务器可以托管的租户数量。另一种选择，即倒排页表，其内存占用仅与物理RAM的数量成正比，而与进程数量无关。这就产生了一个有趣的经济权衡：对于少量租户，分层页表的开销是可以接受的。但对于一个高密度的云节点，会存在一个“盈亏平衡点”，在该点上，倒排页表的固定成本变得比成千上万个分层页表的总成本更便宜。
此外，在旧的影子分页和现代的嵌套分页之间的选择出人意料地微妙。虽然嵌套分页在处理客户机驱动的活动（如进程创建）时表现出色，无需缓慢地陷入虚拟机监视器，但当*虚拟机监视器*需要更改映射时（例如，迁移虚拟机的内存），它可能会代价高昂。这需要跨所有核心使嵌套转换失效，这是一个非常昂贵的操作。对于一个虚拟机监视器不断管理内存的工作负载，“较慢”的影子分页实际上可能胜出。这教会了我们一个深刻的系统设计教训：没有普遍的最佳方案。最优解总是依赖于工作负载。
最后，分层页表正在为下一个计算时代铺平道路：紧密集成的异构系统。现代计算机不仅仅是CPU；它们还包含强大的加速器，如图形处理单元（GPU）。几十年来，它们之间的通信一直很笨拙，需要显式的内存复制。目标一直是共享虚拟内存（Shared Virtual Memory, SVM），一个对CPU和加速器都可见的统一地址空间。
一个统一的分层页表是实现这一愿景的天然结构。由于CPU和GPU都将在同一个虚拟地址空间中操作，一致性操作（如TLB失效）自然地以虚拟页号为键。分层页表，凭借其从虚拟页到叶子PTE的一对一映射，为更新提供了一个单一、权威的节点。当一个页面从CPU内存迁移到GPU内存时，操作系统只需更新一个PTE并广播失效通知。这比使用按物理位置组织的倒排页表要直接得多，后者会使这些基于虚拟地址的一致性操作复杂化。随着CPU和加速器变得越来越强大和紧密耦合，对这种统一页表结构的需求将是巨大的，两个设备上的页表遍历器将产生大量的内存流量，以保持其TLB的供给。
从一个简单的指针树开始，我们已经穿越了处理器微架构、操作系统设计、云基础设施以及异构计算的未来。分层页表不仅仅是一个问题的解决方案；它是一个基本的构建模块，一个多功能且优雅的概念，其应用既深且广，证明了计算系统设计中固有的美感和统一性。