内存虚拟化-分页type
status
date
slug
summary
tags
category
icon
password
Property
操作系统有两种方法，来解决大多数空间管理问题
- 第一种是将空间分割成不同长度的分片，就像虚拟内存管理中的分段。遗憾的是，这个解决方法存在固有的问题。将空间切成不同长度的分片以后，空间本身会碎片化，随着时间推移，分配内存会变得比较困难。
- 因此，值得考虑第二种方法：将空间分割成固定长度的分片。在虚拟内存中，称这种思想为分页，可以追溯到一个早期的重要系统，Atlas。分页不是将一个进程的地址空间分割成几个不同长度的逻辑段（即代码、堆、段），而是分割成固定大小的单元，每个单元称为一页。相应地，把物理内存看成是定长槽块的阵列，叫作页帧（pageframe）。每个这样的页帧包含一个虚拟内存页。
下图展示了一个只有64字节的小地址空间，有4 个16 字节的页（虚拟页0、1、2、3）。物理内存，也由一组固定大小的槽块组成：
虚拟地址空间的页放在物理内存的不同位置。
分页最大的改进就是灵活性：通过完善的分页方法，操作系统能够高效地提供地址空间的抽象，不管进程如何使用地址空间。例如，我们不会假定堆和栈的增长方向，以及它们如何使用。
另一个优点是分页提供的空闲空间管理的简单性。例如，如果操作系统希望将64 字节的小地址空间放到8页的物理地址空间中，它只要找到4个空闲页。也许操作系统保存了一个所有空闲页的空闲列表（free list），只需要从这个列表中拿出4 个空闲页。
操作系统将地址空间的虚拟页0放在物理页帧3，虚拟页1放在物理页帧7，虚拟页2放在物理页帧5，虚拟页3 =放在物理页帧2。页帧1、4、6 目前是空闲的。
为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表（page table）。页表的主要作用是为地址空间的每个虚拟页面保存地址转换，从而让我们知道每个页在物理内存中的位置。对于示例，页表具有以下4 个条目：（虚拟页0→物理帧3）、（VP 1→PF 7）、（VP 2→PF 5）和（VP 3→PF 2）。
页表是一个每进程的数据结构（一个例外是倒排页表，inverted page table）。如果在上面的示例中运行另一个进程，操作系统将不得不为它管理不同的页表，因为它的虚拟页显然映射到不同的物理页面（除了共享之外）。
设想拥有这个小地址空间（64 字节）的进程正在访问内存：
为了转换（translate）该过程生成的虚拟地址，必须首先将它分成两个组件：虚拟页面号（virtual page number，VPN）和页内的偏移量（offset）。对于这个例子，因为进程的虚拟地址空间是64 字节，虚拟地址总共需要6位（ ）。因此，虚拟地址可以表示如下：
因为我们知道页的大小（16 字节），所以可以进一步划分虚拟地址：
页面大小为16 字节，位于64 字节的地址空间。因此需要能够选择4 个页，地址的前2位就是做这件事的，因此有一个2位的虚拟页号（VPN）。其余的位告诉我们，感兴趣该页的哪个字节，在这个例子中是4 位，称之为偏移量。
假设加载是虚拟地址21，二进制形式是“010101”，分解成虚拟页号（VPN）和偏移量：
虚拟地址“21”在虚拟页“01”（或1）的第5 个（“0101”）字节处。通过虚拟页号，可以检索页表，找到虚拟页1 所在的物理页面。在上面的页表中，物理帧号（PFN）（物理页号，physical page number 或PPN）是7（二进制111）。因此，可以通过用PFN 替换VPN 来转换此虚拟地址，然后将载入发送给物理内存：
页表存在哪里?
页表可以变得非常大。例如，想一个典型的32 位地址空间，带有4KB 的页。这个虚拟地址分成20位的VPN 和12位的偏移量（1KB 的页面大小需要10 位，只需增加两位即可达到4KB）。
一个20 位的VPN 意味着，操作系统必须为每个进程管理 个地址转换（大约一百万）。假设每个页表格条目（PTE）需要4个字节，来保存物理地址转换和任何其他有用的东西，每个页表就需要巨大的4MB 内存！这非常大。现在想象一下有100 个进程在运行：这意味着操作系统会需要400MB 内存，只是为了所有这些地址转换！
由于页表如此之大，没有在MMU 中利用任何特殊的片上硬件，来存储当前正在运行的进程的页表，而是将每个进程的页表存储在内存中。
页表中究竟有什么?
页表就是一种数据结构，用于将虚拟地址（实际上，是虚拟页号）映射到物理地址（物理帧号）。因此，任何数据结构都可以采用。最简单的形式称为线性页表（linear page table），就是一个数组。操作系统通过虚拟页号（VPN）检索该数组，并在该索引处查找页表项（PTE），以便找到期望的物理帧号（PFN）。现在，假设采用这个简单的线性结构。
每个PTE 其中有许多不同的位，有效位（valid bit）通常用于指示特定地址转换是否有效。例如，当一个程序开始运行时，它的代码和堆在其地址空间的一端，栈在另一端。所有未使用的中间空间都将被标记为无效（invalid），如果进程尝试访问这种内存，就会陷入操作系统，可能会导致该进程终止。因此，有效位对于支持稀疏地址空间至关重要。通过简单地将地址空间中所有未使用的页面标记为无效，不再需要为这些页面分配物理帧，从而节省大量内存。
还可能有保护位（protection bit），表明页是否可以读取、写入或执行。同样，以这些位不允许的方式访问页，会陷入操作系统。
还有其他一些重要的部分，存在位（present bit）表示该页是在物理存储器还是在磁盘上（即它已被换出，swapped out）。交换允许操作系统将很少使用的页面移到磁盘，从而释放物理内存。脏位（dirty bit）也很常见，表明页面被带入内存后是否被修过。
参考位（reference bit，也被称为访问位，accessed bit）有时用于追踪页是否被访问，也用于确定哪些页很受欢迎，因此应该保留在内存中。这些知识在页面替换（page replacement）时非常重要。
图显示了来自x86 架构的示例页表项。它包含一个存在位（P），确定是否允许写入该页面的读/写位（R/W） 确定用户模式进程是否可以访问该页面的用户/超级用户位（U/S），有几位（PWT、PCD、PAT 和G）确定硬件缓存如何为这些页面工作，一个访问位（A）和一个脏位（D），最后是页帧号（PFN）本身。
分页：也很慢
以简单的指令为例：
假定硬件执行地址转换。要获取所需数据，系统必须首先将虚拟地址（21）转换为正确的物理地址（117）。因此，在从地址117 获取数据之前，系统必须首先从进程的页表中提取适当的页表项，执行转换，然后从物理内存中加载数据。
为此，硬件必须知道当前正在运行的进程的页表的位置。假设一个页表基址寄存器（page-table base register）包含页表的起始位置的物理地址。为了找到想要的PTE的位置，硬件将执行以下功能：
一旦知道了这个物理地址，硬件就可以从内存中获取PTE，提取PFN，并将它与来自虚拟地址的偏移量连接起来，形成所需的物理地址。具体来说，PFN 被SHIFT左移，然后与偏移量进行逻辑或运算，以形成最终地址
最后，硬件可以从内存中获取所需的数据并将其放入寄存器eax。程序现在已成功从内存中加载了一个值！
对于每个内存引用（无论是取指令还是显式加载或存储），分页都需要我们执行一个额外的内存引用，以便首先从页表中获取地址转换。工作量很大！额外的内存引用开销很大，在这种情况下，可能会使进程减慢两倍或更多。
如果不仔细设计硬件和软件，页表会导致系统运行速度过慢，并占用太多内存。
分页：快速地址转换（TLB）
使用分页作为核心机制来实现虚拟内存，可能会带来较高的性能开销。因为要使用分页，就要将内存地址空间切分成大量固定大小的单元（页），并且需要记录这些单元的地址映射信息。因为这些映射信息一般存储在物理内存中，所以在转换虚拟地址时，分页逻辑上需要一次额外的内存访问。每次指令获取、显式加载或保存，都要额外读一次内存以得到转换信息，这慢得无法接受
如何才能加速虚拟地址转换，尽量避免额外的内存访问？需要什么样的硬件支持？操作系统该如何支持？
想让某些东西更快，操作系统通常需要一些帮助。帮助常常来自操作系统的老朋友：硬件。增加所谓的地址转换旁路缓冲存储器（translation-lookaside buffer，TLB），它就是频繁发生的虚拟到物理地址转换的硬件缓存（cache）。因此，更好的名称应该是地址转换缓存（address-translation cache）。对每次内存访问，硬件先检查TLB，看看其中是否有期望的转换映射，如果有，就完成转换（很快），不用访问页表（其中有全部的转换映射）。TLB 带来了巨大的性能提升，实际上，因此它使得虚拟内存成为可能。
TLB 的基本算法
TLB 和其他缓存相似，前提是在一般情况下，转换映射会在缓存中（命中）。如果是这样，只增加了很少的开销，因为TLB 处理器核心附近，设计的访问速度很快。如果TLB未命中，就会带来很大的分页开销。必须访问页表来查找转换映射，导致一次额外的内存引用（或者更多，如果页表更复杂）。如果这经常发生，程序的运行就会显著变慢。相对于大多数CPU 指令，内存访问开销很大，TLB 未命中导致更多内存访问。因此，希望尽可能避免TLB 未命中。
假设有一个由10 个4字节整型数组成的数组，起始虚地址是100。进一步假定，有一个8位的小虚地址空间，页大小为16B。可以把虚地址划分为4 位的VPN（有16 个虚拟内存页）和4位的偏移量（每个页中有16个字节）。
在系统的16 个16 字节的页上。数组的第一项（
a[0]）开始于（VPN=06，offset=04）。当访问第一个数组元素（
a[0]）时，CPU 会看到载入虚存地址100。硬件从中提取VPN（VPN=06），然后用它来检查TLB，寻找有效的转换映射。假设这里是程序第一次访问该数组，结果是TLB 未命中。接下来访问
a[1]，TLB 命中！因为数组的第二个元素在第一个元素之后，它们在同一页。因为之前已经访问了这一页，所以TLB中缓存了该页的转换映射。因此成功命中。访问a[2]同样成功。遗憾的是，当程序访问a[3]时，会导致TLB 未命中。但同样，接下来几项（a[4] … a[6]）都会命中TLB，因为它们位于内存中的同一页。这10次数组访问操作中TLB 的行为表现：未命中、命中、命中、未命中········。命中的次数除以总的访问次数，TLB命中率（hit rate）为70%。即使这是程序首次访问该数组，但得益于空间局部性（spatial locality），TLB 还是提高了性能。
也要注意页大小对本例结果的影响。如果页大小变大一倍（32 字节，而不是16），数组访问遇到的未命中更少。典型页的大小一般为4KB，这种情况下，密集的、基于数组的访问会实现极好的TLB 性能，每页的访问只会遇到一次未命中。
如果在这次循环后不久，该程序再次访问该数组，会看到更好的结果，假设TLB 足够大，能缓存所需的转换映射：命中、····。在这种情况下，由于时间局部性（temporal locality），即在短时间内对内存项再次引用，所以TLB 的命中率会很高。类似其他缓存，TLB 的成功依赖于空间和时间局部性。如果某个程序表现出这样的局部性（许多程序是这样），TLB 的命中率可能很高。
谁来处理TLB 未命中？ 硬件或软件（操作系统）
以前的硬件有复杂的指令集（复杂指令集计算机，Complex-Instruction Set Computer，CISC），造硬件的人不太相信那些搞操作系统的人。因此，硬件全权处理TLB未命中。为了做到这一点，硬件必须知道页表在内存中的确切位置（通过页表基址寄存器，
page-table base register），以及页表的确切格式。发生未命中时，硬件会“遍历”页表，找到正确的页表项，取出想要的转换映射，用它更新TLB，并重试该指令。这种“旧”体系结构有硬件管理的TLB，一个例子是x86 架构，它采用固定的多级页表（multi-level page table），当前页表由CR3 寄存器指出。
更现代的体系结构（如，MIPS R10k、Sun 公司的SPARC v9，都是精简指令集计算机，Reduced-Instruction Set Computer，RISC），有所谓的软件管理TLB（softwaremanaged TLB）。发生TLB 未命中时，硬件系统会抛出一个异常，这会暂停当前的指令流，将特权级提升至内核模式，跳转至陷阱处理程序（trap handler）。这个陷阱处理程序是操作系统的一段代码，用于处理TLB 未命中。这段代码在运行时，会查找页表中的转换映射，然后用特别的“特权”指令更新TLB，并从陷阱返回。此时，硬件会重试该指令（导致TLB 命中）。
TLB 控制流算法（操作系统处理）：
从陷阱返回指令稍稍不同于之前提到的服务于系统调用的从陷阱返回：
- 在后一种情况下，从陷阱返回应该继续执行陷入操作系统之后那条指令，就像从函数调用返回后，会继续执行此次调用之后的语句
- 在前一种情况下，在从TLB 未命中的陷阱返回后，硬件必须从导致陷阱的指令继续执行。这次重试因此导致该指令再次执行，但这次会命中TLB。因此，根据陷阱或异常的原因，系统在陷入内核时必须保存不同的程序计数器，以便将来能够正确地继续执行
在运行TLB 未命中处理代码时，操作系统需要格外小心避免引起TLB未命中的无限递归。有很多解决方案，例如，可以把TLB 未命中陷阱处理程序直接放到物理内存中 [它们没有映射过（unmapped），不用经过地址转换]。或者在TLB 中保留一些项，记录永久有
效的地址转换，并将其中一些永久地址转换槽块留给处理代码本身，这些被监听的（wired）地址转换总是会命中TLB。
软件管理的方法，主要优势是灵活性：操作系统可以用任意数据结构来实现页表，不需要改变硬件。另一个优势是简单性。从TLB 控制流中可以看出，硬件不需要对未命中做太多工作，它抛出异常，操作系统的未命中处理程序会负责剩下的工作。
TLB 的内容
典型的TLB 有32 项、64 项或128 项，并且是全相联的（fully associative）。基本上，这就意味着一条地址映射可能存在TLB 中的任意位置，硬件会并行地查找TLB，找到期望的转换映射。一条TLB 项内容可能像这样：
VPN ｜ PFN ｜ 其他位
VPN 和PFN 同时存在于TLB 中，因为一条地址映射可能出现在任意位置（TLB 被称为全相联的（fully-associative）缓存）。硬件并行地查找这些项，看看是否有匹配。
TLB 通常有一个有效（valid）位，用来标识该项是不是有效地转换映射。通常还有一些保护（protection）位，用来标识该页是否有访问权限。例如，代码页被标识为可读和可执行，而堆的页被标识为可读和可写。还有其他一些位，包括地址空间标识符（address-space identifier）、脏位（dirty bit）等。
注：TLB 的有效位!=页表的有效位
在页表中，如果一个页表项（PTE）被标记为无效，就意味着该页并没有被进程申请使用，正常运行的程序不应该访问该地址。当程序试图访问这样的页时，就会陷入操作系统，操作系统会杀掉该进程。
TLB 的有效位不同，只是指出TLB 项是不是有效的地址映射。例如，系统启动时，所有的TLB 项通常被初始化为无效状态，因为还没有地址转换映射被缓存在这里。一旦启用虚拟内存，当程序开始运行，访问自己的虚拟地址，TLB 就会慢慢地被填满，因此有效的项很快会充满TLB。通过将所有TLB项设置为无效，系统可以确保将要运行的进程不会错误地使用前一个进程的虚拟到物理地址转换映射。
上下文切换时对TLB 的处理
TLB 中包含的虚拟到物理的地址映射只对当前进程有效，对其他进程是没有意义的。所以在发生进程切换时，硬件或操作系统（或二者）必须注意确保即将运行的进程不要误读了之前进程的地址映射。
例子：当进程（P1）正在运行时，假设TLB 缓存了对它有效的地址映射，即来自P1 的页表。假设P1 的10号虚拟页映射到了100 号物理帧。假设还有一个进程（P2），操作系统不久后决定进行一次上下文切换，运行P2。这里假定P2 的10号虚拟页映射到170号物理帧。如果这两个进程的地址映射都在TLB 中，TLB 的内容如表所示。
VPN 10 被转换成了 PFN 100（P1）和PFN 170（P2），但硬件分不清哪个项属于哪个进程。所以还需要做一些工作，让TLB 正确而高效地支持跨多进程的虚拟化。因此，关键问题是：如果发生进程间上下文切换，上一个进程在TLB 中的地址映射对于即将运行的进程是无意义的。硬件或操作系统应该做些什么来解决这个问题呢？
一种方法是在上下文切换时，简单地清空（flush）TLB，这样在新进程运行前TLB 就变成了空的。如果是软件管理TLB 的系统，可以在发生上下文切换时，通过一条显式（特权）指令来完成。如果是硬件管理TLB，则可以在页表基址寄存器内容发生变化时清空TLB（注意，在上下文切换时，操作系统必须改变页表基址寄存器（PTBR）的值）。不论哪种情况，清空操作都是把全部有效位置为0，本质上清空了TLB。
上下文切换的时候清空TLB，有一定开销：每次进程运行，当它访问数据和代码页时，都会触发TLB 未命中。如果操作系统频繁地切换进程，这种开销会很高。为了减少这种开销，一些系统增加了硬件支持，实现跨上下文切换的TLB 共享。比如有的系统在TLB 中添加了一个地址空间标识符（Address Space Identifier，ASID）。可以把ASID 看作是进程标识符（Process Identifier，PID），但通常比PID 位数少（PID 一般32 位，ASID 一般是8 位）。
加上 ASID，很清楚不同进程可以共享TLB 了：只要ASID字段来区分原来无法区分的地址映射。
因此，有了地址空间标识符，TLB 可以同时缓存不同进程的地址空间映射，没有任何冲突。当然，硬件也需要知道当前是哪个进程正在运行，以便进行地址转换，因此操作系统在上下文切换时，必须将某个特权寄存器设置为当前进程的ASID。
TLB 替换策略
向TLB 中插入新项时，会替换一个旧项，这样问题就来了：应该替换那一个？
策略 | 解释 | 演化 | 缺点 |
MIN/OPT最优替换策略 | 替换掉最远的将来才会访问的项目 | 只是一个假设 | 无法决定哪个页在最远的将来才会访问，实际上根本无法实现 |
FIFO | 替换掉最先进入的项目 | 直觉策略 | 缓存容量非常影响命中率，因为存在抖动（thrashing）现象 |
随机 | 随机替换掉一个项目 | 直觉策略 | 命中率也很随机 |
LRU(最近最少使用) | 替换掉最长时间没有被使用的项目（使用一个计数器，每次访问项目计数器加1，替换时替换计数器值最低的项目） | 考虑时间局部性 | 实现成本高，因为每次访问都要更改计数器 |
Approximating LRU（近似LRU） | 将被访问的项目做标记（例如将页表项中的accessed bit置1），定期（例如每100ms）清除所有标记（accessed bit置0），替换掉首个没有标记的项目 | 降低实现成本 | 清理标记的周期参数影响命中率 （但仍为主流实现） |
考虑脏页的近似LRU(适用于交换) | 在LRU的基础上优先选择干净的（即没有被修改过的）页来替换，修改过的页写回磁盘需要额外开销 | 考虑IO开销 | 与近似LRU类似 |
分页：较小的表
假设一个32 位地址空间（ 字节），4KB（ 字节）的页和一个4 字节的页表项。一个地址空间中大约有一百万个虚拟页面
（ ）。乘以页表项的大小，发现页表大小为4MB。
简单的基于数组的页表（通常称为线性页表）太大，在典型系统上占用太多内存。如何让页表更小？
简单的解决方案：更大的页
可以用一种简单的方法减小页表大小：使用更大的页。以32 位地址空间为例，假设用16KB 的页。因此，会有18位的VPN 加上14位的偏移量。假设每个页表项（4字节）的大小相同，现在线性页表中有 个项，每个页表的总大小为1MB，页表缩到四分之一。
这种方法的主要问题在于，大内存页会导致每页内的浪费，这被称为内部碎片问题（因为浪费在分配单元内部）。因此，结果是应用程序会分配页，但只用每页的一小部分，而内存很快就会充满这些过大的页。因此，大多数系统在常见的情况下使用相对较小的页大小：4KB（如x86）或8KB（如SPARCv9）。
混合方法：分页和分段
将分页和分段相结合，减少页表的内存开销。
假设有一个地址空间，其中堆和栈的使用部分很小。例如，使用一个16KB 的小地址空间和1KB 的页。
假定单个代码页（VPN 0）映射到物理页10，单个堆页（VPN 4）映射到物理页23，以及地址空间另一端的两个栈页（VPN 14 和15）被分别映射到物理页28 和4。从图可以看到，大部分页表都没有使用，充满了无效的（invalid）项。太浪费了！
因此，杂合方法不是为进程的整个地址空间提供单个页表，而是为每个逻辑分段提供一个。
分段中，有一个基址寄存器，表示每个段在物理内存中的位置，还有一个界限寄存器，表示该段的大小。在杂合方案中，仍然在MMU 中拥有这些结构。在这里，使用基址不是指向段本身，而是保存该段的页表的物理地址。界限寄存器用于指示页表的结尾（即它有多少有效页）。
假设32 位虚拟地址空间包含4KB 页面，并且地址空间分为 4 个段。在这个例子中，使用 3 个段：一个用于代码，另一个用于堆，还有一个用于栈。要确定地址引用哪个段，用地址空间的前两位。假设00 是未使用的段，01 是代码段，10 是堆段，11 是栈段。因此，虚拟地址如下所示：
在硬件中，假设有3 个基本/界限对，代码、堆和栈各一个。当进程正在运行时，每个段的基址寄存器都包含该段的线性页表的物理地址。因此，系统中的每个进程现在都有3个与其关联的页表。在上下文切换时，必须更改这些寄存器，以反映新运行进程的页表的位置。
在TLB 未命中时（假设硬件管理的TLB，即硬件负责处理TLB 未命中），硬件使用分段位（SN）来确定要用哪个基址和界限对。然后硬件将其中的物理地址与VPN 结合起来，形成页表项（PTE）的地址：
杂合方案的关键区别在于，每个分段都有界限寄存器，每个界限寄存器保存了段中最大有效页的值。例如，如果代码段使用它的前3 个页（0、1 和2），则代码段页表将只有3个项分配给它，并且界限寄存器将被设置为3。内存访问超出段的末尾将产生一个异常，并可能导致进程终止。以这种方式，与线性页表相比，杂合方法实现了显著的内存节省。栈和堆之间未分配的页不再占用页表中的空间（仅将其标记为无效）。
但是，这种方法并非没有问题。首先，它仍然要求使用分段。分段并不像我们需要的那样灵活，因为它假定地址空间有一定的使用模式。例如，如果有一个大而稀疏的堆，仍然可能导致大量的页表浪费。其次，这种杂合导致外部碎片再次出现。尽管大部分内存是以页面大小单位管理的，但页表现在可以是任意大小（是PTE 的倍数）。因此，在内存中为它们寻找自由空间更为复杂。
多级页表
多级页表的基本思想很简单。首先，将页表分成页大小的单元。然后，如果整页的页表项（PTE）无效，就完全不分配该页的页表。为了追踪页表的页是否有效（以及如果有效，它在内存中的位置），使用了名为页目录（page directory）的新结构。页目录因此可以告诉你页表的页在哪里，或者页表的整个页不包含有效页。
图的左边是经典的线性页表。即使地址空间的大部分中间区域无效，仍然需要为这些区域分配页表空间（即页表的中间两页）。右侧是一个多级页表。页目录仅将页表的两页标记为有效（第一个和最后一个）；因此，页表的这两页就驻留在内存中。因此，多级页表的工作方式：它只是让线性页表的一部分消失（释放这些帧用于其他用途），并用页目录来记录页表的哪些页被分配。
在一个简单的两级页表中，页目录为每页页表包含了一项。它由多个页目录项（Page Directory Entries，PDE）组成。PDE（至少）拥有有效位（valid bit）和页帧号（page frame number，PFN），类似于PTE。但是，正如上面所暗示的，这个有效位的含义稍有不同：如果PDE 项是有效的，则意味着该项指向的页表（通过PFN）中至少有一页是有效的，即在该PDE 所指向的页中，至少一个PTE，其有效位被设置为1。如果PDE 项无效（即等于零），则PDE的其余部分没有定义。
多级页表有一些明显的优势。首先，多级页表分配的页表空间，与正在使用的地址空间内存量成比例。因此它通常很紧凑，并且支持稀疏的地址空间。
其次，如果仔细构建，页表的每个部分都可以整齐地放入一页中，从而更容易管理内存。操作系统可以在需要分配或增长页表时简单地获取下一个空闲页。将它与一个简单的（非分页）线性页表相比，后者仅是按VPN 索引的PTE 数组。用这样的结构，整个线性页表必须连续驻留在物理内存中。对于一个大的页表（比如4MB），找到如此大量的、未使用的连续空闲物理内存，可能是一个相当大的挑战。有了多级结构，我们增加了一个间接层（level of indirection），使用了页目录，它指向页表的各个部分。这种间接方式，让我们能够将页表页放在物理内存的任何地方。
多级页表是有成本的。在TLB 未命中时，需要从内存加载两次，才能从页表中获取正确的地址转换信息（一次用于页目录，另一次用于PTE 本身），而用线性页表只需要一次加载。因此，多级表是一个时间—空间折中（time-space trade-off）的小例子。尽管在常见情况下（TLB 命中），性能显然是相同的，但TLB 未命中时，则会因较小的表而导致较高的成本。
另一个明显的缺点是复杂性。无论是硬件还是操作系统来处理页表查找（在TLB 未命中时），这样做无疑都比简单的线性页表查找更复杂。通常我们愿意增加复杂性以提高性能或降低管理费用。在多级表的情况下，为了节省宝贵的内存，我们使页表查找更加复杂。
设想一个大小为16KB 的小地址空间，其中包含64 个字节的页。因此，有一个14 位的虚拟地址空间，VPN 有8位，偏移量有6 位。即使只有一小部分地址空间正在使用，线性页表也会有 （256）个项。
虚拟页0 和1用于代码，虚拟页4 和5用于堆，虚拟页254 和255 用于栈。地址空间的其余页未被使用。
要为这个地址空间构建一个两级页表，从完整的线性页表开始，将它分解成页大小的单元。假设每个PTE 的大小是4个字节。因此，页大小为1KB（256×4 字节）。鉴于我们有64 字节的页，1KB 页表可以分为16 个64 字节的页，每个页可以容纳16 个PTE。
首先索引到页目录。这个例子中的页表很小：256 个项，分布在16 个页上。页目录需要为页表的每页提供一个项。因此，它有16 个项。结果，需要4 位VPN 来索引目录。
一旦从VPN 中提取了页目录索引（简称PDIndex），就可以通过简单的计算来找到页目录项（PDE）的地址：PDEAddr = PageDirBase +（PDIndex×sizeof（PDE））。这就得到了页目录，现在我们来看它，在地址转换上取得进一步进展。
如果页目录项标记为无效，访问无效，从而引发异常。但是，如果PDE 有效，我们还有更多工作要做。具体来说现在必须从页目录项指向的页表的页中获取页表项（PTE）。要找到这个PTE，必须使用VPN 的剩余位索引到页表的部分：
这个页表索引（Page-Table Index，PTIndex）可以用来索引页表本身，给出PTE 的地址：
代入一个包含一些实际值的多级页表，并转换一个虚拟地址。
在该表中，可以看到每个页目录项（PDE）都描述了有关地址空间页表的一些内容。在这个例子中，地址空间里有两个有效区域（在开始和结束处），以及一些无效的映射。在物理页100（页表的第0 页的物理帧号）中，我们有1 页，包含16 个页表项，记录
了地址空间中的前16 个VPN。
VPN 0 和1 是有效的（代码段），4 和5（堆）也是。因此，该表有每个页的映射信息。其余项标记为无效。页表的另一个有效页在PFN 101 中。该页包含地址空间的最后16 个VPN 的映射。
在这个例子中，VPN 254 和255（栈）包含有效的映射。在这个例子中，我们不是为一个线性页表分配完整的16页，而是分配3 页：一个用于页目录，两个用于页表的具有有效映射的块。大型（32 位或64 位）地址空间的节省显然要大得多。
用这些信息来进行地址转换。这里是一个地址，指向VPN 254 的第0 个字节：0x3F80，或二进制的11 1111 1000 0000。
我们将使用VPN 的前4 位来索引页目录。因此，1111 会从上面的页目录中选择最后一个（第15 个，如果你从第0 个开始）。这就指向了位于地址101 的页表的有效页。然后，使用VPN 的下4 位（1110）来索引页表的那一页并找到所需的PTE。1110 是页面中的倒数第二（第14 个）条，并告诉我们虚拟地址空间的页254 映射到物理页55。通过连接PFN = 55（或十六进制0x37）和offset = 000000，可以形成我们想要的物理地址，并向内存系统发出请求：PhysAddr =（PTE.PFN << SHIFT）+ offset = 00 1101 1100 0000 = 0x0DC0。
超过两级
假设我们有一个30 位的虚拟地址空间和一个小的（512 字节）页。因此我们的虚拟地址有一个21 位的虚拟页号和一个9 位偏移量。
构建多级页表的目标：使页表的每一部分都能放入一个页。到目前为止，只考虑了页表本身。但是，如果页目录太大，该怎么办？
要确定多级表中需要多少级别才能使页表的所有部分都能放入一页，首先要确定多少页表项可以放入一页。鉴于页大小为512 字节，并且假设PTE 大小为4 字节，可以在单个页上放入128 个PTE。当索引页表时，可以得出结论，需要VPN的最低有效位7 位（ ）作为索引：
多少位留给了（大）页目录：14。如果我们的页目录有 个项，那么它不是一个页，而是128 个，因此我们让多级页表的每一个部分放入一页目标失败了。
为了解决这个问题，我们为树再加一层，将页目录本身拆成多个页，然后在其上添加另一个页目录，指向页目录的页。可以按如下方式分割虚拟地址：
现在，当索引上层页目录时，使用虚拟地址的最高几位（图中的PD 索引0）。该索引用于从顶级页目录中获取页目录项。如果有效，则通过组合来自顶级PDE 的物理帧号和VPN 的下一部分（PD 索引1）来查阅页目录的第二级。最后，如果有效，则可以通过使用与第二级PDE 的地址组合的页表索引来形成PTE 地址。这会有很多工作。所有这些只是为了在多级页表中查找某些东西。
地址转换过程：记住TLB
在任何复杂的多级页表访问发生之前，硬件首先检查TLB。在命中时，物理地址直接形成，而不像之前一样访问页表。只有在TLB 未命中时，硬件才需要执行完整的多级查找。在这条路径上，可以看到传统的两级页表的成本：两次额外的内存访问来查找有效的转换映射。
反向页表
在反向页表（inverted page table）中，可以看到页表世界中更极端的空间节省。在这里，保留了一个页表，其中的项代表系统的每个物理页，而不是有许多页表（系统的每个进程一个）。页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到此物理页。
现在，要找到正确的项，就是要搜索这个数据结构。线性扫描是昂贵的，因此通常在此基础结构上建立散列表，以加速查找。PowerPC 就是这种架构[JM98]的一个例子。更一般地说，反向页表说明了：页表只是数据结构。可以对数据结构做很多疯狂的事情，让它们更小或更大，使它们变得更慢或更快。