[OS]Three Easy Pieces Chapter 20

Paging: Smaller Tables

基本的页式内存存在的一个问题就是页表占据的空间太大了。

1 Simple Solution: Bigger Pages

最简单的方法就是使用更大的页，这样可以减少页表项的个数，从而减少页表的大小。但是这种方法会导致内部内存碎片。

2 Hybrid Approach: Paging and Segments

段页式内存，结合段式内存和页式内存。每个段由一对base/bound寄存器管理。base寄存器指出该段页表的物理地址，bound寄存器指出该页表的结束地址。这样，当一个段只有很少的页的时候，页表只有几个页表项，节省了空间。但是，因为每个段的页表还是线性的，如果某个段的内存很稀疏，我们仍然需要为所有中间的没有使用的页分配页表项。

3 Multi-level Page Tables

传统页表最本质的问题是，我们很难在内存中找出一大块连续的内存用来存放页表项，并且这些页表项中有很多是无效的。多级页表最本质的思想就是页表按页来管理，如果页表中某页的所有页表项都是无效的，那么可以不分配页表的该页。这样就可以节省很多空间，如上图所示。

多级页表以时间换取空间。每次TLB miss的时候，为了完成地址转换，我们需要额外的内存访问去获取相应的页表项。而且，多级页表增加了复杂性。

4 Inverted Page Tables

我们也可以反转页表，即通过物理页号去找对应的进程的虚拟页号。这样，整个系统只需要一个页表即可。为了完成地址转换，如果需要线性扫描整个页表，时间开销太大了，可以使用哈希表来管理。

5 Swapping the Page Tables to Disk

页表仍然有可能太大导致无法一次性放入内存中，有些系统将页表放在内核虚拟内存中，允许操作系统将页表换出到磁盘中。