319_两级页表
# 3.1_9_两级页表
各位同学大家好，在这个小节中我们会介绍两级页表相关的一系列知识点，两级页表其实是为了解决单极页表当中存在的一些问题，所以我们会从单集页表存在的问题着手开始分析并且分析如何解决这些问题，由此引出两级页表机制。
那么两级页表的原理、逻辑地址结构还有地址变化的过程，这是咱们之后会讲解的内容。最后我们还会强调几个两级页表问题，在考试当中有可能会作为考点的一个很重要的几个细节，我们会按照从上至下的顺序依次讲解。
# 单级页表存在的问题
首先来看咱们之前介绍过的单级页表机制存在什么问题，假设一个计算机系统按照字节选址支持 32 位的逻辑地址，那么采用分页存储管理页面大小是 4KB，页表项长度是 4 个字节，既然一个页面的大小是 4KB，也就是 2 的 12 次方个字节，所以在这 32 位的逻辑地址当中，需要有 12 位来表示页内地址，然后剩余的 20 位才是表示页号
既然有 20 位表示页号，也就意味着一个用户进程最多有可能有 2 的 20 次方个页面，而我们知道每一个页面需要对应一个页表项，那么这么多的页面就需要的对应同等的 220 次方个页表项，而每个页表项的大小是 4 个字节，所以总共就需要二的 22 次方个字节来存储进程的页表。这么多的字节总共就是 2 的 10 次方个页框，也就是 1024 个页框。
但是之前咱们讲过，为了实现通过页号查询对应的页表项这件事情，那么一般来说整个页表都是需要连续的存放在内存当中的，因此在这个系统当中一个进程光它的页表就有可能需要占用连续的 1024 个页框来存放，要为一个进程分配这么多的连续的内存空间，这显然是比较吃力的。并且这已经丧失了我们离散分配这种存储管理方式的最大的一个优点。所以这是单级页表存在的第一个很明显的缺陷问题。
第二个问题，由之前我们介绍过的局部性原理，我们可以知道很多时候其实进程在一段时间内只需要访问某几个特定的页面，就可以正常的运行了。因此我们没有必要让进程的整个页表都常驻内存，我们只需要让进程此时会用到的那些页面对应的页表项在内存当中保存就可以了，所以这是单级页表存在的第二个问题。
那么从刚才的分析当中，我们知道单击页表存在两个明显的问题，第一个问题就是页表必须连续的存放，所以如果页表很大的话，那么光页表就需要占用连续的很多个页框，这和我们离散分配存储管理的这种思想其实是相悖的，所以我们要尝试解决这个问题。第二个问题就是我们没有必要让整个页表都常驻内内存，因为进程在一段时间内可能只需要访问某几个特定的页面就可以顺利的执行了，这是基于局部性原理得出的一个结论，
我们首先讨论第一个问题应该怎么解决。其实我们可以参考一下我们之前解决进程在内存当中必须连续存储的问题的时候提出的那种思路。
我们之前的做法其实很简单，就是把进程的地址空间进行分页，然后再为进程建立一张页表，用来记录它的各个页面之间的顺序，还有保存的位置，这些信息。
同样的思路，其实我们也可以用来解决一个页表必须存储连续占用多个页框的问题，我们可以把很长的页表进行分组，让每一个内存块刚好可以放入一个分组，比如说像之前那个例子当中，我们的页面一个页面可以存放 1k 个页表项，所以我们可以让每 1k 个连续的页表项为一组，然后这样的一组就可以刚好占满一个内存块，然后再把这些各个分组离散的分配到各个内存块当中。为了保证我们把这些分组离散的放到各个内存块之后，还能够知道这些分组之间的先后顺序，因此我们依然是像需要模仿之前的这种思路，为这些分组再建立一个页表，然后页表就称为页目录表，或者叫外层页表或者叫顶层页表。当然 408 的真题当中比较喜欢用的是页目录表这个名词，这个地方光看这些文字描述会比较抽象，
# 两级页表的原理、地址结构
我们直接结合图像来进行进一步的理解，还是沿着刚才的例子进行分析。32 位的逻辑地址空间页表项大小为 4b，页面大小为 4KB，所以页内地址应该是占 12 位，其余的 20 位才是页号。所以如果我们采用的是单极页表结构的话，逻辑地址结构应该是这个样子。既然我们的页号有 20 位，就意味着在这个系统当中一个进程最多有可能会有 220 个页面，相应的也会有 220 个页表项。如果用 10 进制表示的话，这些页表项的编号应该是 0 到1048575，这其实就是 220-1 这么一个数。
现在由于页表的长度过大，所以我们按照之前所说的那种思路，我们可以把这么大的一个长长的页表把它拆分成一个的小分组，每个小分组的大小可以让它刚好能够装入一个内存块，我们每个内存块或者说每个页面的大小是 4KB，而页表项的大小是 4b。所以一个内存块一个页面可以存放 4k 除以 4，也就是 1k 个页表项，那么换算成十进制就应该是 1024 个页表项，因此我们可以把这么大的页表拆分成一个一个小分组，每一个分组的页表项有 1024 个，就像这个样子。另外我们可以给这些小页表进行编号，0 号页表 1 号页表和一直到 1024 个页表，进行这样的拆分之后，最后总共就会形成 1024 个一个的小页表。
这个地方可以稍微注意一下的是，以前在大页表当中编号为 1024 的页表项，在进行拆分以后，应该是变成了第二个小页表当中的第一个页表项，所以可以看到页表项和页表项的块号是一样的，只不过页号就变为了从 0 开始，
我们继续往下分析，再把大页表拆分成这样一个小页表之后，由于每一个小页表的大小都是 4KB，因此每一个小页表都可以依次放到不同的内存块当中。所以为了记录这些小页表之间的相对顺序，还有它们在内存当中存放的块号位置，我们需要为这些小页表再进行再建立上一级的页表，而这级的页表就叫做页目录表或者叫顶级页表，外层页表，相应的这层的小页表，我们可以把它称为二级页表。
从这个图当中也可以很直观的看到，页目录表其实是建立了二级页表的页号，还有二级页表在内存当中存放的块号之间的一个映射的关系。所以如果此时我们想要找到 0 号页表的话，那么我们可以通过页目录表就可以知道 0 号页表是存放在 3 号内存块里的，所以只需要在 3 号内存块这个地方来找 0 号页表就可以了。
在采用了这样的两级页表结构之后，逻辑地址的结构也需要发生相应的变化，我们可以把以前的 20 位的页号拆分成 2 个部分，第一个部分是 10 位的二进制用来表示一级页号，第二部分也是 10 位二进制用来表示 2 级页号，那 10 位的二进制大家会发现刚好是可以表示 0~1023 这么一个范围，所以用一级页号来表示这个范围是刚好的。相应的二级页号的这 10 个二进制位，就是用来表示 2 级页表当中的这些页号。
# 如何实现地址转换
接下来我们再结合这个例子来看一下我们应该怎么实现地址的变化，把逻辑地址这么一串东西转换成物理地址，并且最后的物理地址要用 10 进制表示。
那么要进行地址变化，我们要做第一件事情就是根据我们的地址结构，把逻辑地址拆分成三个部分，也就是一级页号，二级页号，还有页内偏移量这么三个部分。
第二步我们可以从 PCB 当中知道我们的页目录表在内存当中存放的位置到底是哪里，这样的话我们就可以根据一级页号来查询页目录表了，一级页号是 0，从页表项当中我们可以知道0 号的二级页表存放在内存块号为 3 号的地方，所以我们可以从这个位置读出二级的页表，然后开始用二级页号来再进行查询。
二级页号是一，通过页表项我们就可以知道，最终我们想要访问的地址应该是在 4 号内存块里的。所以接下来我们就可以根据最终要访问的内存块号和页内偏移量，得出我们最终的物理地址了。由于我们想要访问的是 4 号内存块，并且每个内存块的大小是 4KB，也就是4096 个字节，所以 4 号内存块的起始地址应该是 4×4096，就等于 16384。另外页内偏移量把它转换为 10 进制之后应该是 1023，所以我们可以用内存块的起始地址，再加上页内偏移量的数字，就可以得到最终的物理地址 17407 了。
经过刚才的一系列分析，我们就解决了我们之前提出的第一个问题。当页表很大的时候，其实我们可以采用两级页表的这种结构，来解决页表必须连续的占用多个页框的问题。
# 解决页表常驻内存的问题
接下来我们再来看一下第二个问题应该怎么解决。其实如果说不让整个页表常驻内存的话，那么我们可以在需要访问页面的时候，才把页面调入内存，其实这是咱们之后会介绍的虚拟存储技术。在之后的小节当中会有更详细的介绍，这只是先简单的提一下他的思想。
我们可以给每一个页表项增加一个标志位，用来表示这个页表相对应的页面到底有没有调入内存。如果说此时想要访问的页面暂时还没有调入内存的话，那么就会产生一个缺页中断。然后操作系统负责把我们想要访问的目标页面从外存调入内存 缺页中断肯定是我们在执行某一条指令，想要访问到某一个暂时还没有调入的页面的时候产生的，所以这个中断信号和当前执行的指令有关，因此这种中断应该是属于内中断，这个部分的内容咱们在之后的小节当中还会有更详细的介绍。
# 需要特别注意的小细节
接下来我们再来强调几个在考试当中需要特别注意的小细节。第一个，如果我们采用的是多级页表机构的话，那么各级页表的大小不能超过一个页面，这个限制的条件，我们在做题的时候应该怎么应用？
我们直接来看一个例子，假设某系统按字节编制采用 40 位逻辑地址结构，然后页面大小是 4KB，页表项是 4b，如果采用的是纯页式存储的话，需要采用几级页表，页内偏移量又是多少位呢？
我们首先最容易确定的应该是页内偏移量的位数，每个页面的大小是 4KB，而这个系统是按字节编制的，所以页内偏移量应该占 12 位，而剩余的 28 位就应该是用来表示页号的。
另外由于每个页面的大小是 4KB，而每个页表项是 4b，所以一个页面可以存放二的 10 次方个页表项也就是 1024 个页表项。
由于采用多级页表的时候，各级页表的大小不能超过一个页面，所以说各级页表当中页表项最多不能超过 2 的 10 次方格，相应的各级页号所占的位数也不能超过 10 位
所以 28 位的页号，我们可以把它分成 3 个部分，1 级页号占 8 位，2 级页号，10 位，3 级页号，也占 10 位，相应的这样的话我们就需要再建立更高一级的页表，最终会形成三级页表的一种结构。三级页表的原理和两级页表的原理其实是一模一样的，这个地方就不再展开赘述。
这个地方假如说我们只是采用了两级页表的结构的话，那么低级的页号就会占 18 位，也就是说在页目录表当中最多有可能会有二的 18 次方个页表项，这么多的页表项显然是不能放在一个页面里的，所以这就违背了采用多级页表的时候，各级页表的大小不能超过一个页面这样的条件，因此如果我们只把它分成两级是不够的，这就是我们需要注意的第一个细节，很有可能作为考点在选择题，甚至是结合大题来进行考察。
第二个我们需要注意的点是两级页表的访存次数的分析。
两级页表的访存次数分析（假设没有快表机构）
- 第一次访存：访问内存中的页目录表
- 第二次访存：访问内存中的二级页表
- 第三次访存：访问目标内存单元
假设我们没有采用快表机制的话，那么第一次访存应该是访问内存当中的页目录表，也就是顶级页表。第二次访存应该是访问内存当中的二级页表，第三次访存才是访问最终的目标内存单元，所以采用两级页表结构的话，我们要访问一个逻辑地址，需要进行三次访存。
那还记得我们分析的单级页表的访存次数问题吗？如果采用的是单级页表结构的话，那么第一次访存就是查询页表第二次访存，访问我们最终想要访问的内存单元，所以单级页表在访问一个逻辑地址的时候，只需要进行两次访存。因此两级页表虽然解决了我们之前提出的单极页表的那两大问题，但是这种内存空间的利用率的上升，付出的代价就是逻辑地址变换的时候需要进行更多一次的访存，这样的话就会导致我们要访问某一个逻辑地址的时候，需要花费更长的时间，所以这是 2 级页表相比于单级页表来说的一个很明显的缺点。如果我们继续分析 3 级页表 4 级页表结构当中的访存次数的话，会发现 3 级页表访问一个逻辑地址需要访存 4 次，4 级页表需要缓存 5 次，5 级页表需要缓存 6 次，所以其实有 1 个规律，如果是没有快表机构的话，那么 n 级页表在访问一个逻辑地址的时候，访存次数应该是 n+1 次，这就是我们需要注意的两个很重要的小细节。
# 小结
那么小节当中我们介绍了两级页表相关的知识点，我们从单极页表存在的两个问题出发，来依次探讨了这两个问题应该怎么解决，特别是第一个
采用了两级页表结构之后，我们就可以解决第一个问题，但是第二个问题的解决需要采用虚拟存储技术，咱们会在之后的小节进行更详细的讲解。在本节当中我们需要重点理解两级页表的逻辑地址结构，还需要注意页目录表、外层页表顶级页表这几个说法，不过在 408 当中最常用的是页目录表术语。
另外大家也需要理解采用了两级，页表之后如何实现逻辑地址到物理地址的转换，转换过程其实和咱们之前介绍的单极页表并没有太大的差异，无非就是还需要多查一级的页表而已，这个过程需要能够自己分析。
最后我们强调了两个我们需要注意的小细节，第一个小细节，多级页表当中各级页表的大小不能超过一个页面，所以说如果两级页表不够的话，那么我们可以进行更多的分级。第二个小细节，我们也需要自己能够分析多级页表的访存次数， n 极页表访问一个逻辑地址是需要 n+1 次访存的。
另外大家还需要能够根据题目给出的逻辑地址、位数、页面大小、页表项大小，这几个条件来确定多级页表的逻辑地址结构，这些内容还需要大家结合课后习题来进行巩固和消化
