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\))。
- 数据结构:所有驻留主存的页面通过指针链接成一个逻辑上的循环单链表(环形队列),并由一个置换指针(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)模型与优化机理¶
在分页虚拟存储系统中,考虑缺页中断与页面置换的平均访存时间模型定义如下:
- 符号定义:
- \(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)
【解析】¶
- 知识定位:考查改进型 CLOCK 算法在四种 \((A, M)\) 状态下的理论淘汰优先级。
- 算法执行次序推导:
- 改进型 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 位。
- 选项逐项判定:
- A 选项:
(0, 0), (0, 1), (1, 0), (1, 1),完全符合四轮扫描确定的优先级序列,判定正确。 - B 选项:错将 \((1, 0)\)$ \text{置于} $\((0, 1)\)$ \text{之前。若先淘汰} $\((1, 0)\),则违背了“优先淘汰未被访问页面”的局部性核心原则,判定错误。
- C 选项:错将 \((1, 1)\)$ \text{置于} $\((1, 0)\) 之前,颠倒了未修改页与修改页在同等访问条件下的置换代价,判定错误。
- D 选项:完全打乱了算法的优先级层级,判定错误。
正确答案:A
【真题 2】2018 年 408 第 45 题 · 改进型 CLOCK 算法的页表结构硬件支持¶
题目(节选自综合解答题第 (3) 问) 某 32 位虚拟存储系统采用二级分页存储管理,系统采用改进型 CLOCK 页面置换算法。 (3) 为了支持改进型 CLOCK 置换算法,需要在页表项中设置哪些字段?
【解析】¶
- 知识定位:考查支持改进型 CLOCK 置换算法所需的最小页表项字段集合及其软硬件协同机制。
- 核心字段分析与采分要点:
- 访问位(Reference Bit / Access Bit / 使用位 / 引用位):
- 设立必要性:反映该页在最近一个时间段内是否被读或写访问过。
- 硬件支持:当 CPU 发出访存指令并命中该页时,MMU 硬件电路自动将该位设置为 \(1\)。操作系统在执行 CLOCK 扫描时通过特权指令将其清零。
- 算法功能:用于区分页面访问活跃度,给予活跃页面(\(A=1\))保留在内存中的“第二次机会”。
- 修改位(Dirty Bit / Modify Bit / 脏位):
- 设立必要性:记录该页面调入主存后内容是否被写指令修改过。
- 硬件支持:当 CPU 执行写内存操作时,MMU 硬件电路自动将该位设置为 \(1\)。
- 算法功能:算法据此判断淘汰该页面时是否需要执行磁盘写回(Write-Back)I/O 操作。若修改位为 \(0\)$ \text{,可直接覆盖释放页框;若修改位为} $\(1\),必须在覆盖前将其写入外存对齐数据,以降低算法的平均 I/O 成本。
- 得分拓展辨析:
- 标准页表项中通常还包含物理页框号(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
【解析】¶
- 知识定位:考查请求分页系统中虚拟地址分解、缺页异常触发、改进型 CLOCK 算法状态迁移推导以及物理地址合成的端到端综合计算。
- 第一步:虚拟地址切分与缺页检测:
- 页面大小为 \(4\text{KB} = 2^{12}\text{B}\),系统按字节编址,故页内偏移量占用低 12 位(即十六进制低 3 位),剩余高位表示虚拟页号。
- 访问的虚拟地址为
02A01H:- 页内偏移量(低 12 位)为:
A01H; - 虚拟页号(高位)为:
02H,即页号 2。
- 页内偏移量(低 12 位)为:
- 检索页表:查页表中页号 2 的行,其“存在位”为 \(0\)。这表明该页尚未调入主存,系统触发缺页中断异常。
- 第二步:驻留集检查与置换算法介入:
- 系统给进程 P 仅分配了 2 个固定物理页框。
- 观察页表中存在位为 1 的记录:页号 3 占用页框
60H,页号 4 占用页框80H,已占用全部 2 个页框,必须淘汰一个驻留页。 - 初始指针指向驻留集的首个页面(页号 3),驻留页初始状态为:
- 页号 3:\((A=1, M=0)\)
- 页号 4:\((A=1, M=1)\)
- 第三步:改进型 CLOCK 算法逐步推演:
- 第 1 轮扫描(寻找 \((0, 0)\)$ \text{,不修改} $\(A\)):
- 指针检查页号 3:状态为 \((1, 0) \ne (0, 0)\),未命中;
- 指针检查页号 4:状态为 \((1, 1) \ne (0, 0)\),未命中。
- 第 1 轮未找到可淘汰页面,指针回到页号 3。
- 第 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。
- 第 3 轮扫描(重新寻找 \((0, 0)\)$ \text{,不修改} $\(A\)):
- 指针首先检查页号 3:由于在第 2 轮中其访问位已被清零,此时页号 3 的状态恰好为 \((0, 0)\)。
- 判定命中:选择页号 3 作为淘汰页面!
- 指针指向下一位置(页号 4),置换算法执行结束。
- 第四步:页框回收与物理地址合成:
- 被淘汰的页号 3 所占用的物理页框号为
60H(由于其 \(M=0\),无需写回磁盘,直接覆盖)。 - 操作系统将目标页号 2 调入该空闲页框
60H,并更新页表中页号 2 的页框号为60H,存在位置 \(1\)。 - 将物理页框号与页内偏移量进行位拼接: $$ \text{物理地址} = \text{页框号} \parallel \text{页内偏移量} = 60\text{H} \parallel \text{A01H} = 60\text{A}01\text{H} $$
- 选项排除分析:
- A 选项(
00A01H):页框号00H在页表中无对应记录,计算错误。 - B 选项(
20A01H):误将虚页号02H与页框号混淆,计算错误。 - C 选项(
60A01H):推导完全正确。 - 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. 核心要点极简速记¶
- 简单 CLOCK:仅含访问位 \(A\)$ \text{,循环链表扫描。遇到} $\(1\)$ \text{改} $\(0\)$ \text{(给机会),遇到} $\(0\)$ \text{淘汰,最多扫描} $\(2\) 轮。
- 改进型 CLOCK:增加修改位 \(M\)$ \text{,状态二元组} $\((A, M)\)。首要原则保护被访问页,次要原则保护已修改页。
- 软硬件职责界定:
- 访问位置 \(1\)$ \text{、修改位置} $\(1\) \(\rightarrow\) MMU 硬件完成;
- 访问位清零、修改位清零(写回后) \(\rightarrow\) 操作系统内核完成。
- 复杂度界限:简单 CLOCK 最多遍历 \(2N\)$ \text{步,改进型 CLOCK 最多遍历} $\(3N + 1 \le 4N\) 步。
2. 改进型 CLOCK 四轮扫描口诀¶
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\) 位十六进制字符。地址拼接时切忌将十进制页框号与十六进制偏移量直接数字串联,必须保证统一转换为十六进制后再进行高低位拼装。