多级页表
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
复习
- 页表：记录虚拟页与物理页帧的对应关系
- 地址转换：沿着一个虚拟地址得到最终的物理地址
- TLB：给频繁的地址转换加一层缓存
TL;DR
- 单级页表太大：一个进程的页表就可能占几 MB，还要连续存放
- 多级页表把页表本身也分层，按需展开
- 用不到的部分根本不必存在，从而大幅省内存
- 代价是多几次访存，但 TLB 能把这笔账几乎抹平
正文
页表虽好，却有个规模问题：地址空间一大，页表本身就胖得离谱。
页表为什么这么占地方
以 32 位地址、4 KB 页为例：页内偏移占 12 位，页号占 20 位，也就是有一百万个页。每个页表项哪怕只占 4 字节，整个页表也要 4 MB——而且每个进程一份，还要求连续存放。
可现实是：一个进程真正用到的地址，往往只集中在少数几处，绝大多数页表项根本用不上。让它们也老老实实占着位置，纯属浪费。
于是思路又来了：把页表也分页。
把页表分层
多级页表的做法，是把页号再切一刀，分成多段，逐级查下去。以两级为例：
虚拟地址 = [ 一级页号 ][ 二级页号 ][ 页内偏移 ]
一级页表：指向某个二级页表
二级页表：指向某个物理页帧
转换时：
- 用一级页号查一级页表，找到一个二级页表的位置
- 用二级页号查那个二级页表，得到物理页帧号
- 拼上页内偏移
省在哪里
关键在于按需展开：一级页表里，某一项如果对应的那一片地址压根没用，就可以标记为“空”，根本不去创建对应的二级页表。
于是，进程真正用到的地址越多，才需要越多的二级页表；大片没用到的地址，只在一级页表里占一个“空”条目。省下来的内存非常可观——这正是多级页表的意义。
代价
分层不是白给的：原来查一次页表，现在要查两次、三次。每多一级，就多一次访存。
好在有上一章的 TLB：绝大多数转换都被 TLB 缓存住了，根本走不到“逐级查页表”这一步。于是，多级页表省了内存，TLB 补了速度，两者配合，才让虚拟内存既实用又高效。这种“用多级结构换空间、再用缓存换时间”的组合，在计算机里比比皆是。
思考题
如果一个进程几乎用满了整个地址空间，多级页表还能省内存吗？它的优势主要出现在什么情况下？
小结
知识点
- 单级页表太大，且要求连续
- 多级页表把页表分层，按需展开
- 没用到的大片地址不创建下级页表，从而省内存
- 代价是多级查表，靠 TLB 弥补
参考资料
- Wikipedia(zh)：页表：多级页表
- Wikipedia(zh)：转译后备缓冲器：TLB 的作用
思考题答案（仅供参考）
如果一个进程几乎用满整个地址空间，那么多级页表里几乎没有“空”条目可以省略，省内存的效果就大打折扣——它甚至还要多花一层目录的开销。多级页表的优势，主要出现在“地址空间很大、但进程实际只用了一小部分”的常见情况下：大片未使用的区域只占一个空条目，下级页表根本不用创建。现实中绝大多数程序都属于后者，所以多级页表非常划算。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