跳转至

408 高频考点精讲:CLOCK置换算法

模块归属:操作系统 · 内存管理 考点层级:微观细分考点(近十年考查 >= 3 次) 适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:3 次(2016 年第 26 题、2018 年第 45 题第 (3) 问、2021 年第 28 题)
  • 历年总考查频次:3 次
  • 出题形式:单项选择题、综合解答题
  • 命题特点:
  • 核心机制与优先级逻辑:重点考查简单 CLOCK 与改进型 CLOCK 算法的基本原理、数据结构支持(访问位与修改位),以及四类页状态 \((0, 0)\)、\((0, 1)\)、\((1, 0)\)、\((1, 1)\) 的循环扫描与淘汰优先级次序。
  • 软硬件协作与页表结构:考查内存管理单元(MMU)硬件自动置位机制与操作系统内核清零机制的职责边界,涉及页表项(Page Table Entry, PTE)字段设置。
  • 端到端综合地址变换模拟:将 CLOCK 页面置换与虚实地址变换、页内偏移切分、缺页异常处理、页框分配及物理地址合成深度融合,考查完整生命周期中的推导计算。

近十年考查年份分布表格(2016 ~ 2025)

+------+------+------+------+------+------+------+------+------+------+
| 2016 | 2017 | 2018 | 2019 | 2020 | 2021 | 2022 | 2023 | 2024 | 2025 |
+------+------+------+------+------+------+------+------+------+------+
| #26  |  --  | #45  |  --  |  --  | #28  |  --  |  --  |  --  |  --  |
+------+------+------+------+------+------+------+------+------+------+
注:2018 年第 45 题为综合解答题,其中第 (3) 问专门考查改进型 CLOCK 算法的页表项字段支持。

二、 具体考察内容

1. 核心概念与机制原理

1.1 页面置换背景与算法动因

在请求分页虚拟存储管理系统中,当进程访问的页面尚未装入主存(页表项存在位为 0),且系统分配给该进程的物理页框已全部占满时,操作系统必须执行页面置换策略(Page Replacement),选择一个驻留页面淘汰并腾出页框。 - 理想置换算法(OPT)淘汰未来最长时间内不被访问的页面,具有最低缺页率,但因依赖未来指令序列而无法在工程中实现,仅作为评价标准。 - 先进先出算法(FIFO)实现开销低,但忽视了页面使用频度,可能导致 Belady 异常(分配页框数增加,缺页次数反而上升)。 - 最近最少使用算法(LRU)性能高度逼近 OPT,但需借助硬件堆栈或寄存器记录时间局部性,硬件实现复杂度高、访存开销过大。 - 时钟置换算法(CLOCK)是一种对 LRU 的工程级近似(Approximation of LRU),亦称最近未使用算法(Not Recently Used, NRU)或二次机会算法(Second-Chance Algorithm)。其利用循环队列指针与标志位,在接近 LRU 性能的同时,大幅度降低了硬件开销。


1.2 简单 CLOCK 算法(二次机会算法)

简单 CLOCK 算法在每个驻留页面的页表项中设置一位访问位(Reference Bit / Access Bit,记为 \(A\)$ \text{或} $\(U\))。

       [页框 0] (A=1)
      ↗             ↘
 [页框 3] (A=0)    [页框 1] (A=0)  <-- 指针当前位置
      ↖             ↙
       [页框 2] (A=1)
  • 数据结构:所有驻留主存的页面通过指针链接成一个逻辑上的循环单链表(环形队列),并由一个置换指针(Next Frame Pointer)指向下一个待检查的页面。
  • 置换工作流程:
  • 当发生缺页中断且页框已满时,置换指针从当前位置开始遍历环形队列。
  • 检查当前指针所指页面的访问位 \(A\):
    • 若 \(A = 0\):表明该页最近未被访问,选择该页作为淘汰目标,将其换出;置换指针顺时针下移一位,算法终止。
    • 若 \(A = 1\)$ \text{:表明该页最近被访问过,给予其“第二次机会”,硬件/系统将该页的访问位置} $\(0\)(\(A \leftarrow 0\)),指针顺时针前进一步继续检查下一页。
  • 若所有驻留页面的访问位均为 \(1\)$ \text{,指针在第一轮扫描中将所有页面的} $\(A\)$ \text{均置为} $\(0\)$ \text{;第二轮扫描时,指针首先遇到的页面(其} $\(A\)$ \text{此时已为} $\(0\))将被直接淘汰。

