两级页表

  本文是在基本分页存储管理的基础上对分页管理的优化。在上篇文章中说到，操作系统会为每个进程建立一张页表，实现页号和内存块号之间的对应关系。本文从单级页表存在的问题引出两级页表，以及两级页表如何实现地址的变换。

1单级页表存在的问题

  假设某计算机系统按字节寻址，支持32位逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为4B。
  4KB = 2¹²B，因此页内地址要用12位表示，剩余20位表示页号。——上篇文章 第三节的结论。
  因此，该系统中用户进程最多有2²⁰页。相应的，一个进程的页表中，最多会有2²⁰个页表项，所以一个页表最大需要2²⁰ * 4B = 2²²B。一个页框（内存块）大小为4B，所以需要2²²/2¹² = 2¹⁰个页框存储该页表。而页表的存储是需要连续存储的，因为根据页号查询页表的方法：K号页对应的页表项的位置 = 页表起始地址 + K * 4B（页表项长度），所以这就要求页表的存储必须是连续的。
  回想一下，当初为什么使用页表，就是要将进程划分为一个个页面可以不用连续的存放在内存中，但是此时页表就需要1024个连续的页框，似乎和当时的目标有点背道而驰了....
  此外，根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此也没有必要让整个页面都常驻内存。
  所以，单级页表存在以上两个问题。

2 两级页表

  如何解决页表过大需要连续存储的问题呢？这个问题可以参考进程太大需要连续存储的答案。因为页表必须连续存放，所以可以将页表再分页。
  解决方案：可以将长长的页表进行分组，使每个页面中刚好可以放下一个分组（如上面的例子中，页面的大小4KB），每个页表项4B，所以每个页面中可以存放1K个（1024）个页表项，因此每1K个连续的页表项为一组，每组刚好占一个页面，再讲各组离散的放在各个内存块中）。这样就需要为离散的页表再建立一张页表，称为页目录表，或外层页表，或顶层页表。
  还是面的例子，32位的逻辑地址空间，页表项大小为4B，页面大小4KB，则页内地址占12位，单级页表结构逻辑结构图如下图所示

  使用单级页表的情况

  将页表分为分为1024个表，每个表中包含1024个页表项，形成二级页表。二级页表结构的逻辑地址结构如下图

  两级页表如何实现地址转换：

(1) 按照地址结构将逻辑地址拆成三个部分。
(2) 从PCB中读取页目录起始地址，再根据一级页号查页目录表，找到下一级页表在内存中存放位置。
(3) 根据二级页号查表，找到最终想要访问的内存块号。
(4) 结合页内偏移量得到物理地址。

  下面以一个逻辑地址为例。将逻辑地址（0000000000,0000000001,11111111111）转换为物理地址的过程。

3 虚拟存储技术

  再解决了页必须连续存放的问题后，再看如何第二个问题：没有必要让整个页表常驻内存，因为进程一段时间内可能只需要访问某几个特定的页面。
  解决方案：可以在需要访问页面时才把页面调入内存——虚拟存储技术（后面再说）。可以在页表中增加一个标示位，用于表示该页表是否已经调入内存。

4 几个问题

  (1) 若采用多级页表机制，则各级页表的大小不能超过一个页面。
  举例说明，某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用（）级页表，页内偏移量为（）位？
  页面大小 = 4KB，按字节编址，因此页内偏移量为12位。
  页号 = 40 - 12 = 28位。
  页面大小 = 4KB，页表项大小 = 4B，则每个页面可存放1024个页表项。因此各级页表最多包含1024个页表项，需要10个二进制位才能映射到1024个页表项，因此每级页表对应的页号应为10位二进制。共28位的页号至少要分为3级。

  (2) 两级页表的访问次数分析（假设没有页表）：

(1) 第一次访问：访问内存中的页目录表。
(2) 访问内存中的二级目录。
(3) 访问目标内存单元。

  从上面可以看出，两级页表虽然解决了页表需要连续存储的问题，但是同时也增加了内存的访问次数。

4 小结