页置换算法
缺页而内存又满了，就必须淘汰一页。淘汰谁，决定了缺页率的高低。
本节五个算法，考法分两类：手算缺页次数（计算题）和辨析各算法的性质（选择题）。先给手算方法，再逐个讲。
机制
手算三步法
第一步：画表。 横轴是访问串，纵轴是各个页框。每一列代表一次访问。
第二步：逐列判断三件事，顺序不能乱：
- 该页是否已在内存？在 → 命中，不缺页（但可能要更新算法的记录，如 LRU 的顺序、Clock 的访问位）
- 不在 → 缺页。内存是否已满？未满 → 直接放入空闲页框
- 已满 → 按算法规则选一页淘汰，再放入
第三步：数缺页次数。 注意：最初把页装入空页框的那几次也算缺页（因为确实发生了缺页中断）。
最容易错的地方是第 1 步的”命中也要更新记录”——FIFO 命中时不改变队列顺序，而 LRU 命中时必须更新最近使用顺序。这一条记反了，整道题就全错。
① OPT 最佳置换算法
规则：淘汰未来最长时间内不再被访问的页面；若某页以后再也不会用到，优先淘汰它。
OPT 的缺页率最低，是理论上的最优解。但它需要预知未来的访问序列，实际系统无法实现，只能作为衡量其他算法优劣的标尺。
疑问点：OPT 的手算技巧
手算最佳置换算法时如何快速判断？ 自己模拟时是向后看、找最晚使用的那个——这个思路是否正确？
思路完全正确：缺页且内存已满时，只看当前内存中的那几页，比较它们各自”下一次出现的位置”，最靠后的那个（或以后不再出现的）被淘汰。
手算的关键在于不要每次都重新扫描整个访问串。 更稳的做法：
- 在访问串上，给每个位置标出该页下一次出现的位置（不再出现的记为 ∞）
- 缺页时只比较内存中那几页的标记值
- 取最大的那个淘汰
这样每次决策只需比较 3~4 个数，而不是重扫全串。
关联对照：作为算法题时的复杂度优化
“每次都向后看肯定会超时”——这个判断是对的。朴素做法每次淘汰都要向后扫描整个剩余序列，最坏
。 通用优化是预处理”下一次出现位置”：
- 从后往前扫一遍访问串，用一个哈希表记录每个页最近一次出现的位置，即可在
内求出每个位置的 nxt[i]（该页下一次出现在哪）。- 用一个按
nxt排序的堆或有序集合维护当前内存中的页。淘汰时直接取堆顶（nxt最大者）。- 每次访问后更新该页的
nxt并调整堆。总复杂度降到
。 这个”预处理下一次出现位置”的技巧在很多题里通用，本质是把”每次向后找”变成”一次性算好，之后 O(1) 查表”。
考试手算时不必这么严格，但理解”要比较的是 nxt 值”能让手算快很多。
② FIFO 先进先出算法
规则：淘汰最早进入内存的页面。用一个队列记录页面调入的先后，每次淘汰队头。
实现最简单，但性能很差——最早调入的页很可能是被频繁访问的核心页（比如主循环所在的页）。
FIFO 是唯一会产生 Belady 异常的算法。
Belady 异常：增加分配的页框数，缺页次数反而增多的反常现象。
这个现象之所以反直觉，是因为我们默认”内存越多越好”。但 FIFO 的淘汰依据是”进来的早晚”，这和”将来还用不用”毫无关系。页框数变化会打乱队列的进出节奏，在特定访问串下就可能变得更糟。
只有 FIFO 会出现 Belady 异常，LRU 和 OPT 都不会——因为它们属于栈算法，具有”页框数增加时，驻留集只增不减”的性质。这是考试的固定考点。
③ LRU 最近最久未使用算法
规则：淘汰最近最久未被访问的页面。
它是 OPT 的”过去镜像”——OPT 向未来看，LRU 向过去看，赌的是时间局部性：最近很久没用的，将来多半也不会马上用。
LRU 是实际效果最接近 OPT 的算法，且不会出现 Belady 异常。
疑问点：LRU 需要维护什么，为何实现代价高
LRU 具体维护的是什么？ 22. 导致 LRU 算法实现起来耗费高的原因是（ ）。 A. 需要硬件的特殊支持 B. 需要特殊的中断处理程序 C. 需要在页表中标明特殊的页类型 D. 需要对所有的页进行排序
操作系统或硬件层面究竟是怎么实现的？
LRU 维护的是”所有驻留页的最近使用顺序”。选择题答案是 A：需要硬件的特殊支持。
代价高的根源在于更新的频率：
每一次访存都必须更新这个顺序记录——不只是缺页时，命中时也要更新。
一个程序每秒执行上亿次访存，如果每次都要陷入内核跑一段软件去维护顺序，开销会远远超过程序本身的计算量。所以这件事只能交给硬件顺带完成，这正是选 A 的理由。
两种典型的硬件实现：
寄存器（计数器）方式：为每个页框配一个寄存器，记录该页最后一次被访问的时刻（或一个不断右移的位串）。淘汰时找数值最小的那个。代价是每个页框都要一个寄存器，且访存时要写。
栈方式：用一个特殊的栈保存页号。每次访问某页，就把它的页号从栈中抽出、压到栈顶。于是栈顶永远是最近使用的，栈底永远是最久未使用的，淘汰时直接取栈底。
D 是本题最强的干扰项，必须说清为什么不选它：
LRU 并不真的”对所有页排序”。 栈方式只需把被访问的页号抽出、压到栈顶，就自动维持了顺序，全程不执行任何排序算法；计数器方式也只是在淘汰时找一次最小值。选项 D 描述的是一种直觉上的印象，不是实际做法。
更关键的是教材自己的表述：王道对 LRU 代价的原话是”需要寄存器和栈的硬件支持”——这句话与选项 A 逐字对应。本题考的正是对这句话的复现。
这道题的答案容易记反（“要维护顺序”听起来太像”要排序”了），做题时回到那句原话即可。
正因为精确 LRU 代价太高，实际系统普遍使用它的近似算法——也就是下面的 Clock。
④ CLOCK 时钟置换算法（NRU）
Clock 是 LRU 的低成本近似。它只用一位访问位 A，就近似地表达了”最近有没有被用过”。
规则：
- 把所有页框组织成一个循环队列，用一个指针指向下一个待检查的页框。
- 页面被访问时，硬件自动把 A 置 1（这一步是免费的，硬件顺手做的）。
- 需要淘汰时，指针开始扫描：
- 遇到 A = 0 → 淘汰它，指针后移
- 遇到 A = 1 → 把 A 置 0（给它”第二次机会”），指针后移，继续扫描
- 若一圈下来全是 1，则第二圈时它们都已被置 0，必然能选出一个。所以最多扫描两轮。
“给第二次机会”是理解 Clock 的关键：A = 1 说明它最近被用过，先饶它一次；如果转了一圈回来它还没被再次访问（A 仍是刚才置的 0），就说明它确实不活跃了，可以淘汰。
⑤ 改进型 CLOCK 算法
疑问点：改进型时钟置换算法的记忆方法
需要一个最通透、最容易理解的记忆方法。
最通透的记法只有一句：把 (A, M) 看成一个两位二进制数，谁小先淘汰谁。
| 优先级 | (A, M) | 二进制值 | 含义 |
|---|---|---|---|
| 1（最先淘汰） | (0, 0) | 0 | 最近没访问、也没修改 → 不用写回，白捡 |
| 2 | (0, 1) | 1 | 最近没访问，但改过 → 该淘汰，但要写回 |
| 3 | (1, 0) | 2 | 最近访问过，没改 → 还可能要用，先留着 |
| 4（最后淘汰） | (1, 1) | 3 | 最近访问过且改过 → 最不该动 |
而这个顺序不是硬记的，它有一条明确的道理——为什么 A 是高位、M 是低位：
A 说的是”这页还会不会再用”（未来的价值）；M 说的是”淘汰它要花多少代价”（写不写回）。
价值优先于代价。 一个马上还要用的页，哪怕淘汰它零成本，也不该淘汰——因为淘汰了马上又要调回来。反过来，一个确实不会再用的页，哪怕要写回一次，也值得淘汰。
所以 A 位的分量必然重于 M 位，把它放在高位，二进制大小顺序就自动等于淘汰优先级顺序。记住”价值优先于代价”这六个字，四种情况的排序就永远不会记反。
扫描过程（最多四轮）：
| 轮次 | 找什么 | 是否清 A |
|---|---|---|
| 第 1 轮 | (0, 0) | 否 |
| 第 2 轮 | (0, 1) | 是（把扫过的 A 置 0） |
| 第 3 轮 | (0, 0) | 否（此时 A 已被第 2 轮清过） |
| 第 4 轮 | (0, 1) | 是 |
第 1、2 轮先按原样找；若都没找到，说明当时所有页的 A 都是 1，而第 2 轮已经把它们全部清零，第 3 轮必然能找到。
改进型 Clock 相对普通 Clock 的收益是：优先淘汰不需要写回的页，减少磁盘 I/O。
2021 统考真题完整解法
疑问点：页、页框、页帧的对应关系
54.【2021 统考真题】某请求分页存储系统的页大小为 4KB，按字节编址， 系统给进程 P 分配 2 个固定的页框，并采用改进型 Clock 置换算法，进程 P 页表的部分内容如下：
页号 页框号 存在位 访问位 修改位 2 20H 0 0 0 3 60H 1 1 0 4 80H 1 1 1 若 P 访问虚拟地址为 02A01H 的存储单元，则经地址变换后得到的物理地址是（ ）。 A. 00A01H B. 20A01H C. 60A01H D. 80A01H
另需厘清”页框 / 页帧”等名词的对应关系。
答案 C：60A01H。
先把名词对齐——这几个词说的是同一样东西，只是译法不同：
页框 = 页帧 = 物理块 = 内存块 = frame
而页 = 页面 = page，指的是逻辑地址空间被分成的块。
一句话对应：页是”逻辑的”，页框是”物理的”，两者大小相同，页表记录的就是”第几页放在第几个页框里”。
解题四步：
第一步：拆地址。 页大小
第二步：查页表，发现缺页。 页号 2 的存在位为 0 → 该页不在内存，产生缺页中断，必须先置换。
这一步是本题的陷阱——不少人直接拿页表里页 2 那一行的”页框号 20H”去拼，得到 20A01H（选项 B）。但存在位为 0 意味着那个页框号是无效的（该页根本没被装入过，这一栏是残留或未定义值）。
第三步：用改进型 Clock 选淘汰页。 内存中现有页 3 (A=1, M=0) 和页 4 (A=1, M=1)：
| 轮次 | 找什么 | 结果 | 扫描后状态 |
|---|---|---|---|
| 第 1 轮 | (0,0) | 未找到 | 页3 (1,0) 页4 (1,1) |
| 第 2 轮 | (0,1)，并清 A | 未找到 | 页3 (0,0) 页4 (0,1) |
| 第 3 轮 | (0,0) | 找到页 3 | — |
淘汰页 3，回收其页框 60H。因为页 3 的 M = 0（未修改），不必写回外存。
第四步：装入并拼接。 页 2 被装入页框 60H：
也可以用乘法验证：
这道题把本章几乎所有考点串了一遍：地址拆分、存在位判断、缺页中断、改进型 Clock 扫描、修改位决定是否写回、页框号拼接。它是第 3 章最值得反复做的一道题。
边界
命中时要不要更新记录
这是手算题最大的失分点，各算法完全不同：
| 算法 | 命中时 | 缺页时 |
|---|---|---|
| FIFO | 什么都不做（队列顺序不变） | 淘汰队头，新页入队尾 |
| LRU | 必须更新最近使用顺序 | 淘汰最久未用者 |
| CLOCK | 把 A 置 1 | 扫描找 A=0 者 |
| 改进型 CLOCK | 把 A 置 1；若是写操作还要置 M = 1 | 四轮扫描 |
| OPT | 什么都不做 | 淘汰 nxt 最大者 |
记法：FIFO 看”进来的时间”，进来了就定了，命中不改变；LRU 和 Clock 看”使用情况”，所以命中必须记一笔。
Belady 异常只出现在 FIFO
只有 FIFO 会出现”页框数增加、缺页反而增多”的 Belady 异常。 LRU 和 OPT 都不会。
根本原因是 LRU 和 OPT 属于栈算法：它们保证页框数为
而 FIFO 的淘汰依据是”进入的先后”，与”是否还会被访问”毫无关系，不满足这个包含性质，因此可能反常。
LRU 与 Clock 的关系
Clock 是 LRU 的近似，而不是另一种思路。
- LRU 需要知道精确的使用先后顺序（谁比谁更久没用）——代价是每次访存都要更新。
- Clock 只需要知道**“最近有没有用过”这一位信息**——硬件置位是免费的。
用一位近似换取了实现成本的大幅下降，代价是精度降低（它区分不出”刚用过”和”半秒前用过”）。
实际系统几乎都用 Clock 系列而非精确 LRU，原因就在这里。
各算法的性能排序
OPT 是理论上限（不可实现），FIFO 是实用算法里最差的。 LRU 效果好但代价高，Clock 是工程上的最佳折中。
对照速查
| 算法 | 淘汰依据 | 可实现 | Belady 异常 | 性能 |
|---|---|---|---|---|
| OPT | 未来最晚使用 | ❌ | 否 | 最优（标尺） |
| FIFO | 进入内存最早 | ✅ | ✅ 会 | 最差 |
| LRU | 过去最久未用 | ✅（需硬件） | 否 | 接近 OPT |
| CLOCK | 访问位 A = 0 | ✅ | 否 | LRU 的近似 |
| 改进型 CLOCK | (A,M) 按二进制值 | ✅ | 否 | 更省 I/O |
| 改进型 Clock 淘汰顺序 | 理由 |
|---|---|
| (0,0) → (0,1) → (1,0) → (1,1) | 把 (A,M) 当两位二进制数，从小到大 |
| A 为何是高位 | 价值优先于代价：A 管”还用不用”，M 管”写不写回” |
考点
- 手算三步法，尤其”命中时各算法是否更新记录”
- 只有 FIFO 有 Belady 异常；LRU、OPT 是栈算法故不会
- LRU 代价高的原因是”每次访存都要更新”，只能靠硬件（选 A）
- LRU 的两种硬件实现：寄存器（计数器）与栈（栈底即最久未用）
- Clock 最多扫描两轮；改进型 Clock 最多四轮
- 改进型 Clock 的顺序：(A,M) 当二进制数从小到大
- 2021 真题：存在位为 0 时页表里的页框号无效，必须先置换
链接
- 🏠 返回总览：操作系统第 3 章：内存管理总览
- ⬅️ 上一节：3.2.3 页框分配
- ➡️ 下一节：3.2.5 抖动和工作集
- 🔗 访问位与修改位的来历见 3.2.2 请求分页管理方式
- 📖 名词库：第 3 章名词库