1.3 改进型 CLOCK 算法(Enhanced Second-Chance)

简单 CLOCK 算法仅考虑了页面是否被访问,但未考虑页面是否被修改。在现代操作系统中,置换修改过的页面需要付出昂贵的磁盘写回 I/O 开销,而置换未修改过的页面仅需直接丢弃或覆盖,代价极低。因此,改进型 CLOCK 算法综合权衡使用频度与写回代价。

(1)状态定义与四类页面划分

在页表项中同时引入访问位 \(A\)$ \text{ 与 修改位} $\(M\)(Dirty Bit / Modify Bit,脏位): - \(A = 0\)$ \text{:该页最近未被访问;} $\(A = 1\):该页最近已被访问。 - \(M = 0\)$ \text{:该页未被修改;} $\(M = 1\):该页已被修改(写操作)。

根据二元状态元组 \((A, M)\),驻留内存的页面可被划分为四种优先级状态:

类别代号 状态元组 \((A, M)\) 状态物理含义 淘汰优先级 置换代价分析
第 1 类 \((0, 0)\) 最近未访问,未被修改 最高(首选) 既无访问热度,又无需写回磁盘,开销最小
第 2 类 \((0, 1)\) 最近未访问,已被修改 次高 虽无访问热度,但置换时必须写回外存,存在 I/O 开销
第 3 类 \((1, 0)\) 最近已访问,未被修改 较低 具备访问局部性,给予第二次机会保留;且无写回开销
第 4 类 \((1, 1)\) 最近已访问,已被修改 最低 既有访问局部性,又有昂贵写回开销,最不应被置换
(2)四轮扫描淘汰算法执行规则

当发生缺页需要置换页面时,置换指针从当前位置开始,遵循以下严格的四步循环判定规则:

               +----------------------------------+
               |        发生缺页异常,页框已满     |
               +----------------------------------+
                                 |
                                 v
               +----------------------------------+
               |  第 1 轮扫描:寻找最佳候选 (0, 0) |
               |     【注意:本轮不修改任何 A 位】  |
               +----------------------------------+
                     /                      \
             找到 $(0, 0)$$ \text{未找到} $$(0, 0)$
                   /                          \
                  v                            v
          +---------------+      +----------------------------------+
          | 淘汰该页, 结束 |      |  第 2 轮扫描:寻找次佳候选 (0, 1) |
          +---------------+      |     【扫描过的页面 A 位强制置 0】 |
                                 +----------------------------------+
                                       /                      \
                               找到 $(0, 1)$$ \text{未找到} $$(0, 1)$
                                     /                          \
                                    v                            v
                            +---------------+      +----------------------------------+
                            | 淘汰该页, 结束 |      |  第 3 轮扫描:重新寻找 (0, 0)    |
                            +---------------+      |     【注意:本轮不修改任何 A 位】  |
                                                   +----------------------------------+
                                                         /                      \
                                                 找到 $(0, 0)$$ \text{未找到} $$(0, 0)$
                                                       /                          \
                                                      v                            v
                                              +---------------+      +----------------------------------+
                                              | 淘汰该页, 结束 |      |  第 4 轮扫描:重新寻找 (0, 1)    |
                                              |               |      | 【必能命中第一个遇到的 (0, 1)】  |
                                              +---------------+      +----------------------------------+
                                                                                       |
                                                                                       v
                                                                             +-------------------+
                                                                             | 淘汰该页, 算法终止 |
                                                                             +-------------------+
  • 第 1 轮扫描:置换指针顺序扫描环形队列,寻找第一个状态为 \((0, 0)\) 的页面。
  • 核心约束:此轮扫描期间,不修改任何页面的访问位 \(A\)。
  • 操作结果:若找到 \((0, 0)\),则将该页置换出,指针指向下一位置,算法结束;若未找到,进入第 2 轮。
  • 第 2 轮扫描:置换指针继续顺序扫描环形队列,寻找第一个状态为 \((0, 1)\) 的页面。
  • 核心约束:在此轮扫描过程中,所有被指针扫描经过的页面,其访问位 \(A\)$ \text{均被强制置为} $\(0\)$ \text{(即} $\(A \leftarrow 0\))。
  • 操作结果:若找到初始即为 \((0, 1)\) 的页面,则将该页淘汰,写回外存,指针下移,算法结束;若扫描一整圈仍未找到,进入第 3 轮。
  • 第 3 轮扫描:置换指针重新从头扫描环形队列,寻找状态为 \((0, 0)\) 的页面。
  • 机制演化:由于第 2 轮已将所有原本为 \((1, 0)\)$ \text{的页面的访问位} $\(A\)$ \text{清零,这些页面在第 3 轮中已转变为} $\((0, 0)\)。
  • 核心约束:此轮扫描不修改任何 \(A\) 位。
  • 操作结果:若找到 \((0, 0)\)$ \text{,直接置换淘汰;若未找到(说明进入第 2 轮前没有} $\((1, 0)\)$ \text{,所有页面原先均为} $\((1, 1)\)$ \text{,并在第 2 轮全部转变为} $\((0, 1)\)),则进入第 4 轮。
  • 第 4 轮扫描:置换指针寻找第一个状态为 \((0, 1)\) 的页面。
  • 必然终止性:此时环形队列中剩余的所有页面状态必然全为 \((0, 1)\),因此指针扫描遇到的第一个页面即被直接淘汰,写回外存,算法必定在此步成功终止。

