3.1 分页存储相关概念

1、数据结构——页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

• 一个进程对应一张页表

• 页表通常存在PCB中，使用专门的页表基址寄存器存放

• 进程的每个页面对应一个页表项

• 每个页表项由页号和块号组成

• 页表记录进程页面和实际存放的页框之间的映射关系

页表项大小的计算

Eg：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节?

• 内存块大小=页面大小=4KB=$2^{12}$B

• 4GB的内存总共会被分为 $2^{32}/2^{12}=2^{20}$个内存块

• 内存块号的范围应该是 $0 \sim 2^{20} -1$

• 内存块号至少要用20bit来表示

• 至少要用3B来表示块号(3* 8=24bit)

每一个页表项中，块号占上述空间，页号不占存储空间（页表项是连续存放的，只要知道起始地址，即可推算出某个块的地址）

2、逻辑地址的转换

虽然进程的各个页是离散存放的，但是页面的内部是连续的。

要访问逻辑地址A，步骤一般如下：

1. 确定逻辑地址A对应的页号P（页号P = 逻辑地址 / 页面长度）

2. 找到P号页面在内存中的起始地址（P号页框的起始地址 = P * 页框大小）

3. 确定逻辑地址A的页内偏移量（页内偏移量 = 逻辑地址 % 页面长度）

则，逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量。

• 如果每个页面大小为 $2^{K}$B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号。
• 如果页面大小是2的整数次幂，则直接将页框的起始地址和页内偏移量拼接，即可得到对应的物理地址。

如果有K位表示页内偏移量，则说明该系统中一个页面的大小是 $2^{K}$ 个内存单元

如果有M位表示页号，则说明在该系统中，一个进程最多允许有 $2^{M}$ 个页面

3、基本地址变换机构

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

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。 进程未执行时，页表的始址和页表长度放在**进程控制块(PCB)**中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

根据逻辑地址访问内存单元的流程：

1. 根据逻辑地址计算出页号、页内偏移量

2. 判断页号是否越界（页号应当小于页表长度）

3. 查询页表，找到页号对应的页表项，确定页面的内存块号

4. 用内存块号和页内偏移量得到物理地址

5. 根据物理地址访问内存单元

页表长度：这个页表中总共有几个页表项，即总共有几个页；

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

页面大小：一个页面占多大的存储空间

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

这里页面大小1K也可以描述为“按照字节编址，页内偏移量占10位”

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

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

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

2. 由题可知，页号2没有越界，且内存块号为8

3. 求物理地址

   • 物理地址：E = b * L + W = 8 * 1024 + 452 = 8644

**页式管理中地址是一维的。**在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。只需要给出逻辑地址，计算机就可以得出页号、页内偏移量。

4、具有快表的地址变换机构

快表，又称联想寄存器（TLB，Translation Lookaside Buffer），是一种访问速度比内存快很多的高速缓存（TLB不是内存），用来存放最近访问的页表项的副本，可以加速地址变换的速度。

与此对应，内存中的页表常称为慢表。

• 每一次切换进程时处理机会清空快表

• 在检查完页号是否越界后会尝试访问快表中的副本，若命中，则直接得到内存块号

• 否则，正常查询，并在找到页表项之后将其存入快表

• 快表少了一次内存访问

例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1us,访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少?

$(1+100) * 0.9+ (1+100+100) * 0.1 = 111 us$

注意题目中是否支持快慢表一起查询

5、两级页表

单级页表的问题：

1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框

2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面（局部性原理）

通过将页表进行分组，例如使得每一组恰好装入一个内存块，并对这些分组后的页表再建立一个页表用于查询。分别称为一级页表（页目录表\顶级页表\外层页表）、二级页表、三级页表等。

例：某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用（ ）级页表，页内偏移量为（ ）位?

1. 分析数据

   • 页面大小 = 4KB = $2^{12}$B
   • 页表项大小 = 4B = $2^{2}$B
2. 求页号、页内偏移量

   • 页内偏移量 = 12

   • 页号位数 = 40 - 12 = 28

   • 每一页内可存放的表项：页面大小 / 页表项大小 = $2^{10}$
   • 剩余的28位可以分为8+10+10，即三级页表

当快表不存在时，页表级数越多、访存次数越大。