多级页表与稀疏地址空间

平表为每个可能虚页预留一个槽。两级表把16个相邻虚页归为一组：只有该组至少需要一个驻留映射时才分配叶表。地址空间越稀疏、映射越聚集，省下的空叶表越多；若每组只映一个页，省空间效果会明显减弱。

查表不是把整个地址拿去“查树”。每层消费固定的几位，位宽决定分支数，PTE宽度决定条目字节地址。页框号、表页基址和条目地址是三个不同的量。

两个根完整走一遍 ​

P根在PFN0x01，即r=0x0100；根索引1指向叶表PFN0x02。Q根在PFN0x03，索引1指向PFN0x04。两张叶表的索引2分别映射到数据PFN0x30和0x50。

v=0x12AB给出i1=1,i0=2,o=0xAB。P先读根项物理地址0x0100+1×16=0x0110，得到0x02；再读0x0200+2×16=0x0220，得到0x30；最后访问0x30AB。Q相应读0x0310、0x0420，最后访问0x50AB。首次访问没有TLB命中、没有缓存表页时，两次PTE读取再加一次数据读取，共三次内存访问。

若P访问0x2701而根索引2不存在，遍历在第一层停止，不能继续把零当下一层地址读内核页。若根存在而叶项不驻留，则停在第二层。软件随后查合法区域；两种停止位置都没有直接告诉它“应该杀死进程”还是“应该分配页”。

空间不一定总比平表省 ​

P仅映射VPN0x10、0x12、0x13时，共需根和一张叶表，512B。加入VPN0xF0后需第二张叶表，共768B。平表始终需256×16=4096B。若16个根分支都需要叶表，则两级结构占17页、4352B，比平表多一页；稀疏优化不意味着任何输入都更小。

按页分配表页时，新增某组第一个映射的成本包括清零整张叶表；新增同组的另一个映射只需改叶项。最后一个叶映射撤销后，只有确认没有并行遍历或缓存引用需要该表页，才可回收叶表。

对固定层数L，未缓存遍历最多读取L个PTE，成功数据访问再加一次。对一般每层f项、m个已映射虚页的树，空间取决于它们共享多少索引前缀，不能简单写成mL个新节点并称精确值。最坏按路径计上界可以，聚集映射通常共享很多上层页。

多级结构只解决表空间和查找组织，访问速度还需TLB理路TLB与地址翻译失效Translation lookaside buffer · TLB miss · TLB invalidation将翻译缓存键、权限和映射生命周期一起核对，区别TLB未命中与缺页，构造改PTE后仍越权的最短反例。。OS-16两级不是xv6的Sv39：rev5教材使用三个9位索引与12位偏移、8B PTE。把OS-16的地址直接套到Sv39会得到错误表项地址；同一分解方法可以迁移，参数必须重新取自ISA。