1.4 软硬件分工与页表项支持

CLOCK 算法的高效性依赖于操作系统与体系结构硬件(MMU)的精细分工:

+-----------------------+-------------------------------------------------------------+
| 组成部分              | 软硬件职责协同说明                                          |
+-----------------------+-------------------------------------------------------------+
| 访问位 A (Access)     | 硬件行为:CPU 发生任何形式的访存(读/写)时,MMU 自动置 A = 1。|
|                       | 软件行为:操作系统在时钟中断处理程序或 CLOCK 置换算法扫描时,通过指令置 A = 0。|
+-----------------------+-------------------------------------------------------------+
| 修改位 M (Modify)     | 硬件行为:CPU 对页面发生数据写入操作时,MMU 自动置 M = 1。     |
|                       | 软件行为:操作系统将脏页写回磁盘交换区后,将该页表项的 M 置 0。|
+-----------------------+-------------------------------------------------------------+
| 存在位 P (Present)    | 硬件行为:MMU 转换虚实地址时检测,若 P = 0,触发缺页异常。  |
|                       | 软件行为:操作系统将页面装入页框后置 P = 1,换出后清零。     |
+-----------------------+-------------------------------------------------------------+

2. 核心定理推导与计算模型

2.1 扫描步数界限推导(算法时间复杂度模型)

设进程分配到的驻留集物理页框总数为 \(N\)。

定理 1(简单 CLOCK 扫描步数上界)

在简单 CLOCK 算法中,置换一个页面所需检查的最大页框数(即置换指针移动步数)为 \(2N\)$ \text{步,其时间复杂度为严格的} $\(O(N)\)。 - 证明: 若发生缺页时,所有 \(N\)$ \text{个页框的访问位} $\(A\)$ \text{均为} $\(1\)。 - 第 1 轮扫描遍历全部 \(N\)$ \text{个页框,无任何页面的} $\(A=0\)$ \text{,但依次将这} $\(N\)$ \text{个页框的} $\(A\)$ \text{置为} $\(0\)$ \text{。耗费步数} $\(N\)。 - 第 2 轮扫描从首个页框重新开始,此时首个页框的 \(A\) 已在第 1 轮被清零,算法立即选中该页淘汰。 - 最坏总扫描步数为: $\(S_{\max} = N + 1 \le 2N\)$ 得证。

定理 2(改进型 CLOCK 扫描步数上界)

