分页：较小的表

原始方法

• 我们需要为一个进程的整个地址空间提供页表映射，而就像简单地址空间机制一样，地址空间中存在很多未被使用的部分

分页与分段的杂合(Hybrid)方法

• 我们不为进程的一整个地址空间提供一个页表，而是为代码、堆、栈各维护一个页表
• 在MMU中存储三对基址-界限寄存器，其中：
  • 基址指示该段的页表的物理地址
  • 界限指示页表的结尾（即它有多少有效页）
• 此时，内存访问使用的虚拟地址会包含：段位、虚拟页面号、页内偏移量
• 使用这种方式会让栈与堆之间未被分配的页不再占用页表中的空间
• 这种方法仍然存在问题：
  • 虽然段外的空间不需要用页表来记录，但是对于段内的未使用部分，仍然需要在页表中为其标注无效
  • 在此方法下，页表的大小变得不固定（PTE的倍数），为页表分配内存时则可能会出现外部碎片问题

实现方式：将页表以类似树的数据结构存储

• 将页表分成页大小的单元
• 如果有某个存储页表的页，这一整个页里的页表项都无效，那么就完全不分配这些页表项
• 使用一个新结构页目录(Page directory) 来追踪存储页表的页是否“里面的页表项有效“，也就是指示出某一部分页表的在哪一页，或者某个页里的页表项不包含有效页
• 在一个二级页表中，页目录将每一部分页表（大小为一页）都存储在各个页目录项(PDE, Page Directory Entries) 中
• 一个PDE（至少）包含有效位(Valid bit) 和页帧号(Page frame number) ，类似于PTE
  • 有效位：如果该PDE指向的那一部分页表中至少标记了一个有效的页，那么该位就会被置1，否则被置0

多级页表的性质

• 只要仔细构建，那么页表中的每个部分都可以刚好放在一个页中，从而更容易地管理内存
• 操作系统在需要一个页时，可以非常简单的找到下一个空闲页：
  • 线性页表：按照PTE数组寻找空闲页。这需要整个页表都驻留在内存中
  • 多级页表：增加了一个间接层(Level of indirection)，使用一个指向页表任何地方的页目录，让我们能够将页表的每个部分存储在物理内存的任何地方
• 多级页表通过一个新的容器，达到了“时空折中(Time-space trade-off)”的效果