3.1_6 基本地址变换机构

提示：

  重点理解、记忆**基本地址变换机构（即用于实现逻辑地址到物理地址转换的一组硬件机构）**的原理和流程。

（一）基本地址变换机构

  基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

  通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。

  进程未执行时，页表的始址 和 页表长度 **放在进程控制块（PCB）**中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

  注意：页面大小是2的整数幂。

---

  设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

  我们知道，操作系统会把内存分为系统区、用户区。在系统区当中，会存放着一些操作系统对整个计算机软硬件进行管理的一些相关的数据结构（包括进程控制块PCB，也是在系统区当中的）。

  如果一个进程被调度、需要上处理机运行的话，进程切换相关的内核程序就会把这个进程的运行环境给恢复（这个进程运行环境的相关信息本来是保存在PCB当中的）。内核程序会把进程相关信息放到一系列寄存器当中（包括页表寄存器）。页表寄存器当中存放着这个进程的页表起始地址，和页表的长度。程序计数器PC也是需要恢复的，它指向下一条指令的逻辑地址A。

  采用分页存储管理方式的系统当中，逻辑地址的结构肯定是固定不变的。（比如总长度是32位，前xx位是页号，后xx位是页内偏移量）在一个逻辑地址里，页号占多少位、页内偏移量占多少位，这些都是操作系统知道的。

  所以，获得逻辑地址A之后，就能很快地切分出页号P、页内偏移量W。

  接下来，会对页号的合法性进行检查。

  一个进程的“页表长度M”表示在这个进程的页表中，有M个页表项，也就意味着这个进程的页面总共有M页。

  那么，此时逻辑地址所表示的“页号P”，如果已经超过了页面长度M，即进程总共页面的数量，那么，我们就认为，此时要访问的这个逻辑地址是非法的。

  如果页号P是合法的，那么接下来会拿着页号，和页表始址F结合起来，计算这个页号在页表中所对应的页表项到底是多少。

  通过之前的讲解，我们知道，页表当中的每一个页表项的长度其实是相同的。所以只要我们知道了页号，还有页表起始地址，再知道每一个页表项的长度，我们就可以算出我们想要访问的页号对应的页表项所存放的位置，就知道了它对应的块号。

  既然知道它的内存块号，那么，再结合页内偏移量W，就能得到最终的物理地址E了。

  最终，就成功访问到了“逻辑地址A”所对应的物理地址了。

  在考试当中，经常会：给出一个逻辑地址，还有页表。之后让我们算出它的物理地址。

  所以，需要对上面所说的过程（主要是图中的5个步骤）非常的熟悉。

---

文字性概括：

  设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

  1.计算页号P和页内偏移量W。

  如果用十进制手算，则P = A / L，W = A % L。

  但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量。

  2.比较页号P和页表长度M，若P ≥ M，则产生越界中断，否则继续执行。

  注意：页号是从0开始的，而页表长度至少是1。因此P = M时也会越界。

  3.页表中页号P对应的页表项地址 = 页表起始地址F + 页号P * 页表项长度，取出该页表项内容b，即为内存块号。

  注意区分：页表项长度、页表长度、页面大小的区别。

  页表长度指的是这个页表中总共有几个页表项，即总共有几个页；

  页表项长度指的是每个页表项占多大的存储空间；

  页面大小指的是一个页面占多大的存储空间。

  4.计算E = b * L + W，用得到的物理地址E去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了）

  动手验证：假设页面大小L=1KB，最终要访问的内存块号b=2，页内偏移量W=1023。

  ①尝试用E = b * L + W计算目标物理地址。

  ②尝试把内存块号、页内偏移量用二进制表示，并把它们拼接起来得到物理地址。

  对比①②的结果是否一致。

---

例题

  若页面大小L为1K字节，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E。

  等价描述：某系统按字节寻址，逻辑地址中，页内偏移量占10位，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E。

  “按字节寻址”就意味着，在这个系统中，每个地址对应的是1个字节大小的存储单元。

  “页内偏移量占10位”的信息也很重要，因为页内偏移量的位数直接决定了一个页面的大小是多少。此处，说明一个页面的大小为$2^{10}B=1KB$。

  读完题目之后，对于“逻辑地址到物理地址的转换”这样的题目，我们就根据上文所总结的思路来做即可。

答：

  1.计算页号、页内偏移量。

  题中给的数据也都是十进制的，我们正常使用除法、取余进行计算即可。、

  页号P = A / L = 2500 / 1024 = 2；

  页内偏移量W = A % L = 2500 % 1024 = 452。

  2.根据题中条件可知，页号2对应的内存块号b=8。

  同时页号P=2也是没有越界的。

  3.物理地址E = B × L + W = 8 × 1024 + 425 = 8644。

  我们知道了内存块号、页内偏移量，也知道每个内存块的大小（与进程的页面大小一样），就可以计算物理地址了。

  注意，内存块号是通过查询页表，根据页号对应得知的。此外，不要忘了内存当中的内存块大小与进程的页面大小是一样的。

  在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

（二）对页表项大小的进一步探讨

  每个页表项的长度是相同的，页号是“隐含”的。

例子

  假设某系统物理内存大小为4GB，页面大小为4KB，它的内存总共会被分为$2^{32}/2^{12}=2^{20}$个内存块，因此内存块号的范围应该是0 ~ $2^{20}-1$。

  因此，至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才足够。（每个字节是8个二进制位）

  则页表中的“块号”就需要3个字节来存储。此外，页号并不需要存储，页号是“隐含”的。因此，即每个页表项的大小为3字节。

  各页表项会按顺序连续地存放在内存中。如果该页表在内存中存放的起始地址是X，则M号页对应的页表项是存放在内存地址为X + 3 * M。

  但是，进一步思考一个问题。回到本例的第一句话上，它说一个页面为4KB，则每个页面可以存放4096 / 3 = 1365个页表项，但是（除不尽，有余数）这个页面会剩余4096 % 3 = 1B页内碎片。

  我们从起始地址X开始存放页表项。由于每个页面可以存放1365个页表项，则如图所示，第一个页面存放了0 ~ 1364号，这1365个页表项，且页面中剩余1B的页内碎片。而继续存下一个页表项，即1365号页表项时，由于不能跨页存储，其只能从下一个页框（内存块）开始存放，因此那1B的碎片空间只能放在那。

  同时，对于1365号页表项的起始地址的计算，也会有变化，不能再按照X + 3 * M了，而是要额外再加上1B。因此，1365号页表项存放的地址为X + 3 * 1365 + 1。

  由此可见，如果页表项大小的设置不合理，导致页表项不能恰好装满一个页框的话，就会对我们计算页表项地址带来麻烦。

  为了解决这个问题，我们可以适当的把每个页表项的长度拓展一下。如果每个页表项占4字节，则每个页框刚好可存放1024个页表项，不会有任何的页内碎片。

  此外，1024号页表项虽然是存放在下一个页框中的，但是它的地址依然可以直接用X + 4 * 1024得出。

结论

  理论上，页表项长度为3B即可表示内存块号的范围。但是，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。

  注意：题目中如果让我们计算“页表项的长度最少是几？”——当然虽少是3字节，不能再比3字节少了，再少就存不下了，而不能说“长度最少是4字节”，因为3字节也可以存的下，4字节当然不是“最少”。之所以设置成4字节大小，目的是为了在实际应用当中方便而采用的一种策略。4字节当然不是“最少”的长度。

  此外，一个页表的页表项数目较多的话，需要放在多个页框中，我们通常会让它们装在连续的页框中。这也是为了方便我们计算页表项的存储地址。

总结