在改进型 CLOCK 算法中,置换一个页面所需检查的最大页框数为 \(3N + 1 \le 4N\)$ \text{步,时间复杂度仍为} $\(O(N)\)。 - 证明: 考查最坏极端初始状态:所有 \(N\)$ \text{个页面的初态均为} $\((1, 1)\)。 - 第 1 轮扫描:寻找 \((0, 0)\)$ \text{,指针循环一周检查} $\(N\)$ \text{个页框,均不匹配,不修改标志位。耗费步数} $\(N\)。 - 第 2 轮扫描:寻找 \((0, 1)\)$ \text{,指针循环一周检查} $\(N\)$ \text{个页框。由于初始状态全为} $\((1, 1)\)$ \text{,无初始} $\((0, 1)\)$ \text{,扫描过程中所有页面的} $\(A\)$ \text{位均被置为} $\(0\)$ \text{,所有页面状态由} $\((1, 1)\)$ \text{变为} $\((0, 1)\)$ \text{。耗费步数} $\(N\)。 - 第 3 轮扫描:寻找 \((0, 0)\)$ \text{,指针循环一周检查} $\(N\)$ \text{个页框。由于所有页面当前均为} $\((0, 1)\)$ \text{,无任何} $\((0, 0)\)$ \text{页面匹配。耗费步数} $\(N\)。 - 第 4 轮扫描:寻找 \((0, 1)\)$ \text{,指针检查当前位置的第 1 个页框,其状态即为} $\((0, 1)\)$ \text{,匹配成功并淘汰该页。耗费步数} $\(1\)。 - 最坏扫描步数精确值为: $\(S_{\max} = N + N + N + 1 = 3N + 1 \le 4N\)$ 得证。


2.2 有效访存时间(EAT)模型与优化机理

在分页虚拟存储系统中,考虑缺页中断与页面置换的平均访存时间模型定义如下:

\[EAT = (1 - p) \cdot t_{ma} + p \cdot \left[ t_{fault} + P_{dirty} \cdot t_{write\_disk} + t_{read\_disk} + t_{ma} \right]\]
  • 符号定义:
  • \(p\):缺页率(Page Fault Rate);
  • \(t_{ma}\):物理内存访问时间(Memory Access Time);
  • \(t_{fault}\):缺页中断处理与上下文切换开销;
  • \(P_{dirty}\)$ \text{:被选中淘汰的页面为脏页(修改位} $\(M=1\))的概率;
  • \(t_{write\_disk}\):将脏页数据写回外存磁盘的耗时;
  • \(t_{read\_disk}\):从外存读取目标页调入主存的耗时。

由于磁盘 I/O 耗时(毫秒级)远大于主存访问时间(纳秒级),即 \(t_{write\_disk} \approx t_{read\_disk} \gg t_{ma}\)。 改进型 CLOCK 算法的核心数学价值在于主动最小化 \(P_{dirty}\): - 算法第 1 轮优先淘汰 \(M=0\)$ \text{的页面,使} $\(P_{dirty} \rightarrow 0\); - 此时单次缺页的处理时间由 \(t_{fault} + t_{write\_disk} + t_{read\_disk}\)$ \text{降为} $\(t_{fault} + t_{read\_disk}\),磁盘 I/O 负荷减半,显著抑制了系统有效访存延迟的恶化。


3. 对比辨析

3.1 常见页面置换算法全维度技术特征对比

对比维度 最佳置换 (OPT) 先进先出 (FIFO) 最近最少使用 (LRU) 简单 CLOCK (NRU) 改进型 CLOCK
置换基准 淘汰未来最远访问页 淘汰驻留时间最长页 淘汰过去最久未用页 淘汰近期未访问页 淘汰近期未访问且未修改页
硬件支持 理论需要未来序列(不可实现) 仅需基本队列指针 寄存器/栈/时间戳(硬件昂贵) 1 位访问位 \(A\)$ \text{+ 循环指针 访问位} $\(A\)$ \text{+ 修改位} $\(M\) + 循环指针
Belady 异常 不存在(属于栈式算法) 存在(非栈式算法) 不存在(属于栈式算法) 不存在 不存在
时间开销 无法运行 \(O(1)\) \(O(1)\)$ \text{查找,但更新开销大 最多} $\(2N\)$ \text{步,均摊低 最多} $\(4N\) 步,均摊低
I/O 开销权衡 无感知 无感知 无感知 无感知 优先规避写回 I/O
工程实用性 理论上限基准 较差,常导致抖动 代价过高,极少纯硬件实现 极高,Linux 等系统广泛应用 极高,兼顾访存局部性与写回代价

