[操作系统笔记]两级页表

内容系听课复习所做笔记，图例多来自课程截图

单级页表存在的问题

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

可推知：

• 页面大小$4KB=2^{12}B$，故页内地址12位
• 页号有32-12=20位，即最多$2^{20}$页，对应$2^{20}$个页表项
• $2^{20}$个页表项需要$2^{22}$B存储（页表项长度4B）
• $2^{20}$个页表项需要$2^{10}$个页框（$2^{22}/2^{12}$）

需要连续的$2^{10}$大小的空间来存储页表，这样的“连续分配”与离散分配的思想相悖

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

解决方案

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

然后再以离散分配的每组页表为单位，建立一张页表，称为页目录表，或称外层页表，或称顶层页表

查询过程

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

---

页面未必非得全在内存中（用到再调入也不是不行），给页表加一项，记录是否在页面中就可以了。若想访问的页面不在内存中，则产生缺页中断（内中断），然后将目标页面从外存调入内存

题目

各级页表大小均不得超过一个页面

没有快表的情况下，n级页表访问内存次数为n+1次