第 20 章 分页：较小的表

第 20 章 分页：较小的表

分页面临的第二个挑战是：页表过大，导致内存消耗过多。

以 32 位地址空间（$2^{32}$ 字节）、4KB（$2^{12}$ 字节）页大小和 4 字节页表项（PTE）为例：

• 每个进程的虚拟页面数约为 100 万个（$2^{32}/2^{12}$）。
• 单个页表大小为 4MB。
• 若系统中有 100 个活跃进程，页表将占用数百兆内存。

如何让页表更小？

线性页表（基于数组）在典型系统上占用太多内存。如何减小页表大小？其核心思路是什么？引入新的数据结构后，会对效率产生什么影响？

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

减小页表大小的一种直观方法是增加页的大小。

以 32 位地址空间为例，若将页大小从 4KB 增加到 16KB（$2^{14}$ 字节）：

• VPN 位数：从 20 位降至 18 位。
• 页表项数量：减少至 $2^{18}$ 个。
• 页表大小：在 PTE 大小不变的情况下，总大小降至 1MB（缩减为原来的 1/4）。

多种页大小（Huge Pages）

许多架构（如 x86-64）支持多种页大小。大页（如 4MB）常用于数据库等高性能应用，其主要目的并非节省页表空间，而是减少 TLB 压力，提高 TLB 命中率。但引入多种页大小会增加 OS 虚拟内存管理的复杂性。

主要缺陷：内部碎片（Internal Fragmentation） 大页会导致分配单元内部的浪费。应用程序可能只使用大页的一小部分，导致内存迅速被填满。因此，大多数系统仍采用较小的页大小（如 4KB 或 8KB）。

混合方法：分页和分段

为了减少线性页表的内存开销，可以将分页与分段相结合。

核心动机：消除无效项的浪费

在线性页表中，如果地址空间是稀疏的（例如堆和栈之间有巨大的空隙），页表中会充斥着大量无效（invalid）的项，造成极大的内存浪费。

PFN	valid	prot	present	dirty
10	1	r-x	1	0
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
23	1	rw-	1	1
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
—	0	—	—	—
28	1	rw-	1	1
4	1	rw-	1	1

实现机制

不再为整个地址空间维护一个大页表，而是为每个逻辑段（代码、堆、栈）分别提供一个页表。

• 基址（Base）寄存器：不再指向段本身，而是存放该段页表的物理地址。
• 界限（Bound）寄存器：用于指示页表的末尾（即该段有多少个有效页）。

地址转换流程

虚拟地址的前两位（SN）用于标识段，其余位用于 VPN。

在 TLB 未命中时，硬件根据 SN 获取对应的基址和界限，计算 PTE 地址：

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

优缺点分析

• 优点：显著节省内存。堆和栈之间未分配的区域不再占用页表空间。
• 缺点：
  • 灵活性受限：仍受分段限制，若存在大而稀疏的堆，页表依然会很大。
  • 外部碎片：页表大小不再固定（是 PTE 的倍数），在物理内存中分配变长页表会导致外部碎片。

杂合的哲学

当两种方案各有优劣时，尝试结合它们往往能实现“两全其美”。但并非所有杂合都是完美的，需要权衡其引入的新复杂性。

多级页表

多级页表（Multi-level Page Table）通过将线性页表转换为树状结构，有效解决了稀疏地址空间下的内存浪费问题。它是现代系统（如 x86）中应用最广泛的方案。

核心思想

1. 分块管理：将页表切分为页大小的单元。
2. 按需分配：如果整页的页表项（PTE）都无效，则完全不为该页分配物理内存。
3. 引入间接层：使用 页目录（Page Directory） 来追踪页表页。页目录项（PDE）指向页表页，若 PDE 无效，则表示对应的整个页表块均未分配。

优缺点分析

• 优点：
  • 空间效率高：页表空间与实际使用的地址空间量成正比，完美支持稀疏布局。
  • 内存管理灵活：页表页可以离散地存放在物理内存的任何位置，无需连续的大块空间。
