软考（软件设计师）存储管理—虚拟存储器管理，页面置换算法
虚拟存储器管理
一、基本概念与核心思想
1. 虚拟存储器定义
虚拟存储器是一种内存管理技术，它使应用程序认为自己拥有连续可用的内存（一个连续完整的地址空间），而实际上物理内存被分割成多个片段，部分暂时存储在外部磁盘上，在需要时进行数据交换。
2. 核心目标
- 地址空间扩展：提供比物理内存更大的地址空间
- 内存隔离：每个进程拥有独立的虚拟地址空间
- 内存共享：允许多个进程共享内存区域（如共享库）
- 内存保护：防止非法内存访问
3. 关键原理
- 按需调页：只在需要时加载页面到内存
- 页面置换：当内存不足时选择页面换出
- 局部性原理：
- 时间局部性：最近访问的页面可能再次被访问
- 空间局部性：访问某位置后，其附近位置也可能被访问
二、地址转换机制
1. 页表结构（32位系统典型）
┌──────────────────────┬──────────────────────┬──────────────────┐
│ 页目录索引 (10位, PDE) │ 页表索引 (10位, PTE) │ 页内偏移 (12位) │
└──────────────────────┴──────────────────────┴──────────────────┘
2. 页表项结构
typedef struct {uint32_t present:1; // 页是否在内存中uint32_t rw:1; // 读写权限 (0=只读, 1=读写)uint32_t user:1; // 访问权限 (0=内核, 1=用户)uint32_t accessed:1; // 访问标志位uint32_t dirty:1; // 修改标志位uint32_t reserved:7; // 保留位uint32_t frame:20; // 物理页框号
} page_table_entry_t;
3. 地址转换流程
三、关键技术与算法
1. 页面置换算法
(1) 最佳置换(OPT)
原理**：置换未来最长时间不会被访问的页面（理想算法，需预知未来访问序列）
流程：
例子：
- 访问序列：
2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 - 内存块数：3
- 置换过程（⭐ 表示缺页）：
| 访问 | 内存状态 | 说明 |
|---|---|---|
| 2 | [2] | ⭐ |
| 3 | [2,3] | ⭐ |
| 2 | [2,3] | 命中 |
| 1 | [2,3,1] | ⭐ |
| 5 | [2,3,5] | ⭐ 置换1（未来不再访问） |
| 2 | [2,3,5] | 命中 |
| 4 | [2,3,4] | ⭐ 置换5（下次访问最晚） |
| 5 | [5,3,4] | ⭐ 置换2（未来最晚访问） |
| 3 | [5,3,4] | 命中 |
| 2 | [5,3,2] | ⭐ 置换4（不再访问） |
| 5 | [5,3,2] | 命中 |
| 2 | [5,3,2] | 命中 |
缺页次数：6 次
(2) LRU(最近最少使用)
核心思想：基于时间局部性原理，认为最近使用过的页面很可能被再次使用，优先置换最长时间未被访问的页面。
算法流程
关键实现方式
-
链表法（常用）
- 双向链表：头节点存放最近使用的页面，尾节点存放最久未使用的页面
- 哈希表：快速定位页面在链表中的位置
- 操作：
- 访问页面 → 移动到链表头部
- 置换页面 → 删除链表尾部
-
计数器法
- 每个页面关联一个时间戳
- 置换时选择时间戳最小的页面
示例演示
访问序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3
内存帧数：3
逐步执行过程
| 访问 | 内存状态（链表头→尾） | 操作 | 说明 |
|---|---|---|---|
| 7 | [7] | 加载7 | 缺页 |
| 0 | [0, 7] | 加载0 → 0移到头部 | 缺页 |
| 1 | [1, 0, 7] | 加载1 → 1移到头部 | 缺页 |
| 2 | [2, 1, 0] | 加载2 → 置换尾节点7 | 缺页，置换7 |
| 0 | [0, 2, 1] | 0已存在 → 移到头部 | 命中 |
| 3 | [3, 0, 2] | 加载3 → 置换尾节点1 | 缺页，置换1 |
| 0 | [0, 3, 2] | 0已存在 → 移到头部 | 命中 |
| 4 | [4, 0, 3] | 加载4 → 置换尾节点2 | 缺页，置换2 |
| 2 | [2, 4, 0] | 加载2 → 置换尾节点3 | 缺页，置换3 |
| 3 | [3, 2, 4] | 加载3 → 置换尾节点0 | 缺页，置换0 |
缺页次数：9次访问中发生7次缺页
命中位置：访问0（第5次）和访问0（第7次）命中
算法特点
| 优点 | 缺点 |
|---|---|
| 1. 缺页率接近OPT（实际最优算法之一） | 1. 硬件实现复杂（需记录访问顺序） |
| 2. 符合程序局部性原理 | 2. 链表操作开销大（每次访问需移动节点） |
| 3. 无Belady异常 | 3. 时间戳法需维护全局计数器 |
(3) FIFO（先进先出算法）
原理：置换最先进入内存的页面（队列实现）
流程：
例子：
- 访问序列：
2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 - 内存块数：3
- 队列状态（→ 表示队列顺序）：
| 访问 | 内存状态 | 队列顺序 | 说明 |
|---|---|---|---|
| 2 | [2] | 2→ | ⭐ |
| 3 | [2,3] | 2→3→ | ⭐ |
| 2 | [2,3] | 2→3→ | 命中 |
| 1 | [2,3,1] | 2→3→1→ | ⭐ |
| 5 | [3,1,5] | 3→1→5→ | ⭐ 置换2（队头） |
| 2 | [1,5,2] | 1→5→2→ | ⭐ 置换3（队头） |
| 4 | [5,2,4] | 5→2→4→ | ⭐ 置换1（队头） |
| 5 | [5,2,4] | 5→2→4→ | 命中 |
| 3 | [2,4,3] | 2→4→3→ | ⭐ 置换5（队头） |
| 2 | [2,4,3] | 2→4→3→ | 命中 |
| 5 | [4,3,5] | 4→3→5→ | ⭐ 置换2（队头） |
| 2 | [3,5,2] | 3→5→2→ | ⭐ 置换4（队头） |
缺页次数：9 次
(4) NUR（最近未使用算法，Clock 算法）
核心思想
基于页面的访问位（Reference Bit）实现，在 FIFO 框架 上增加 访问状态判断，优先置换既"老"又"未被使用"的页面。
核心组件
- 环形链表：按加载顺序链接所有内存页面
- 指针 (clock hand)：循环扫描链表的当前位置
- 访问位 (R-bit)：
1= 页面最近被访问过0= 页面最近未被访问
算法流程
关键规则
- 访问页面时：硬件自动将对应页面的 R-bit 置 1
- 置换选择：
- 遇到
R=1→ 给页面"第二次机会"（R 置 0），继续扫描 - 遇到
R=0→ 立即置换
- 遇到
示例演示
访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2
内存帧数：3
初始状态：内存空，指针指向帧0
逐步解析
| 访问 | 操作 | 内存状态 (R-bit) | 指针 | 说明 |
|---|---|---|---|---|
| 1 | 缺页加载 | [1:1] | ↑0 | 加载1，R置1 |
| 2 | 缺页加载 | [1:1, 2:1] | ↑1 | 加载2，R置1 |
| 3 | 缺页加载 | [1:1, 2:1, 3:1] | ↑2 | 加载3，R置1 |
| 4 | 缺页置换 | [1:0, 2:0, 4:1] | ↑0 | 扫描：1(R=1→0)→2(R=1→0)→3(R=1→0)→1(R=0) 置换1 |
| 1 | 缺页加载 | [1:1, 2:0, 4:0] | ↑1 | 扫描：2(R=0) 置换2 |
| 2 | 命中 | [1:1, 2:1, 4:0] | - | 访问2 → R置1 |
| 5 | 缺页加载 | [1:0, 5:1, 4:0] | ↑2 | 扫描：1(R=1→0)→2(R=1→0)→4(R=0) 置换4 |
| 1 | 命中 | [1:1, 5:1, 4:0] | - | 访问1 → R置1 |
| 2 | 缺页加载 | [1:0, 5:0, 2:1] | ↑0 | 扫描：1(R=1→0)→5(R=1→0)→2(装入) 置换5 |
扫描过程详解（访问4时）
- 指针从帧0（页面1）开始：
- 页面1：R=1 → 置0，指针移向帧1
- 帧1（页面2）：
- R=1 → 置0，指针移向帧2
- 帧2（页面3）：
- R=1 → 置0，指针移回帧0（环形）
- 帧0（页面1）：
- R=0 → 置换页面1，加载页面4
💡 注意：实际置换发生在第二次扫描到页面1时（此时R已被置0）
算法特点
| 优点 | 缺点 |
|---|---|
| 1. 实现简单（只需1个R-bit） | 1. 精度不如LRU |
| 2. 避免FIFO的Belady异常 | 2. 指针扫描可能引入小延迟 |
| 3. 开销远小于LRU（无需时间戳） | 3. 访问模式突变时表现不稳定 |
页面置换算法对比总表
| 算法 | 核心思想 | 优点 | 缺点 | 实际应用场景 |
|---|---|---|---|---|
| OPT | 置换未来最久不用的页面 | ▶ 理论最优缺页率 | ▶ 需预知未来序列（不可实现） | 算法研究基准 |
| FIFO | 置换最早进入的页面 | ▶ 实现简单（队列） ▶ 开销极低 | ▶ 存在Belady异常 ▶ 忽略访问频率 | 简单嵌入式系统 |
| NUR (Clock) | 环形扫描+访问位淘汰 | ▶ 逼近LRU效果 ▶ 硬件开销低 ▶ 无Belady异常 | ▶ 精度依赖扫描频率 ▶ 突发访问敏感 | 通用操作系统 (Linux/Windows) |
| LRU | 置换最久未使用的页面 | ▶ 实际最优缺页率 ▶ 符合局部性原理 ▶ 无Belady异常 | ▶ 实现复杂 ▶ 高频访问开销大 | 数据库/缓存系统 (Redis/MySQL) |
关键特性深度对比
1. 实现复杂度
2. 缺页率表现
3. 特殊现象处理
| 问题 | OPT | FIFO | NUR | LRU |
|---|---|---|---|---|
| Belady异常 | ❌ | ✅ | ❌ | ❌ |
| 缓存污染 | ❌ | ✅ | ⚠️ | ⚠️ |
| 扫描抵抗 | ✅ | ❌ | ✅ | ✅ |
💡 术语解释：
- Belady异常：分配更多内存帧时缺页率反而升高
- 缓存污染：低频访问页面挤出高频页面
- 扫描抵抗：应对顺序访问模式的能力
现代演进方向
-
LRU改进
- LRU-K：基于K次历史访问频率
- ARC：自适应LRU+FIFO混合
-
机器学习应用
- 预测未来访问模式（类OPT实现）
- 动态调整置换策略（如Google的ML-Cache）
📌 典型案例：
- Linux内核：NUR改进版（多级Clock链表）
- Redis：近似LRU（随机采样淘汰）
- Oracle DB：Touch-Count算法（访问频率加权）
为什么称为"二次机会"？
- 当页面被扫描到且
R=1时：- 不被置换 → 获得第二次生存机会
- 但R-bit被重置为0（"用掉"这次机会）
- 下次扫描时若仍未被访问（R=0），则被置换
📌 应用场景：Linux内核早期版本、Windows NT的物理页管理
2. 工作集模型
工作集 W(t, Δ) = 在时间间隔 [t-Δ, t] 内被访问的页面集合
3. 抖动(Thrashing)与解决方案
抖动现象：频繁的页面置换导致系统效率急剧下降
解决方案：
- 局部置换策略：每个进程限制最大页面数
- 工作集模型：确保进程有足够的工作集空间
- 负载控制：调整多道程序度
- 页面大小优化：针对不同应用调整页面大小