3.2 简单 CLOCK 与改进型 CLOCK 机制纵向对比

属性 简单 CLOCK 算法 改进型 CLOCK 算法
控制标志位 单标志位:访问位 \(A\)$ \text{ 双标志位:访问位} $\(A\)$ \text{+ 修改位} $\(M\)
页面状态维度 2 种取值:\(A=0\)$ \text{与} $\(A=1\)$ \text{ 4 种取值:} $\((0, 0), (0, 1), (1, 0), (1, 1)\)
淘汰目标次序 仅按访问频次:\(0\)$ \text{优先于} $\(1\)$ \text{ 综合排序:} $\((0, 0) \succ (0, 1) \succ (1, 0) \succ (1, 1)\)
扫描轮数上限 最多扫描 2 轮 最多扫描 4 轮
最坏步数消耗 \(N + 1\) \(3N + 1\)
优化目标 纯粹拟合 LRU 的时间局部性 在拟合 LRU 的基础上,进一步降低外存磁盘回写频率

三、 近十年真题精讲(2016~2025)

【真题 1】2016 年 408 第 26 题 · 改进型 CLOCK 算法淘汰优先级判定

题目 某系统采用改进型 CLOCK 置换算法,页表项中字段 A 为访问位,M 为修改位。A=0 表示页最近没有被访问,A=1 表示页最近被访问过。M=0 表示页没有被修改过,M=1 表示页被修改过。按 (A, M) 所有可能的取值,将页分为四类:(0, 0)、(1, 0)、(0, 1) 和 (1, 1),则该算法淘汰页的次序为( )。 A. (0, 0), (0, 1), (1, 0), (1, 1)
B. (0, 0), (1, 0), (0, 1), (1, 1)
C. (0, 0), (0, 1), (1, 1), (1, 0)
D. (0, 0), (1, 1), (0, 1), (1, 0)

【解析】

  1. 知识定位:考查改进型 CLOCK 算法在四种 \((A, M)\) 状态下的理论淘汰优先级。
  2. 算法执行次序推导:
  3. 改进型 CLOCK 算法在置换过程中按照四轮循环查找:
    • 第 1 轮查找目标:寻找 \((A=0, M=0)\)。此类页面最近未被访问且未被修改,淘汰该类页面既不会破坏局部性,又无需将内容写回磁盘,代价最低,因此置换优先级最高,排在第 1 位。
    • 第 2 轮查找目标:寻找 \((A=0, M=1)\)$ \text{。此类页面最近未被访问,但已被修改。虽然置换该页需写回外存,但相比仍处于活跃访问状态的页面(} $\(A=1\)$ \text{),其换出对程序运行局部性的影响更小,因此排在第 2 位。在这一轮扫描中,未被选中的页面其} $\(A\) 位被清零。
    • 第 3 轮查找目标:寻找 \((A=0, M=0)\)$ \text{。经过第 2 轮的清零操作,原本处于活跃状态且未被修改的页面} $\((1, 0)\)$ \text{转变为} $\((0, 0)\)$ \text{。此轮扫描重新命中此类页面并将其淘汰,因此} $\((1, 0)\) 的实质淘汰优先级排在第 3 位。
    • 第 4 轮查找目标:寻找 \((A=0, M=1)\)$ \text{。原本处于活跃状态且已被修改的页面} $\((1, 1)\)$ \text{在第 2 轮被清零为} $\((0, 1)\),并在第 4 轮被淘汰,其实质淘汰优先级最低,排在第 4 位。
  4. 选项逐项判定:
  5. A 选项:(0, 0), (0, 1), (1, 0), (1, 1),完全符合四轮扫描确定的优先级序列,判定正确。
  6. B 选项:错将 \((1, 0)\)$ \text{置于} $\((0, 1)\)$ \text{之前。若先淘汰} $\((1, 0)\),则违背了“优先淘汰未被访问页面”的局部性核心原则,判定错误。
  7. C 选项:错将 \((1, 1)\)$ \text{置于} $\((1, 0)\) 之前,颠倒了未修改页与修改页在同等访问条件下的置换代价,判定错误。
  8. D 选项:完全打乱了算法的优先级层级,判定错误。

正确答案:A


