【操作系统】页面置换算法（CLOCK/改进型CLOCK）
考点频率：★★★★☆（选择题常考，是LRU的工程实现方案）
难度：⭐⭐⭐
建议：重点掌握CLOCK算法的指针扫描过程，理解改进型CLOCK中访问位和修改位的组合策略
1️⃣ 为什么需要CLOCK算法？
上一篇文章讲了LRU（最近最久未使用），它性能很好，但存在一个实际问题：LRU需要记录每个页面的精确访问顺序（如维护一个访问链表或时间戳），硬件开销大，实现成本高。
能不能用更简单的硬件机制，实现近似LRU的效果？CLOCK算法就是这样一个经典方案。它用一个指针和一个“使用位”（访问位）来近似判断哪些页面最近被访问过，被广泛应用于实际操作系统（如Linux、Windows的页置换）。
2️⃣ 基本CLOCK算法（又称NRU，Not Recently Used）
2.1 数据结构
- 内存中的页面排成一个循环队列
- 每个页面有一个使用位（Reference Bit，R位）：
- 页面被访问时，R位被硬件置为1
- 页面未被访问时，R位保持为0
- 系统维护一个指针（Hand），指向当前要检查的位置
2.2 算法步骤（发生缺页时）
检查指针当前指向的页面：
- 如果R = 0：选择该页面换出（淘汰），指针指向下一个位置
- 如果R = 1：将R位清零（清为0），指针指向下一个位置，继续检查
重复步骤1，直到找到一个 R = 0 的页面进行置换
核心逻辑：给每一个页面一个“第二次机会”。被访问过的页面R=1，指针经过时不清除，相当于“保留一次”。如果一轮循环后，所有页面都刚被访问过，指针转了一圈，自然会把第一个遇到的R=0页面（即最早被清0的）淘汰。
2.3 算法执行示例
假设内存中有3个页面（页框），指针初始指向页框0，访问序列中发生缺页时，操作如下：
| 页框 | 初始R位 | 指针指向 | 缺页处理过程 | 结果 |
|---|---|---|---|---|
| 页框0 | 1 | 指针→页框0 | R=1 → 清0，指针移向页框1 | 继续扫描 |
| 页框1 | 1 | 指针→页框1 | R=1 → 清0，指针移向页框2 | 继续扫描 |
| 页框2 | 0 | 指针→页框2 | R=0 →淘汰页框2，装入新页（R=1），指针移向页框0 | 完成置换 |
注意到R=0的页面被淘汰后，指针指到了下一个位置（页框0），而不是原地。这保证了公平性。
2.4 优点与缺点
| 优点 | 缺点 |
|---|---|
| 硬件开销小（只需要一个访问位） | 只是LRU的近似，不能精确区分页面的访问时间先后顺序 |
| 实现简单，性能稳定 | 如果所有页面的R位都为1，需要扫描一整圈才能淘汰一个页面（最坏情况） |
3️⃣ 改进型CLOCK算法（增强型NRU）
基本CLOCK算法只考虑了页面是否被访问过，但没有考虑页面是否被修改过。如果换出一个被修改过的页面（脏页），需要写回磁盘，代价比换出干净页要大得多。
改进型CLOCK在R位的基础上，增加了修改位（Modified Bit，M位，也称脏位），根据R和M的组合决定淘汰优先级。
3.1 四种页面类别
| 类别 | R位 | M位 | 含义 | 淘汰优先级 |
|---|---|---|---|---|
| 第1类 | 0 | 0 | 最近未访问且未被修改 | 最高（最优淘汰） |
| 第2类 | 0 | 1 | 最近未访问但已被修改 | 中等（换出前需写回磁盘） |
| 第3类 | 1 | 0 | 最近被访问但未被修改 | 较低（给第二次机会） |
| 第4类 | 1 | 1 | 最近被访问且已被修改 | 最低（最不希望淘汰） |
3.2 算法扫描过程
改进型CLOCK执行多轮扫描，每次扫描寻找不同类别的页面：
- 第一轮扫描：寻找
(R=0, M=0)的页面，找到即淘汰。扫描过程中，将遇到的R=1的页面置为0（给它们第二次机会），但M位不变。 - 第二轮扫描：如果第一轮没找到，寻找
(R=0, M=1)的页面，找到即淘汰。 - 第三轮扫描：如果还没找到，重新扫描一遍，此时所有R位都已被清零。再次寻找
(R=0, M=0)并淘汰（因为第一轮时R=1的页面已被清0）。 - 第四轮扫描：如果仍然没有，再次寻找
(R=0, M=1)并淘汰（必能找到）。
3.3 为什么第四轮一定能找到？
经过前三轮，所有的R位都已经是0，且页面的M位非0即1。因此第四轮扫描时，(0,0)和(0,1)两类页面必然存在，至少能找到一类。这是算法终止的保障。
4️⃣ 基本CLOCK vs 改进型CLOCK
| 对比项 | 基本CLOCK | 改进型CLOCK |
|---|---|---|
| 使用位 | 仅R位（访问位） | R位（访问位）+ M位（修改位） |
| 淘汰依据 | 仅看是否最近被访问 | 同时考虑是否被访问和是否被修改 |
| 是否考虑磁盘I/O代价 | 否 | 是（优先淘汰干净页） |
| 扫描轮数 | 通常1轮 | 最多4轮 |
| 实现复杂度 | 低 | 中等 |
5️⃣ 经典例题
例题1：某系统采用基本CLOCK置换算法，内存中有4个页面，R位依次为[1, 0, 0, 1]，指针当前指向第0个页面。发生缺页中断时，被淘汰的页面是哪个？
解析：
- 检查页0：R=1 → 清0，指针→页1
- 检查页1：R=0 → 淘汰页1
答案：页1
例题2：某系统采用改进型CLOCK算法，某时刻内存中4个页面的R位和M位分别为：页0: (1,0)，页1: (0,1)，页2: (0,0)，页3: (1,1)，指针指向页0。发生缺页时，淘汰哪个页面？
解析：
- 第一轮扫描查找
(0,0)：- 页0: (1,0) → R清0，变成(0,0)，指针→页1
- 页1: (0,1) → 不是目标，指针→页2
- 页2: (0,0) →找到！淘汰页2
答案：页2
例题3（概念）：改进型CLOCK算法相比基本CLOCK算法，主要改进之处在于（ ）。
A. 增加了R位
B. 增加了M位，优先淘汰未被修改的页面
C. 用链表代替循环队列
D. 淘汰页面时不需要扫描
解析：改进型CLOCK增加了修改位（M位），优先淘汰(0,0)类页面（未被访问且未被修改），以减少磁盘I/O开销。选B。
6️⃣ 记忆口诀
时钟算法循环查，R位为零就换它。
R位为一清零走，二次机会给一下。
改进加上M位判，优先替换干净页。
零零最优零一次，一一最差放一边。
7️⃣ 小测验（评论区对答案）
某系统采用基本CLOCK置换算法，内存中有3个页面，R位依次为
[0, 1, 1]，指针当前指向页0。发生缺页中断时，被淘汰的页面是（ ）。经过这次淘汰后，指针指向（ ）。
A. 页0，页1
B. 页0，页2
C. 页1，页2
D. 页2，页0
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #CLOCK算法 #页面置换 #NRU #操作系统