• 缺点：
  • 时间开销增加：TLB 未命中时，需要多次访问内存（页目录、页表项），增加了访问延迟（时间—空间折中）。
  • 复杂性提升：硬件或 OS 的地址转换逻辑变得更加复杂。

理解时空折中

在构建数据结构时，通常需要权衡访问速度（时间）与存储开销（空间）。多级页表通过牺牲 TLB 未命中时的查找时间，换取了巨大的内存空间节省。

详细示例与地址转换

假设 16KB 地址空间，64 字节页大小，4 字节 PTE。VPN 为 8 位，页表共 256 个项。

1. 索引结构拆分

• 页目录索引（PDIndex）：使用 VPN 的高位（如前 4 位），在页目录中查找 PDE。
• 页表索引（PTIndex）：使用 VPN 的剩余位（如后 4 位），在 PDE 指向s的页表页中查找 PTE。

2. 转换逻辑

PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))

3. 实例展示（见表 20.2）

Page Directory (PD)		Page of PT (@PFN:100)			Page of PT (@PFN:101)
PFN	valid	PFN	valid	prot	PFN	valid	prot
100	1	10	1	r-x	—	0	—
—	0	23	1	r-x	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	80	1	rw-	—	0	—
—	0	59	1	rw-	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	—	0	—
—	0	—	0	—	55	1	rw-
101	1	—	0	—	45	1	rw-

超过两级

当页目录本身过大（无法放入单个页）时，需要增加层级（如三级或四级页表）。例如，将页目录拆分，并引入顶级页目录。

完整转换流程（含 TLB）

在多级页表中，硬件首先检查 TLB。只有在 TLB 未命中时，才会执行完整的多级查找。

VPN = (VirtualAddress & VPN_MASK) >> SHIFT 
(Success, TlbEntry) = TLB_Lookup(VPN) 
if (Success == True) // TLB Hit 
    if (CanAccess(TlbEntry.ProtectBits) == True) 
        Offset = VirtualAddress & OFFSET_MASK 
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset 
        Register = AccessMemory(PhysAddr)
    else 
        RaiseException(PROTECTION_FAULT) 
else // TLB Miss 
    // first, get page directory entry 
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT 
    PDEAddr = PDBR + (PDIndex * sizeof(PDE)) 
    PDE = AccessMemory(PDEAddr) 
    if (PDE.Valid == False) 
        RaiseException(SEGMENTATION_FAULT) 
    else 
        // PDE is valid: now fetch PTE from page table 
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT 
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE)) 
        PTE = AccessMemory(PTEAddr) 
        if (PTE.Valid == False) 
            RaiseException(SEGMENTATION_FAULT) 
        else if (CanAccess(PTE.ProtectBits) == False) 
            RaiseException(PROTECTION_FAULT) 
        else 
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits) 
            RetryInstruction()

反向页表

反向页表（Inverted Page Table） 采取了更极端的空间节省策略：

• 全局唯一：系统只维护一个物理页表，项数对应物理内存页数，而非每个进程一个页表。
• 内容：每项记录哪个进程（PID）的哪个虚拟页（VPN）映射到了该物理页。
• 查找优化：由于需要搜索整个结构，通常在反向页表之上建立 散列表（Hash Table） 以加速查找（如 PowerPC 架构）。

将页表交换到磁盘

当页表依然过大无法完全装入内存时，一些系统会将其放入内核虚拟内存。这允许操作系统在内存压力较大时，将页表的部分内容交换（Swap）到磁盘。

小结

构建真实的页表需要在时间与空间之间进行折中：

• 内存受限系统：倾向于使用更紧凑的结构（如多级页表、反向页表）。
• 高性能/大内存系统：可能选择更简单的结构以加速 TLB 未命中的处理。

页表本质上是数据结构。在软件管理 TLB 的系统中，操作系统开发者可以灵活创新，设计出更符合特定工作负载需求的地址转换机制。