分页存储管理

基本原理

  1. 逻辑空间划分：将进程的逻辑地址空间划分为若干个大小相等的区域，称为 页 (Page)，并从 0 开始连续编号。
  2. 物理空间划分：将物理内存空间划分为与页大小相等的区域，称为 物理块 或 页框 (Frame)，同样从 0 开始连续编号。

为了实现从逻辑页到物理块的映射，系统为每个进程建立一张 页表 (Page Table)。

  • 作用：记录进程的每个页存放在哪个物理块中。
  • 存储位置：页表本身通常存放在内存中。
  • 寻址方式：通过 页表寄存器 (PTR) 定位，该寄存器存放页表的基地址和长度。
  • 性能影响：每次访问逻辑地址都需要 两次内存访问（一次访问页表获取块号，一次访问目标数据），导致执行速度显著下降。

地址结构与变换

逻辑地址结构

逻辑地址通常由 页号 (P) 和 页内偏移 (w) 两部分组成。

  • 示例：在一个 32 位地址空间、页面大小为 4KB ($2^{12}$B) 的系统中：
    • 0-11 位：页内偏移 (w)，共 12 位，决定了页面大小为 4KB。
    • 12-31 位：页号 (P)，共 20 位，表示逻辑地址空间最多可有 $2^{20}$ (即 1M) 个页面。

若给定逻辑地址 A 和页面大小 L，则：

  • 页号 P = INT(A / L)
  • 页内偏移 w = A MOD L

例：页面大小为 1KB (1024B)，逻辑地址 A = 2170。

  • P = INT(2170 / 1024) = 2
  • w = 2170 MOD 1024 = 122

地址变换过程

地址变换机构的任务是将逻辑地址转换为物理地址，其核心是利用页表完成 页号 到 块号 的转换。

性能问题与快表 (TLB)

分页机制导致每次访存都需要两次内存操作，性能减半。为解决此问题，引入了硬件支持——快表。

快表 (Translation Lookaside Buffer, TLB)

快表是一种基于程序 局部性原理 设计的特殊高速缓存，也称 联想寄存器。

  • 内容：缓存了页表中的部分常用条目（页号 → 块号）。
  • 工作流程：
    1. CPU 产生逻辑地址后，首先在 快表 中查找页号。
    2. 命中 (Hit)：若在快表中找到，直接获取对应的物理块号，与页内偏移组合成物理地址。只需一次快表访问和一次内存访问。
    3. 未命中 (Miss)：若未找到，则需访问内存中的 页表，找到对应的物理块号，然后将该页表项 存入快表（若快表已满，则按替换算法淘汰一项）。此过程需要一次快表访问和两次内存访问。

引入快表后的有效访问时间 (EAT)

假设快表命中率为 p，访问快表时间为 t_tlb，访问内存时间为 t_mem，则有效访问时间为：

EAT = p × (t_tlb + t_mem) + (1 - p) × (t_tlb + 2 × t_mem)

多级页表

对于 32 位系统，若页面为 4KB，页表项为 4B，则一个进程的页表最大需要 2^20 * 4B = 4MB 的连续内存空间，这非常巨大。对于 64 位系统，单级页表的空间开销更是无法接受。

为解决此问题，引入了 多级页表 机制。其核心思想是 对页表本身进行分页，将外层页表离散地存放在物理块中，并用更高一级的页表来索引它们。

逻辑地址结构（已补充完整）

在多级页表结构中，原有的页号部分被进一步划分为多个字段，对应不同级别的页表。

以 两级页表 为例，逻辑地址结构如下：

外层页号 (P1) 内层页号 (P2) 页内偏移 (w)

地址变换过程：

  1. 使用 外层页号 (P1) 作为索引，访问顶级页表，找到二级页表的基地址。
  2. 使用 内层页号 (P2) 作为索引，访问对应的二级页表，找到目标页面所在的 物理块号。
  3. 将获取的物理块号与 页内偏移 (w) 拼接，形成最终的物理地址。

这种方式的优点在于，二级页表只有在被需要时才创建和调入内存，极大地节省了内存空间。

例题解析

题目：一个计算机系统有 32 位虚拟地址空间和 20 位物理地址空间，采用两级页表机制，一级页表域（外层页号）长为 10 位，二级页表域（内层页号）长为 10 位。请问页面容量为多少？有多少个页框？

解答：

  1. 计算页面容量（页面大小）：

    • 虚拟地址总长度为 32 位。
    • 页号部分由两级构成：外层页号 (10 位) + 内层页号 (10 位) = 20 位。
    • 页内偏移位数 = 总位数 - 页号位数 = 32 - 20 = 12 位。
    • 因此，页面容量为 $2^{12}$ B = 4096 B (即 4KB)。

  2. 计算页框数量：

    • 物理地址空间总长度为 20 位，所以物理内存总大小为 $2^{20}$ B。
    • 页框大小与页面大小相等，即 4KB ($2^{12}$ B)。
    • 页框数量 = 物理内存总大小 / 页框大小 = $2^{20} / 2^{12} = 2^8$ = 256 个。