第六章 虚拟存储器
5 分钟阅读2,144 字31 个小节
第六章 虚拟存储器
6.1 虚拟存储器概述
局部性原理⭐
- 时间局部性：刚访问的单元不久会被再访问（循环）
- 空间局部性：刚访问的单元附近的单元不久会被访问（顺序执行）
传统存储管理特征 vs 虚拟存储器
| 特征 | 传统 | 虚拟 |
|---|---|---|
| 一次性 | 必须一次性全部装入 | 多次性：允许分多次调入 |
| 驻留性 | 一直驻留到结束 | 对换性：允许换入换出 |
| — | — | 虚拟性：逻辑扩大内存 |
虚拟存储器三大特征：多次性（最重要）、对换性、虚拟性 虚拟性以多次性和对换性为基础，多次性和对换性建立在离散分配方式上
虚拟存储器的实现方式
- 请求分页存储管理（最常用）：以页为单位换入/换出
- 请求分段存储管理：以段为单位换入/换出
6.2 请求分页存储管理方式
请求页表项
| 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 |
|---|
- P（存在位）：该页是否在内存中（1在/0不在）
- A（访问字段）：记录访问次数或多久未访问,供置换算法参考
- M（修改位/脏位）：该页是否被修改过,供换出时决定是否写回
- 外存地址：该页在外存的位置
缺页中断⭐
- 发生在指令执行期间（不同于一般中断在指令执行后检查）
- 一条指令可能产生多次缺页中断（极端情况下可达6次：指令本身跨页最多2次 + 源操作数跨页最多2次 + 目的操作数跨页最多2次）
内存分配策略
| 策略 | 分配 | 置换 | 适用/特点 |
|---|---|---|---|
| 固定分配局部置换 | 固定物理块数 | 从本进程页面中选换出 | 物理块数难确定 |
| 可变分配全局置换 | 可变 | 从所有进程中选换出 | 最易实现,但可能影响其他进程 |
| 可变分配局部置换 | 可变 | 从本进程中选换出,可动态增减 | 兼顾灵活和隔离 |
页框分配与回收（新增强化）
常见页框分配算法
- 等额分配：每个进程平均分配相同数量页框
- 比例分配：按进程大小（页数）比例分配页框
- 优先级分配：高优先级进程获得更多页框（缺页时可从低优先级进程回收）
回收策略要点
- 局部回收：仅在本进程驻留集中置换，隔离性好
- 全局回收：可跨进程选牺牲页，系统吞吐量高但会互相干扰
- 后台回收：系统在空闲或阈值触发时批量回收脏页并维护空闲页框池
考试常用结论：页框过少会触发抖动；页框分配和页面置换需配合工作集思想联合判断。
缺页率
影响因素：页面大小、分配的物理块数、页面置换算法、程序局部性
6.3 页面置换算法（⭐⭐⭐必考）
OPT（最佳页面置换算法）
- 淘汰未来最长时间不会被访问的页
- 最低缺页率，但不可实现（需预知未来）
- 用作评价其他算法的标准
FIFO（先进先出）
- 淘汰最早进入内存的页
- 实现简单（FIFO队列）
- Belady异常：增加物理块数反而缺页率上升！⭐
- 实际应用极少
LRU（最近最久未使用）⭐
- 淘汰最近最久未使用的页
- 向前看（基于历史）对比OPT向后看（基于未来）
- 性能接近OPT
- 需要硬件支持：移位寄存器 或 栈
⚠️ LRU不会出现Belady异常（属于"栈算法"类）
LFU（最少使用）
- 淘汰一段时间内使用次数最少的页
- 用移位寄存器记录访问频率
Clock（时钟/NRU）⭐
- 简单Clock：循环队列,每页一个访问位A
- 若A=0 → 换出
- 若A=1 → 置A=0,给第二次机会,检查下一页
- 又称二次机会算法/NRU（最近未用）
改进型Clock⭐
- 同时考虑访问位A和修改位M
- 四类页面优先级：
| 类别 | A | M | 含义 | 淘汰优先级 |
|---|---|---|---|---|
| 第1类 | 0 | 0 | 未访问,未修改 | 最优先淘汰 |
| 第2类 | 0 | 1 | 未访问,已修改 | 次优先 |
| 第3类 | 1 | 0 | 已访问,未修改 | 可能再被访问 |
| 第4类 | 1 | 1 | 已访问,已修改 | 最不应淘汰 |
扫描过程：
- 第1轮找(0,0)不改A
- 找不到则第2轮找(0,1)同时把扫过的A置0
- 还找不到则重复1-2（此时A都已为0,必能找到）
页面缓冲算法 PBA
- 设空闲页面链表+修改页面链表
页面置换手工模拟示例（⭐⭐⭐ 必练）
题目：3个物理块，访问串 ，分别用 FIFO 和 LRU 计算缺页次数。
FIFO（淘汰最早进入的页）：
访问 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 块1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 块2 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 块3 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 缺页 ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ FIFO 缺页 15 次，缺页率 = 15/20 = 75%
LRU（淘汰最近最久未使用的页）：
访问 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 块1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 块2 0 0 0 0 3 3 3 3 3 3 3 3 3 2 2 2 7 7 7 块3 1 1 1 1 0 0 2 2 2 2 2 2 2 0 0 0 0 0 缺页 ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ LRU 缺页 12 次，缺页率 = 12/20 = 60%
结论：LRU(12次) < FIFO(15次)，LRU性能更优且无Belady异常。
📝 答题提醒：画表时每一步标清"淘汰了谁"和"新换入谁"，缺页打 ✗ ，命中留空。
- 换出时不立即写盘,而是挂在链表上
- 后续需要该页时可直接从链表取回（避免磁盘I/O）
- 修改页面积累到一定数量后批量写盘
6.4 "抖动"与工作集
抖动（颠簸）
- 定义：进程大部分时间用于页面置换而非有效计算
- 原因：分配给进程的物理块太少
- 多道程序度过高→物理块不足→频繁缺页→I/O繁忙→CPU利用率下降
工作集 w(t, Δ)
- 定义：进程在时间间隔中实际访问的页面集合
- 为窗口尺寸
- 工作集大小是的非降函数
抖动预防方法
- 局部置换策略：限制影响范围
- 工作集算法融入调度：确保驻留集足够才调入新作业
- L=S准则：L(缺页间平均时间)≈S(平均缺页服务时间)时最优
- 挂起进程：减少多道程序度
6.5 请求分段存储管理
请求段表项
在普通段表项基础上增加：存取方式、访问字段A、修改位M、存在位P、增补位、外存地址
增补位
- 请求分段特有字段
- 表示该段在运行过程中是否做过动态增长
共享段表
- count（共享计数）：记录共享该段的进程数，count为0时才回收
- 存取控制：不同进程可有不同的读写权限
- 段号：不同进程中可有不同的段号
分段保护
- 越界检查：段号 vs 段表长度；段内地址 vs 段长
- 存取控制检查：只读/只执行/读写
- 环保护机构：低编号环=高特权，程序可调用内环服务，可访问外环数据
🎯 本章真题锚点与最短模板
- 高频题号（2009-2025）：2009Q46、2010Q46、2011Q28/Q29、2014Q30、2015Q27/Q30、2016Q26/Q29、2018Q45、2019Q29、2024Q45、2025Q25/Q28/Q29
- 优质例题：4页框下访问串
1,2,3,4,1,2,5,1,2,3,4,5，比较FIFO与LRU缺页次数并判断Belady异常。 - 最短解题模板：
- 画页框时间表（每一步记录页框内容）。
- 命中不替换，缺页按算法选牺牲页。
- 汇总缺页次数并比较：FIFO可能Belady，LRU通常不出现。
⚡ 秒杀版口令卡（10秒回忆）
- 口令：置换必画表，口算易翻车。
- 口令：命中不动，缺页才换。
- 口令：FIFO有Belady，LRU更稳。