3.2 基本分页存储管理

页面与页框、页面大小与地址结构；页表与页表寄存器，基本地址变换过程；具有快表的地址变换与有效访问时间；两级页表与多级页表的结构和计算。

分页的基本概念

固定分区有内部碎片，动态分区有外部碎片。分页的思想是：把内存划分为大小相等且固定的块（页框，也称页帧、物理块），把进程的逻辑地址空间也划分为与块大小相等的页面（页）。进程以页为单位申请内存，每个页面可以离散地放入任意一个页框中，这样就不会产生外部碎片，只在每个进程的最后一页会有不到一页的内部碎片。

• 页面大小：通常是 2 的整数次幂，如 4 KB。页面太小会使页表过长、占用大量内存，也会增加换页的开销；页面太大会使页内碎片增多，降低内存利用率；
• 地址结构：逻辑地址由页号 P 和页内偏移量 W 组成。若页面大小为 L = 2ᵏ，则逻辑地址的低 k 位为页内偏移，其余高位为页号。例如 32 位地址、4 KB 页面，页号 20 位、页内偏移 12 位，一个进程最多 2²⁰ 页。

给定逻辑地址 A（十进制）和页面大小 L，页号 P = ⌊A / L⌋，页内偏移 W = A mod L；若 A 用十六进制或二进制给出，直接按位截取即可。

页表

为了找到每个页面在内存中对应的物理块，系统为每个进程建立一张页表，记录页号与物理块号的对应关系。页表一般存放在内存中，每个页面对应一个页表项，页表项由页号和块号组成（页号是隐含的，即页表项的序号，不占存储空间）。

基本地址变换机构

系统中通常设置一个页表寄存器（PTR），存放页表在内存中的起始地址 F 和页表长度 M。进程未执行时，这两个值存放在 PCB 中；进程被调度执行时，才把它们装入页表寄存器。

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

1. 计算页号 P = A / L 和页内偏移 W = A % L；
2. 比较页号 P 和页表长度 M，若 P ≥ M，则产生越界中断；
3. 页表中页号 P 对应的页表项地址 = 页表起始地址 F + P × 页表项长度，取出该页表项的内容 b，即物理块号；
4. 物理地址 E = b × L + W。

整个过程由硬件自动完成。分页管理中，页内偏移的大小一定小于页面大小，所以只需检查页号是否越界。没有快表时，访问一个逻辑地址要访问两次内存：第一次访问页表，第二次访问目标数据。

具有快表的地址变换机构

为了提高地址变换的速度，在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器——快表（TLB，相联存储器），存放当前访问的若干页表项；内存中的页表相应地称为慢表。

1. CPU 给出逻辑地址后，由硬件进行地址转换，把页号送入快表，与快表中的所有页号并行比较；
2. 若找到匹配的页号（命中），直接取出该页对应的块号，与页内偏移拼接成物理地址，只需访问一次内存；
3. 若未命中，则访问内存中的页表，读出页表项后，同时把它存入快表，以便后面可能的再次访问。若快表已满，则按一定的算法替换一个旧的页表项。

根据局部性原理，快表的命中率一般可达 90% 以上。设快表访问时间为 t、访存时间为 m、命中率为 h，若先查快表、未命中再查页表，则有效访问时间

若快表和慢表同时查找，则未命中时的时间为 2m。

两级页表

假设 32 位逻辑地址、页面大小 4 KB、页表项 4 B，则每个进程的页表最多有 2²⁰ 项，占 4 MB，而且必须连续存放，这显然不现实。而且根据局部性原理，进程在一段时间内只需访问少数几页，没有必要让整个页表常驻内存。

解决办法是对页表本身也进行分页：把页表分散存放在若干个页框中，再建立一张页目录表（外层页表、顶级页表），记录各个页表分页所在的物理块号。逻辑地址结构变为：

地址变换时，先用一级页号查页目录表，得到二级页表所在的物理块，再用二级页号查二级页表，得到数据所在的物理块。没有快表时，两级页表需要访问内存三次（页目录表、二级页表、数据）；一般地，n 级页表要访存 n + 1 次。

即时练习