【真题 2】2018 年 408 第 45 题 · 改进型 CLOCK 算法的页表结构硬件支持

题目(节选自综合解答题第 (3) 问) 某 32 位虚拟存储系统采用二级分页存储管理,系统采用改进型 CLOCK 页面置换算法。 (3) 为了支持改进型 CLOCK 置换算法,需要在页表项中设置哪些字段?

【解析】

  1. 知识定位:考查支持改进型 CLOCK 置换算法所需的最小页表项字段集合及其软硬件协同机制。
  2. 核心字段分析与采分要点:
  3. 访问位(Reference Bit / Access Bit / 使用位 / 引用位):
    • 设立必要性:反映该页在最近一个时间段内是否被读或写访问过。
    • 硬件支持:当 CPU 发出访存指令并命中该页时,MMU 硬件电路自动将该位设置为 \(1\)。操作系统在执行 CLOCK 扫描时通过特权指令将其清零。
    • 算法功能:用于区分页面访问活跃度,给予活跃页面(\(A=1\))保留在内存中的“第二次机会”。
  4. 修改位(Dirty Bit / Modify Bit / 脏位):
    • 设立必要性:记录该页面调入主存后内容是否被写指令修改过。
    • 硬件支持:当 CPU 执行写内存操作时,MMU 硬件电路自动将该位设置为 \(1\)。
    • 算法功能:算法据此判断淘汰该页面时是否需要执行磁盘写回(Write-Back)I/O 操作。若修改位为 \(0\)$ \text{,可直接覆盖释放页框;若修改位为} $\(1\),必须在覆盖前将其写入外存对齐数据,以降低算法的平均 I/O 成本。
  5. 得分拓展辨析:
  6. 标准页表项中通常还包含物理页框号(Page Frame Number)、存在位/有效位(Valid / Present Bit)、存取控制保护位(Read/Write/Execute Protection Bits)等,但设问明确要求“为了支持改进型 CLOCK 置换算法”,因此核心得分点严格聚焦于访问位与修改位。

正确答案(采分点): 需要在页表项中设置:访问位(或使用位、引用位) 和 修改位(或脏位)。


【真题 3】2021 年 408 第 28 题 · 请求分页虚实地址变换与改进型 CLOCK 置换模拟

题目 某请求分页存储系统的页大小为 4KB,按字节编址。系统给进程 P 分配 2 个固定的页框并采用改进型 Clock 置换算法,进程 P 页表的部分内容如下表所示:

页号 页框号 存在位 (Valid) 访问位 (Access) 修改位 (Modified)
2 - 0 0 0
3 60H 1 1 0
4 80H 1 1 1

若 P 访问虚拟地址为 02A01H 的存储单元,则经地址变换后得到的物理地址是( )。 A. 00A01H
B. 20A01H
C. 60A01H
D. 80A01H

