使用多级页表节省空间

概要：以 32 位操作系统为例，计算单级页表占用的巨大内存空间，引出多级页表（Multi-level Page Table）通过按需分配页表项来节省空间的原理。

1 单级页表很占空间

设定一个最常见的场景：一个 32 位的操作系统。

1.1 基础环境设置

• 虚拟地址空间：$2^{32} = 4GB$。
• 物理页大小：$4KB$（即 $2^{12}$ 字节）。
• 总页数：$4GB / 4KB = 2^{20} \approx 100$ 万页。
• 页表项大小：每个条目（PTE）占 $4$ 字节。

---

1.2 单级页表分析

想象一张巨大的表格，每一行对应一个虚拟页。

• 实现方式：为了让 CPU 能通过索引（$O(1)$ 时间）快速找到物理地址，这张表必须是连续的。
• 空间计算：$100 \text{ 万个条目} \times 4 \text{ 字节} = 4MB$。

实际例子：运行一个 “Hello World” 程序

你的程序非常小，只占用了 $1MB$ 的内存。

• 逻辑：即便你只用了 $1MB$，由于单级页表必须涵盖整个 $4GB$ 的范围才能进行索引映射，操作系统必须为这个进程分配完整的 $4MB$ 连续内存来存放页表。
• 浪费情况：在这个 $4MB$ 的页表中，只有极少部分（指向那 $1MB$ 数据的项）是有意义的，剩下 $99.9\%$ 的空间都在记录“这里没用到”。

痛点：如果你运行 $100$ 个这样的小程序，光是存放页表就要浪费 $400MB$ 的物理内存。

2 朴素的想法

• 一个问题：一个进程一般不会用完所有的虚拟地址，那么这些虚拟地址如果也存储，就十分的占空间。一个朴素的想法是，数组元素只存用到的虚拟地址对应的物理地址，比如元素0{(1, 物理页A)}，元素1{ (201, 物理页B)}。为什么不行呢？

因为这样的速度太慢了： MMU 拿到虚拟页号 201，然后他怎么知道哪个元素对应的是虚拟页号201的映射呢，只能一个个找，这样太慢了。

能否再建立一个虚拟地址的页表呢，告诉MMU虚拟页号201的页表项在元素1中？

当然不行，实际上这里有一个套娃。如果你建立一个“辅助表”，那么 MMU 在查找时，依然面临同样的问题：MMU 怎么知道“虚拟页号 201”在辅助表里的哪一行？ 如果辅助表也是数组：为了能 O(1) 查找，辅助表必须以虚拟页号作为下标。那么这个辅助表依然要有 201 个坑位（甚至更多）。我们绕了一圈，空间还是没省下来。 如果辅助表不是数组（比如是链表）：MMU 还是得一个个对比（“你是 201 吗？”“不是”……），速度依然慢。

3 聪明的解决方案

把“大数组”切成“小目录”。既然“大数组”太占空间，我们的解法不是取消数组，而是把一个巨大的数组，拆成很多个离散的小数组。这就是多级页表。它的逻辑结构和上文提到的“辅助表”非常像，但它是这样工作的：第一层（页目录/辅助表）：它不记录具体的页号（201），而是记录地址范围。比如：

• 第 0 项：负责 $0 \sim 1023$ 号页的映射表在哪里。
• 第 1 项：负责 $1024 \sim 2047$ 号页的映射表在哪里。
• ……

第二层（实际页表）：只有当进程真的用了 $0 \sim 1023$ 号页中的某一个时，内核才会真正去申请 4KB 的内存来存放这一组的映射关系。

为什么这样能省空间？因为如果进程只用了第 1 页和第 100 万页，中间那几十万个页对应的“第二层小表”根本就不会被创建。第一层的“页目录”里，中间那些项直接写上“空”就好了。

3.1 多级页表的空间占用分析

我们将这 $100$ 万个页表项拆成两层：

1. 页目录（一级页表）：包含 $1024$ 个项。
2. 页表（二级页表）：每个页目录项指向一个包含 $1024$ 个项的二级表。

实际例子：同样运行那个 “Hello World” 程序（$1MB$）

由于这个程序很小，它在虚拟空间里可能只占用了前 $1MB$ 的范围。

• 一级页目录：始终存在，占用 $1024 \times 4 \text{ 字节} = 4KB$（正好是一个物理页）。
• 二级页表：因为你的程序只用了 $1MB$，而一个二级页表就能覆盖 $1024 \times 4KB = 4MB$ 的范围。所以，你只需要创建一个二级页表。
• 空间计算：$4KB (\text{一级}) + 4KB (\text{二级}) = 8KB$。

结果对比：

• 单级页表：$4096KB$ (4MB)
• 二级页表：$8KB$
• 节省比例：512 倍！