《Operating Systems: Three Easy Pieces》学习笔记(十六) 分页：较小的表

假设一个 32 位地址空间（232 字节）， 4KB（212 字节）的页和一个 4 字节的页表项。一个地址空间中大约有一百万个虚拟页面（232/212）。乘以页表项的大小，你会发现页表大小为4MB。回想一下：通常系统中的每个进程都有一个页表！有一百个活动进程（在现代系统中并不罕见），就要为页表分配数百兆的内存！

简单的解决方案：更大的页

再以 32 位地址空间为例，但这次假设用 16KB 的页。因此，会有 18 位的 VPN 加上 14 位的偏移量。假设每个页表项（4 字节）的大小相同，现在线性页表中有 218 个项，因此每个页表的总大小为 1MB，页表缩到四分之一。

补充：多种页大小

另外请注意，许多体系结构（例如 MIPS、SPARC、x86-64）现在都支持多种页大小。通常使用一个小的（4KB 或 8KB）页大小。但是，如果一个“聪明的”应用程序请求它，则可以为地址空间的特定部分使用一个大型页（例如，大小为 4MB），从而让这些应用程序可以将常用的（大型的）数据结构放入这样的空间，同时只占用一个 TLB 项。这种类型的大页在数据库管理系统和其他高端商业应用程序中很常见。然而，多种页面大小的主要原因并不是为了节省页表空间。这是为了减少 TLB 的压力，让程序能够访问更多的地址空间而不会遭受太多的 TLB 未命中之苦。然而，正如研究人员已经说明[N+02]一样，采用多种页大小，使操作系统虚拟内存管理程序显得更复杂，因此，有时只需向应用程序暴露一个新接口，让它们直接请求大内存页，这样最容易。

这种方法的主要问题在于，大内存页会导致每页内的浪费，这被称为内部碎片（internal fragmentation）问题（因为浪费在分配单元内部）。

混合方法：分页和分段

一个进程只使用了部分页，大部分页表都没有使用，充满了无效的（invalid）项。浪费了页表空间

分段见《Operating Systems: Three Easy Pieces》学习笔记(十二) 分段，有一个基址（base）寄存器，告诉我们每个段在物理内存中的位置，还有一个界限（bound）或限制（limit）寄存器，告诉我们该段的大小。

基址不是指向段本身，而是保存该段的页表的物理地址。界限寄存器用于指示页表的结尾（即它有多少有效页）。

假设 32 位虚拟地址空间包含 4KB 页面，并且地址空间分为 4 个段。在这个例子中，我们只使用 3 个段：一个用于代码，另一个用于堆，还有 一个用于栈。

用地址空间的前两位确定地址引用哪个段,假设 00 是未使用的段，01 是代码段，10 是堆段，11 是栈段。因此，虚拟地址如下所示：

在硬件中，假设有 3 个基本/界限对，代码、堆和栈各一个。当进程正在运行时，每个段的基址寄存器都包含该段的线性页表的物理地址。因此，系统中的每个进程现在都有 3 个与其关联的页表。在上下文切换时，必须更改这些寄存器，以反映新运行进程的页表的位置。

在 TLB 未命中时（假设硬件管理的 TLB，即硬件负责处理 TLB 未命中），硬件使用分段位（SN）来确定要用哪个基址和界限对。从基址寄存器找到页表的起始物理地址，再加上 VPN*sizeof(PTE)就是页表项(PTE)的地址，判断是否超过界限寄存器规定的界限，然后从页表项找到对应页的物理地址。(页表项就是页表线性数组中的一条记录)

SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

栈和堆之间未分配的页不再占用页表中的空间（仅将其标记为无效）。(就是分段的特性)

当然分段有的缺点不可避免，如果有一个大而稀疏的堆(堆的基址只有一个，堆内部空间的浪费避免不了)，仍然可能导致大量的页表浪费，同时外部碎片再次出现

多级页表

如何去掉页表中的所有无效区域，而不是将它们全部保留在内存中？

将线性页表变成树的形式。我们将这种方法称为多级页表（multi-level page table）

上图中左边为线性页表，页表位于物理内存的201页，由于线性页表使用索引进行查询，所以注定其必须为未使用的页也分配索引(线性索引必须连续)，导致无效信息太多，占用空间大。

上图右边为多级页表，页目录位于物理内存的200页，假设页目录中一个页能存4个页目录项（Page Directory Entries，PDE）（当然实际上一个页有4KB，能存1024个4字节的PDE）。PDE也有有效位，表示其管理的PTE至少有一个有效，此时一个PDE指向一个页，假设该页包括4个PTE；否则PDE不指向任何页。

多级页表支持稀疏空间，因为对于没有使用的页一般不分配页表。同时除了页目录需要连续外，页表存放不需要连续，通过PDE指向的方式，让我们能够将页表页分散的放在物理内存的任何地方。

在本例中，还有问题，如何定位PDE，需要用到虚拟地址 VPN 中的开头页目录索引

PDEAddr = PageDirBase +（PDIndex×sizeof（PDE））

(上述表达式也能看出稀疏也是有限制的，至少被页目录索引 PageDirBase 限制了范围)

当然比二级更多层级的页表也是允许的

多级页表是有成本的。在 TLB 未命中时，需要从内存加载两次，才能从页表中获取正确的地址转换信息（一次用于页目录，另一次用于 PTE 本身），而用线性页表只需要一次加载。因此，多级表是一个时间—空间折中（time-space trade-off）的小例子。

另一个明显的缺点是复杂性。无论是硬件还是操作系统来处理页表查找（在 TLB 未命中时），这样做无疑都比简单的线性页表查找更复杂。

反向页表

反向页表（inverted page table）

整个系统只有一个页表，其中的项代表系统的每个物理页，而不是有许多页表（系统的每个进程一个）。

页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到此物理页。通常在此基础结构上建立散列表，以加速查找。

将页表交换到磁盘

一些系统将这样的页表放入内核虚拟内存（kernel virtual memory），从而允许系统在内存压力较大时，将这些页表中的一部分交换（swap）到磁盘。

小结

在一个内存受限的系统中（像很多旧系统一样），小结构是有意义的。在具有较多内存， 并且工作负载主动使用大量内存页的系统中，用更大的页表来加速 TLB 未命中处理，可能是正确的选择。

参考

• Operating Systems: Three Easy Pieces 中文版