【解析】

  1. 知识定位:考查请求分页系统中虚拟地址分解、缺页异常触发、改进型 CLOCK 算法状态迁移推导以及物理地址合成的端到端综合计算。
  2. 第一步:虚拟地址切分与缺页检测:
  3. 页面大小为 \(4\text{KB} = 2^{12}\text{B}\),系统按字节编址,故页内偏移量占用低 12 位(即十六进制低 3 位),剩余高位表示虚拟页号。
  4. 访问的虚拟地址为 02A01H:
    • 页内偏移量(低 12 位)为:A01H;
    • 虚拟页号(高位)为:02H,即页号 2。
  5. 检索页表:查页表中页号 2 的行,其“存在位”为 \(0\)。这表明该页尚未调入主存,系统触发缺页中断异常。
  6. 第二步:驻留集检查与置换算法介入:
  7. 系统给进程 P 仅分配了 2 个固定物理页框。
  8. 观察页表中存在位为 1 的记录:页号 3 占用页框 60H,页号 4 占用页框 80H,已占用全部 2 个页框,必须淘汰一个驻留页。
  9. 初始指针指向驻留集的首个页面(页号 3),驻留页初始状态为:
    • 页号 3:\((A=1, M=0)\)
    • 页号 4:\((A=1, M=1)\)
  10. 第三步:改进型 CLOCK 算法逐步推演:
  11. 第 1 轮扫描(寻找 \((0, 0)\)$ \text{,不修改} $\(A\)):
    • 指针检查页号 3:状态为 \((1, 0) \ne (0, 0)\),未命中;
    • 指针检查页号 4:状态为 \((1, 1) \ne (0, 0)\),未命中。
    • 第 1 轮未找到可淘汰页面,指针回到页号 3。
  12. 第 2 轮扫描(寻找 \((0, 1)\)$ \text{,并将遍历页面的} $\(A\)$ \text{位置} $\(0\)):
    • 指针检查页号 3:当前状态为 \((1, 0) \ne (0, 1)\)$ \text{,未命中。同时将其访问位清零:} $\(A \leftarrow 0\)$ \text{,页号 3 状态变为} $\((0, 0)\)。
    • 指针检查页号 4:当前状态为 \((1, 1) \ne (0, 1)\)$ \text{,未命中。同时将其访问位清零:} $\(A \leftarrow 0\)$ \text{,页号 4 状态变为} $\((0, 1)\)。
    • 第 2 轮扫描结束,仍未找到初始的 \((0, 1)\),指针再次回到页号 3。
  13. 第 3 轮扫描(重新寻找 \((0, 0)\)$ \text{,不修改} $\(A\)):
    • 指针首先检查页号 3:由于在第 2 轮中其访问位已被清零,此时页号 3 的状态恰好为 \((0, 0)\)。
    • 判定命中:选择页号 3 作为淘汰页面!
    • 指针指向下一位置(页号 4),置换算法执行结束。
  14. 第四步:页框回收与物理地址合成:
  15. 被淘汰的页号 3 所占用的物理页框号为 60H(由于其 \(M=0\),无需写回磁盘,直接覆盖)。
  16. 操作系统将目标页号 2 调入该空闲页框 60H,并更新页表中页号 2 的页框号为 60H,存在位置 \(1\)。
  17. 将物理页框号与页内偏移量进行位拼接: $$ \text{物理地址} = \text{页框号} \parallel \text{页内偏移量} = 60\text{H} \parallel \text{A01H} = 60\text{A}01\text{H} $$
  18. 选项排除分析:
  19. A 选项(00A01H):页框号 00H 在页表中无对应记录,计算错误。
  20. B 选项(20A01H):误将虚页号 02H 与页框号混淆,计算错误。
  21. C 选项(60A01H):推导完全正确。
  22. D 选项(80A01H):如果考生机械地认为第 2 轮扫描时页号 4 被清零为 \((0, 1)\)$ \text{后立即满足第 2 轮条件而淘汰页号 4,则会误选 D。实际上第 2 轮判断的是扫描前该页的原始状态,由于页号 4 初始为} $\((1, 1)\)$ \text{,在第 2 轮仅做置零处理,不能在第 2 轮作为} $\((0, 1)\) 被淘汰,故 D 错误。

正确答案:C


四、 综合考法拓展

1. 综合大题中的全链路考法设计

408 操作系统综合解答题(45 题)通常将 CLOCK 页面置换算法置于计算机体系结构与操作系统的交汇点,考查完整的虚实地址转换与异常处理生命周期。典型出题脉络如下图所示:

       虚拟地址 (VA)
            |
            v
     [切分:VPN + Offset]
            |
            v
     TLB 命中检索 ---------命中--------> 拼接物理地址 (PA)
            | (未命中)
            v
     查页表项 (PTE)
            |
    +-------+-------+
    |               |
(存在位 P=1)    (存在位 P=0, 触发缺页异常)
    |               |
    v               v
拼接物理地址    操作系统介入:检查驻留集是否已满
                    |
            +-------+-------+
            |               |
         (未满)           (已满)
            |               |
      分配空闲页框     执行 CLOCK / 改进型 CLOCK 算法
                            |
                     扫描选定被淘汰页
                            |
                   检查修改位 M 是否为 1
                            |
                     +------+------+
                     |             |
                  (M = 0)       (M = 1)
                     |             |
                 直接覆盖      写回外存磁盘
                     |             |
                     +------+------+
                            |
                     从外存读入新页
                            |
                     更新 PTE 映射 (置 P=1, A=1, M=0)
                            |
                     重新执行触发缺页的访存指令

