操作系统笔记(8)-多级页表

简介

假设一个 32 位地址空间（2^32 字节），4KB （2^12 字节）的页大小和 4B 的页表项大小，那么每个进程需要用来维护页表的内存就是 4 * 2^20B 也就是 4MB，当多个进程运行时，页表占用的空间就会非常大！
为了解决这个问题，提出了 多级页表 ，它的思想是将页表分成 页大小 的 单元，如果一整块 单元 的页表项无效，就完全不分配该页的页表，为了追踪页表的页是否有效，引入了一个新的数据结构叫 页目录（PD），它可以告诉你页表的页在哪里或者页表的整个页不包含有效页
可以看到，多级页表 的工作方式就是让线性页表的一部分消失（因为实际运行的程序中可能会有很多单元无效），就相当于将原来的一大张页表拆分成很多小的，用一个 页目录 来映射这些 小页表，如果某个小页表中的所有项都是无效的，就不分配这页的内存，如下图所示：
上图就是 二级页表 结构，每一个 有效 的 页目录项（PDE） 都对应这一张含 有效 页表项的页表，可以大大节省空间，但是这样会产生额外的内存引用开销，因此 多级页表 是一个时间——空间折中

设想一个大小为 16KB 的地址空间，其中包含 64B 的页，因此我们有 14 位（2^14 = 16KB）的虚拟地址空间，其中 6 位表示偏移量（2^6 = 64B），剩余 8 位表示页号 VPN
如果不使用 多级页表 ，我们的页表有 2^8 = 256 项，假设页表项 PTE 的大小为 4B，则页表的大小为 256 * 4B = 1KB
使用 多级页表 ，我们就需要将页表划分为若干 单元，1KB 的页可以分为 16 个 64B 的页，每页可以容纳 16 项 PTE
划分依据，根据单页的大小划分，划分出的每页大小为 64B ，可以容纳 64 / 4 = 16 项，因此原页表为划分成了 256 / 16 = 16 块 单元，这样就确定了 页目录（PD） 结构的大小，如果页目录项 PDE 的大小也是 4B，那么 PD 的大小刚好为一页的大小
为了通过虚拟地址确定页目录项以及页表偏移，我们把 VPN 的 8 再划分，前 4 位表示页目录索引，后 4 位表示页表索引，如下图：
假如地址空间中只有前两项和后两项被使用，那么我们只用创建两张页表和一张页目录，相比于原来的 单级页表，多级页表 大大节省了内存空间

拿现在最常见的 64 位机器来说（2^64 字节的地址空间），如果页表的大小为 4KB ，那么偏移量占 12 位，剩余 52 位为 VPN，此时如果使用两级页表，页表项大小为 4B，则一张页表可以容纳 1024 项，需要的页表索引就是 10 位，但是这样页目录索引就占了 42 位，页目录需要的大小就是 2^42 * 4 B，太大了完全不可行，因此我们需要对页目录再进行划分，按每个子目录表的大小为 4K 来算，需要进行 4 级划分（2^40），前面还有 2 位就不用了，4 级页表可以将内存消耗控制在一个合理的大小

有些系统使用了 反向页表，即保留一个页表，其中的项代表系统的每个 物理页，而不是每个进程一个的页表
页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到此物理页，因此是 反向 的，由于物理地址非常大，所以线性扫描页表不合理，所以采用了 散列表 的方式快速查找

尽管使用 多级页表 减少了内存消耗，但是它仍然有可能是太大而无法一次装入内存，因此一些系统将这样的页表放入内核虚拟内存，从而允许系统在内存压力较大时，将这些页表中的一部分交换到磁盘