简单易懂，两级页表（多级页表）

两级页表 (Two-Level Page Table)。这是对基本分页管理的一次“降维打击”，把一个大问题分解成了多个小问题。

我们继续用那个写论文和活页本的比喻，但这次，你的论文是一部鸿篇巨著，比如一部《大英百科全书》。

• 进程：一部《大英百科全书》。
• 逻辑地址空间：这部百科全书的全部内容，非常庞大。
• 页面：百科全书被切割成的标准大小的页面。
• 内存：一本物理的活页本。
• 页框：活页本里的一张张物理纸。

1. 单级页表遇到的两大难题

如果这部《大英百科全书》非常厚，那么它的**目录（单级页表）**本身也会变得非常厚，甚至比其中任何一卷正文还要厚。这就带来了两个严重的问题：

1. 目录必须连续存放：按照基本分页的原理，这个巨大的目录需要被存放在一连串连续的物理活页纸（页框）上。你可能需要找20张连续的空白纸才能放下整个目录。这与我们采用分页存储的初衷——“利用离散的碎片空间”——背道而驰。为了存放一个“目录”，反而需要一次大的连续空间分配，这太讽刺了。

2. 目录必须全部在场：根据局部性原理，你在某一个小时内，可能只会查阅“字母B”开头的词条。这意味着，你只需要目录中关于“B”的那几页。但按照基本分页的原理，整本厚厚的目录都必须放在活页本（内存）里，占用了大量宝贵的空间，而其中大部分页面（比如“字母Z”的目录）根本没被用到。

2. 两级页表的解决方案：给目录再做个目录！

面对这个“目录太大”的问题，我们想出了一个绝妙的办法：把管理正文的方法，用来管理目录本身！

1. 分割大目录：我们把那本厚厚的总目录，也按照活页纸的大小，切割成一小份一小份的“分目录”。比如，A-C的目录是一份，D-F的目录是另一份... 每一份“分目录”的大小，恰好可以放满一张物理活页纸。

2. 创建“目录的目录”：现在，我们有了一堆离散的“分目录”。为了把它们组织起来，我们再创建一个更高级的、薄薄的“总览目录”，我们叫它页目录表 (Page Directory)。

   • 这个“页目录表”里，每一行记录的不再是正文的位置，而是一份“分目录”被放在了活页本的第几张纸上。

这样，我们就形成了一个两级结构：

• 一级页表（页目录表）：指向二级页表。
• 二级页表（普通的页表）：指向真正的物理页面。

3. 两级页表的逻辑地址结构与地址变换

为了支持这种两级查找，我们的逻辑地址也需要被重新划分。

• 单级页表逻辑地址：| 页号P | 页内偏移量W |
• 两级页表逻辑地址：| 一级页号P1 | 二级页号P2 | 页内偏移量W |

地址变换过程（智能秘书的升级版工作流）：

你（CPU）发出指令：“我要找逻辑地址 A 处的内容！”

1. 拆分指令：秘书拿到逻辑地址A，将其拆分成三部分：一级页号P1，二级页号P2，页内偏移量W。

2. 第一步查找：查“总览目录”（访问页目录表）：

   • 秘书从一个特殊的页目录基址寄存器 (PDBR) 中知道“总览目录”的起始位置。
   • 他用P1作为索引，去“总览目录”里查找，第一次访问内存，得到一份**“分目录”（二级页表）**的存放地址。

3. 第二步查找：查“分目录”（访问二级页表）：

   • 秘书根据上一步得到的地址，找到了对应的“分目录”。
   • 他再用P2作为索引，在这个“分目录”里查找，第二次访问内存，最终得到存放正文内容的那一页的物理块号b。

4. 拼接地址，找到最终目标：

   • 秘书用得到的物理块号b和页内偏移量W，计算出最终的物理地址。
   • CPU第三次访问内存，去读取真正的数据。

4. 两级页表如何解决那两个难题？

1. 解决了连续存放问题：现在，只有那个小小的“页目录表”需要连续存放（通常它也很小，能放在一个页框里）。而大量的“二级页表”可以被离散地存放在内存的任何空闲页框中。这完美地贯彻了分页的思想。