2. 解题推演模板:改进型 CLOCK 四步推导法

当综合题或选择题给出驻留集各页的 \((A, M)\) 状态并要求推演淘汰页时,建议考生在草稿纸上采用表格化指针推演法:

【解题四步模板】
第 1 步:标记指针起始位置,列出所有候选页的初始二元组 (A, M);
第 2 步:第 1 轮扫描,沿指针方向寻找第一个 (0, 0),若存在则直接选中,不改任何位;
第 3 步:第 2 轮扫描(若第 1 轮未命中),寻找第一个 (0, 1);
        注意:检查时必须依据该页进入本轮前的 A 位,扫描过的页无论是否选中均执行 A <- 0;
第 4 步:第 3 轮扫描(若前两轮未命中),寻找经修改后变为 (0, 0) 的页,首个遇到的必定是原 (1, 0) 页。

3. 跨知识点综合辨析:与 Cache 写策略及文件缓冲区的映射关联

  • 与 Cache 写回策略的关联: 改进型 CLOCK 的修改位 \(M\) 本质上与 CPU 缓存中的“脏位(Dirty Bit)”机制完全一致。Cache 的写回法(Write-Back)仅在块被替换时判断脏位是否写回主存;页表中的修改位同样用于避免不必要的磁盘块写回,体现了计算机层次存储体系中统一的设计思想。
  • 与操作系统的页面缓冲池(Page Buffering)机制联动: 现代操作系统(如 Windows、Linux)在 CLOCK 算法基础上引入了页面缓冲算法。被淘汰的页面不立即释放或写回磁盘,而是根据修改位状态分别挂入空闲页面链表或修改页面链表。若该页在被覆盖前再次被访问,只需将其从链表移回驻留集,避免了昂贵的磁盘 I/O。

五、 考点速记清单

1. 核心要点极简速记

  1. 简单 CLOCK:仅含访问位 \(A\)$ \text{,循环链表扫描。遇到} $\(1\)$ \text{改} $\(0\)$ \text{(给机会),遇到} $\(0\)$ \text{淘汰,最多扫描} $\(2\) 轮。
  2. 改进型 CLOCK:增加修改位 \(M\)$ \text{,状态二元组} $\((A, M)\)。首要原则保护被访问页,次要原则保护已修改页。
  3. 软硬件职责界定:
  4. 访问位置 \(1\)$ \text{、修改位置} $\(1\) \(\rightarrow\) MMU 硬件完成;
  5. 访问位清零、修改位清零(写回后) \(\rightarrow\) 操作系统内核完成。
  6. 复杂度界限:简单 CLOCK 最多遍历 \(2N\)$ \text{步,改进型 CLOCK 最多遍历} $\(3N + 1 \le 4N\) 步。

2. 改进型 CLOCK 四轮扫描口诀

一轮找 (0, 0) 不动位,
二轮找 (0, 1) 访问清,
三轮重找 (0, 0) 必命中,
四轮兜底 (0, 1) 算法终。

3. 易错陷阱排查清单

  • 陷阱 1:轮次与清除标志的时机混淆
    第 1 轮寻找 \((0, 0)\)$ \text{时绝对不修改访问位} $\(A\)$ \text{;只有在第 1 轮完全失败进入第 2 轮时,扫描经过的页面才被置} $\(A=0\)。
  • 陷阱 2:误将当前轮清零的新状态代入当前轮匹配
    在第 2 轮中,页面 \((1, 1)\)$ \text{被置为} $\((0, 1)\)$ \text{。该页面在第 2 轮中不能作为} $\((0, 1)\)$ \text{立即被淘汰!因为该页在被扫描前的真实状态是} $\((1, 1)\)$ \text{,其变为} $\((0, 1)\) 只能供第 4 轮淘汰使用(2021 年第 28 题的关键解题陷阱)。
  • 陷阱 3:物理地址合成计算时的进制位混淆
    页大小为 \(4\text{KB} = 2^{12}\text{B}\)$ \text{时,页内偏移占} $\(12\)$ \text{位二进制,对应} $\(3\) 位十六进制字符。地址拼接时切忌将十进制页框号与十六进制偏移量直接数字串联,必须保证统一转换为十六进制后再进行高低位拼装。