3.1_8 两级页表

（一）单级页表存在的问题

  某计算机系统按字节寻址，支持32位的逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为4B。

  4KB = $2^{12}B$，因此页内地址要用12位表示，剩余20位表示页号。

  因此，该系统中用户进程最多有$2^{20}$页。相应的，一个进程的页表中，最多会有$2^{20}=1M=1,048,576$个页表项，所以一个页表最大需要$2^{20}\ast 4B=2^{22}B$，共需要$2^{22}/2^{12}=2^{10}$个页框存储该页表。

  根据页号查询页表的方法：K号页对应的页表项存放位置 = 页表始址 + K * 4。

  要在所有的页表项都连续存放的基础上才能用这种方法找到页表项。

  因此，在这个系统当中，某个进程，光对它的页表进行存储，就有可能需要专门分配$2^{10}=1024$个连续的页框。

  为每个进程都要分配许多连续的页框，这显然是很吃力的，完全不具备离散存储的优点。——这是单级页表的第一个明显的缺点。

  根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

  这是单级页表存在的第二个问题。

（二）如何解决单级页表的问题？

问题一

  页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。

  思考：我们是如何解决进程在内存中必须连续存储的问题的？

  答：将进程地址空间分页，并为其建立一张页表，记录各页面的存放位置。——同样的思路，再次套用，就可用于解决“页表必须连续存放”的问题，把必须连续存放的页表再分页。

  解决方案：

  可将长长的页表进行分组，使每个内存块刚好可以放入一个分组（比如上个例子中，页面大小4KB，每个页表项4B，每个页面可存放1K个页表项，因此每1K个连续的页表项为一组，每组刚好占一个内存块，再将各组离散地放到各个内存块中）。

  另外，要为离散分配的页表再建立一张页表，称为页目录表，或称外层页表，或称顶层页表。

问题二

  没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

  解决方案：

  可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。

  缺页中断肯定是在执行某条指令、这个指令想访问到某一个暂时还没有被调入内存的页面而产生的。所以，这个中断信号和当前执行的指令有关。因此，这种中断应该属于内中断。（对于缺页中断的相关内容，在之后会更加详细的介绍）

（三）两级页表的原理、地址结构

  32位逻辑地址空间，页表项大小为4B，页面大小为4KB，则页内地址占12位。

  页号占20位，则进程最多有$2^{20}$个页面。

  按照刚才的思路，我们可以把这么大的一个页表，拆分成多个小的分组。每个小分组的大小可以让它刚好能够装入一个内存块。

  我们每个内存块的大小是4KB，而页表项的大小是4B，所以一个页面可以存放1K个页表项。——所以，我们把这个大的页表拆分成一个个的小分组，其中，每个小分组当中也有1024个页表项，如图所示。

  另外，我们给这些“小页表”进行编号，0号页表、1号页表……、1023号页表。

  进行这样的拆分后，我们就把$2^{20}$个页表项的大页表，拆分成了$2^{10}$个小页表，且每个小页表中有$2^{10}$个页表项。

  需要注意“页号”的分配。例如，在原来的大页表当中，页号为1024的页表项，它经过分配以后，它应该是变成了1号页表当中的页号为0的页表项。

  在得到拆分好的$2^{10}=1024$个小页表之后，由于每个小页表的大小也都是4KB（刚好是内存块的大小），因此每个小页表都可以各自放到一个页框当中。

  所以，为了记录这些小页表最终存放到的内存块的位置。我们需要对这些小页表再建立上一级的表。这个上一级的表就叫做“页目录表”（或顶级页表、外层页表）。

  那么相应的，我们下一级的那1024个小页表就可以称之为“二级页表”。

  在采用这样的两级页表之后，逻辑地址结构也需要发生相应的变化。我们可以把以前20位的页号，拆分成两个部分——第一个部分是10位的，用来表示“一级页号”；第二个部分是10位的，用来表示“二级页号”。（且10位二进制数刚好足够表示0 ~ 1023）

（四）如何实现地址变换

  例：将逻辑地址(0000000000, 0000000001, 111111111111)转换为物理地址（用十进制表示）。

分析

  1.按照地址结构将逻辑地址拆分成三部分。

  2.从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置。

  根据题目信息，可知，要查询的逻辑地址，其一级页号是0，即“页目录表”中的0号表项。（即下图中的第一项，其对应内存块号是3）

  根据一级页表查出，其二级页表存放的物理位置在内存块号为3的地方。于是就可以从内存当中对应位置读出该二级页表。

  根据题目条件，可知逻辑地址当中的“二级页号”是页号1，即查找二级页表中页号为1的页表项，即上图中间的二级页表的第二项。

  3.根据二级页号查表，找到最终想访问的内存块号。

  通过二级页表的查找，可以知道，最终我们想要查找的逻辑地址是在4号内存块中。

  4.结合页内偏移量得到物理地址。

  最后，我们根据所访问的内存块号，结合页内偏移量，得出最终的物理地址。

  我们最终要访问的内存块号为4，并且每个内存块的大小为4KB。那么，该内存块的起始地址为4 * 4096 = 16384。同时，由题目条件可知，页内偏移量转换为十进制之后是1023。

  最终物理地址为：16384 + 1023 = 17407。

（五）需要注意的几个细节

  1.若采用多级页表机制，则各级页表的大小不能超过一个页面。

例题：

  某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用（）级页表，页内偏移量为（）位？

分析：

  首先，比较容易确定的是“页内偏移量的位数”。页面大小是4KB，且是按字节编址。所以，页内偏移量应该占12位。而剩余的28位就应该是用来表示页号的。

  另外，由于页面大小是4KB，每个页表项大小是4B，所以每个页面可以存放$2^{10}$ =1024个页表项。

  由于采用多级页表机制时，各级页表的大小不能超过一个页面。所以，各级页表当中，页表项的个数最多不能超过$2^{10}$个。——相应地，各级的页号所占位数不能超过10位。——所以，28位的页号，我们可以把它分成三个部分。

  2.两级页表的访存次数分析（假设没有快表机构）。

  第一次访存：访问内存中的页目录表（顶级页表）；

  第二次访存：访问内存中的二级页表；

  第三次访存：访问目标内存单元。

  如果是单级页表，不考虑快表的话，在访问一个逻辑地址的时候只需两次访存。

  可见，两级页表虽然解决了我们之前提出的单级页表的两大问题，但是这种内存空间利用率的上升所同时付出的代价就是，逻辑地址需要更多一次的访存，就会导致我们访问某个逻辑地址的时候就要花费更长的时间。这也是两级页表相比于单级页表的一个比较明显的缺点。

  如果我们继续分析三级页表、四级页表的访存次数……

  会发现，其实有一个规律：n级页表在访问逻辑地址的时候，访存次数是n+1次。（在不考虑快表机构的情况下）

总结