Appearance
CLOCK 与改进 CLOCK 算法
考情分析
CLOCK 算法是 LRU 的近似实现，也是实际操作系统中最常用的页面置换策略。考试中常与 FIFO/LRU/OPT 对比出题。🔥🔥🔥 高频。
LRU 性能好但硬件开销大，FIFO 简单但性能差。实际操作系统需要一个低开销、高性能的折中方案——CLOCK 算法就是这个平衡点。
LRU 与 FIFO 的折中方案
LRU 性能好但实现开销太大（每次访问都要更新计数器或移动栈），FIFO 实现简单但性能差。
CLOCK 算法在两者之间取得了平衡：用一个访问位近似模拟 LRU 的效果，实现代价低，性能接近 LRU。
简单 CLOCK（NRU）
数据结构
- 所有页面组成一个循环链表（想象成钟表）
- 一个指针（时钟指针）指向当前位置——像钟表的秒针一样绕圈扫描
- 每个页面有一个访问位 A（硬件在页面被访问时自动置 1）
算法流程
- 指针从当前位置开始扫描
- 如果当前页面 A=0 → 淘汰该页面
- 如果当前页面 A=1 → 将 A 置为 0，指针前移，继续扫描
- 最坏情况：转一整圈回到起点（此时所有页面的 A 都已被清零），淘汰起始页面
示例
假设 3 个页框，循环链表状态（指针 ↑ 标注）：
页面: A=1 B=0 C=1
↑（指针）需要置换时：
- 检查 B：A=0 → 淘汰 B，新页面装入此位置，指针移到 C
如果 B 的 A=1：
- B: A=1→置为 0，指针移到 C
- C: A=1→置为 0，指针移到 A
- A: A=1→置为 0，指针移到 B
- B: A=0→淘汰 B
交互可视化
改进 CLOCK 算法
简单 CLOCK 只考虑了是否被访问，没有考虑页面是否被修改过。
被修改过的页面（脏页）换出时需要写回磁盘，代价更高。改进 CLOCK 优先淘汰未修改的页面以减少 I/O。
用两个位分类
| 类别 | (A, M) | 含义 | 淘汰优先级 |
|---|---|---|---|
| 第 1 类 | (0, 0) | 未访问、未修改 | 最优先淘汰 |
| 第 2 类 | (0, 1) | 未访问、已修改 | 次优先 |
| 第 3 类 | (1, 0) | 已访问、未修改 | 再次 |
| 第 4 类 | (1, 1) | 已访问、已修改 | 最后淘汰 |
改进 CLOCK 的扫描过程
最多进行 4 轮扫描：
| 轮次 | 寻找目标 | 扫描时操作 |
|---|---|---|
| 第 1 轮 | (A=0, M=0) | 不修改任何位 |
| 第 2 轮 | (A=0, M=1) | 不修改任何位 |
| 第 3 轮 | (A=0, M=0) | 将扫过的页面 A 置 0 |
| 第 4 轮 | (A=0, M=1) | 必然找到（第 3 轮已将所有 A 清零） |
做题关键
第 1、2 轮不改 A 位，第 3 轮才清零 A 位。每轮都是从上次停下的位置继续扫描。
CLOCK 算法的性质
| 性质 | 简单 CLOCK | 改进 CLOCK |
|---|---|---|
| 近似算法 | 近似 LRU | 近似 LRU + 考虑修改 |
| 最多扫描 | 2 圈 | 4 轮（但通常不到 4 轮就找到） |
| I/O 优化 | 无 | 优先淘汰干净页，减少写回 |
| Belady 异常 | 不会（属于栈算法的近似） | 不会（属于栈算法的近似） |
| 实际使用 | Linux/Unix 变体广泛使用 | 部分系统采用 |
四种页面置换算法对比
| 算法 | 决策依据 | 实现复杂度 | 性能 | Belady 异常 |
|---|---|---|---|---|
| OPT | 未来最久不用 | 不可实现 | 最优 | 无 |
| LRU | 过去最久没用 | 高（计数器/栈） | 接近 OPT | 无 |
| CLOCK | 访问位近似 LRU | 低 | 接近 LRU | 可能 |
| FIFO | 进入时间 | 最低 | 最差 | 有 |
考研高频考点
- 🔥🔥🔥 简单 CLOCK 的扫描过程（A=0 淘汰，A=1 清零后继续）
- 🔥🔥🔥 改进 CLOCK 的 4 轮扫描规则
- 🔥🔥 (A, M) 四种组合的淘汰优先级
- 🔥🔥 CLOCK 是 LRU 的近似实现
- 🔥 改进 CLOCK 优先淘汰未修改页面以减少 I/O
四种页面置换算法各有特点，实际做题时经常要对同一引用串分别跑不同算法再比较缺页次数。下篇用一个交互模拟器把它们放在一起对比。