【操作系统】页面置换算法（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 算法步骤（发生缺页时）

1. 检查指针当前指向的页面：

   • 如果R = 0：选择该页面换出（淘汰），指针指向下一个位置
   • 如果R = 1：将R位清零（清为0），指针指向下一个位置，继续检查

2. 重复步骤1，直到找到一个 R = 0 的页面进行置换

核心逻辑：给每一个页面一个“第二次机会”。被访问过的页面R=1，指针经过时不清除，相当于“保留一次”。如果一轮循环后，所有页面都刚被访问过，指针转了一圈，自然会把第一个遇到的R=0页面（即最早被清0的）淘汰。

2.3 算法执行示例

假设内存中有3个页面（页框），指针初始指向页框0，访问序列中发生缺页时，操作如下：

注意到R=0的页面被淘汰后，指针指到了下一个位置（页框0），而不是原地。这保证了公平性。

2.4 优点与缺点

3️⃣ 改进型CLOCK算法（增强型NRU）

基本CLOCK算法只考虑了页面是否被访问过，但没有考虑页面是否被修改过。如果换出一个被修改过的页面（脏页），需要写回磁盘，代价比换出干净页要大得多。

改进型CLOCK在R位的基础上，增加了修改位（Modified Bit，M位，也称脏位），根据R和M的组合决定淘汰优先级。

3.1 四种页面类别

3.2 算法扫描过程

改进型CLOCK执行多轮扫描，每次扫描寻找不同类别的页面：

1. 第一轮扫描：寻找(R=0, M=0)的页面，找到即淘汰。扫描过程中，将遇到的R=1的页面置为0（给它们第二次机会），但M位不变。
2. 第二轮扫描：如果第一轮没找到，寻找(R=0, M=1)的页面，找到即淘汰。
3. 第三轮扫描：如果还没找到，重新扫描一遍，此时所有R位都已被清零。再次寻找(R=0, M=0)并淘汰（因为第一轮时R=1的页面已被清0）。
4. 第四轮扫描：如果仍然没有，再次寻找(R=0, M=1)并淘汰（必能找到）。

3.3 为什么第四轮一定能找到？

经过前三轮，所有的R位都已经是0，且页面的M位非0即1。因此第四轮扫描时，(0,0)和(0,1)两类页面必然存在，至少能找到一类。这是算法终止的保障。

4️⃣ 基本CLOCK vs 改进型CLOCK

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 #操作系统