2. 为解决“全部在场”问题提供了可能：我们可以只把“页目录表”和当前需要的少数几个“二级页表”放入内存。如果访问到一个逻辑地址，其对应的二级页表不在内存中，就会触发一个缺页中断（这属于虚拟存储的范畴）。操作系统再把需要的那个二级页表从硬盘调入内存。这样就无需让整个页表体系常驻内存了。

5. 考试中的重要细节

• 多级页表的大小限制：一个核心设计原则是，每一级的页表，其自身的大小都不能超过一个物理页框的大小。这样才能把它作为一个“页面”来管理。

  • 如何判断级数？
    1. 计算一个页表项的大小（比如4B）。
    2. 计算一个页面能存放多少个页表项（比如页面大小4KB，则 4KB / 4B = 1K = 1024 个）。
    3. 这个数量1024，就是一级页表能管理的下一级页表（或页面）的最大数量。
    4. 如果一个进程的逻辑地址空间所需页面总数超过了这个值，就需要多级页表。比如需要1024 * 1024个页面，就需要两级页表。

• 访存次数：

  • 在没有快表的情况下，访问一次逻辑地址，需要先访问各级页表，最后再访问数据。
  • 单级页表：1次查页表 + 1次访数据 = 2次。
  • 两级页表：1次查页目录 + 1次查页表 + 1次访数据 = 3次。
  • n级页表：需要 n+1 次内存访问。
  • （当然，在有快表的情况下，如果命中，就永远只需要1次访存。）

必会题与详解

题目一：在一个32位地址的系统中，采用两级页表，页面大小为4KB，页表项大小为4B。请问，逻辑地址是如何划分的？

答案详解：

1. 计算页内偏移量位数：

   • 页面大小 = 4KB = 2^12 B。
   • 因此，页内偏移量占 12 位。

2. 计算一个页面能存放多少个页表项：

   • 页面大小 / 页表项大小 = 4KB / 4B = (2^12) / (2^2) = 2^10 = 1024 个。
   • 这意味着，无论是页目录表，还是二级页表，每一张表最多只能有1024个条目。

3. 计算各级页号的位数：

   • 要索引1024个条目，需要 log2(1024) = 10 位地址。
   • 因此，二级页号需要 10 位。
   • 同理，一级页号也需要 10 位。

4. 验证总位数：

   • 一级页号位数 + 二级页号位数 + 偏移量位数 = 10 + 10 + 12 = 32 位。与总地址位数吻合。

结论：逻辑地址被划分为 | 10位一级页号 | 10位二级页号 | 12位页内偏移量 |。

题目二：采用多级页表结构，最主要解决了单级页表的什么问题？它是如何解决的？

答案详解：

多级页表最主要解决了单级页表本身必须占用巨大、连续的物理内存空间的问题。

解决方法：

1. 多级页表采用了“分而治之”的思想，将原本一个巨大的、线性的页表，分割成了多个小的页表（称为二级页表、三级页表等）。
2. 这些小的页表，每一个的大小都被设计为不超过一个物理页框，因此它们可以像普通的用户页面一样，被离散地存储在内存中任何可用的页框里。
3. 然后，再用一个顶层的页表（页目录表）来管理这些分散的小页表的位置。
4. 通过这种方式，原本需要一块巨大连续内存的需求，被转化为了对多个离散的小块内存的需求，这与分页存储管理“利用碎片空间”的核心思想完全一致，大大提高了内存分配的灵活性。

题目三：假设一个系统采用两级页表，且没有快表。当CPU访问一个逻辑地址时，需要进行几次内存访问？请说明每次访问的目的。

答案详解：

在没有快表的情况下，采用两级页表，访问一个逻辑地址总共需要 3次 内存访问。

1. 第一次访存：访问页目录表（一级页表）。

   • 目的是：根据逻辑地址中的一级页号，查询页目录表，以获取存放目标二级页表的那个页框的物理地址。

2. 第二次访存：访问二级页表。

   • 目的是：根据上一步得到的地址，访问对应的二级页表。再根据逻辑地址中的二级页号，查询这个二级页表，以获取存放目标数据页面的那个页框的物理块号。

3. 第三次访存：访问目标数据单元。

   • 目的是：将上一步得到的物理块号和逻辑地址中的页内偏移量组合成最终的物理地址，然后访问这个地址，读取或写入真正需要的数据。