分页和页表

除了分段，空间管理的第二种常见方式是分页。

Linux将虚拟内存划分成固定大小的页（Linux中的页大小是4KB），并且以页作为操作内存的最小单元。例如一次性读取一页，虚拟内存中的页称为虚拟页。对应的，物理内存也会划分成固定大小的页来管理，称为物理页，也常称为页框或页帧（page frame）。物理页和虚拟页的大小相等。

值得注意的是，虽然虚拟内存和物理内存都将空间全部划分成页，但不可能会为所有虚拟页分配好所有对应的物理页，所以虚拟页有一个有效位的属性，如果该页有分配对应的物理页，则有效，否则无效。

为了将虚拟页的页号（Virtual page number，VPN）和物理页的页号（Physical page number, PPN）也对应起来，也需要进行地址翻译。如图所示。

为了完成这个翻译过程，操作系统为每个进程都维护了一个称为页表（page table）的数据结构。页表中的每项代表一个页的映射信息，也称为页表项（Page Table Entry，PTE）。

注意，页表是每个进程都有一个的，因为每个进程的虚拟地址空间都是独立的，各进程中的页映射到物理页自然也是不同的。

每一个页表项中都保存了很多东西，比如最基本的虚拟页号和物理页号、页偏移、页是否有效的有效位（比如表明是否已分配该页内存）、页是否可读/写/执行的保护位、页是存在于内存还是存在于交换分区的存在位、页是否修改过的脏位、页是否最近访问过的访问位，等等。

通过分段+分页的方式，不再为整个地址空间分配一个页表，而是为每个段落分配一个页表，这样每个页表的大小就减小了，而且段落是独立管理的，那么每个段落中的页表的访问频繁度也将不一样。在文件系统中，分段+分页的思想体现为块组+数据块。但是分段+分页的方式也是有缺点的，它虽然为每个段划分页表，但仍然为所有的内存划分了页，且总页表大小并没有改变。所以，操作系统不使用这种方案。

第二种方案是使用多级页表，也是Linux中使用的方案，它不依赖于分段。它的思想是：如果某页表中包含的所有页表项都是无效的页（例如未分配的），就不为这段空间的页维护页表，这样就能减小页表的大小。这个逻辑其实很简单：对于没有分配的页，没有必要去记录这些页的翻译方式。

由于不是所有页都维护了页表，所以使用一个称为页目录（Page Director）的数据结构去记录所有的页表（通过指向页表的指针记录），并标记每个页表是否有效，页表有效表示该页表已经分配，这也意味着该页表中一定有正在使用中的有效页。因为页目录是页表的更高一层次，所以称为多级页表。

下图显示了使用线性页表和多级页表的不同之处。在线性页表中，尽管有连续的页是无效页，但仍然维护了4个页表。而在多级页表中，没有为那些连续无效的页维护页表。显然，使用多级页表减小了页表的大小。