CLOCK页面置换 · 融合风（象牙 + Obsidian 入口）

速查

CLOCK 是 LRU 的近似实现：给每个页面一个访问位 R，淘汰时给未访问页面"第二次机会"。简单CLOCK：$R=1$→置0跳过，$R=0$→淘汰。最多扫描两轮。

速查 ▾

项目	值
别名	时钟置换算法、第二次机会算法、近似LRU
核心思想	给每个页面一个访问位，淘汰时给未访问页面"第二次机会"
实现	循环链表 + 访问位（reference bit）
优势	实现简单，接近LRU性能

核心概念 ▾

CLOCK 算法是 LRU 的近似实现，用一个访问位（reference bit）代替精确的访问时间记录。

简单 CLOCK 算法：

所有页面组织成一个循环链表，指针从某位置开始
每个页面有一个访问位 R：被访问时置 1
缺页时，指针开始扫描：
- 若 $R=1$：将 R 置 0，指针前移（给"第二次机会"）
- 若 $R=0$：淘汰该页面，装入新页面

改进型 CLOCK 算法：

增加修改位 M（dirty bit）
优先淘汰未访问且未修改的页面（代价最小）
扫描顺序：① $R=0$且$M=0$ ② $R=0$且$M=1$ ③ $R=0$且$M=0$（第二轮） ④ $R=0$且$M=1$

关键性质 ▾

对比项	简单CLOCK	改进型CLOCK
位信息	只有访问位R	访问位R + 修改位M
淘汰优先级	$R=0$优先	$R=0,M=0 > R=0,M=1$
需要写回	不考虑	已修改页面需写回磁盘
性能	接近LRU	比简单CLOCK更好

常见考法 ▾

考法	解题套路
手算CLOCK	维护循环链表和指针，$R=1$→置0跳过，$R=0$→淘汰
改进型CLOCK	优先淘汰 $R=0,M=0$ 的页面
CLOCK vs LRU	CLOCK 是 LRU 的近似，实现更简单
访问位R的作用	区分最近是否被访问——$R=1$ 说明最近访问过

易错点 ▾

注意

CLOCK 扫描时，$R=1$ 的页面不会被淘汰——只是将 R 置 0 后跳过
改进型 CLOCK 优先淘汰 $R=0$ 且 $M=0$ 的页面（不需写回，代价最小）
CLOCK 需要两轮扫描才能淘汰所有页面
访问位 R 在每次页面访问时由硬件自动置 1
CLOCK 不是严格精确的 LRU——只是近似

核心结论 ▾

必背

CLOCK 用访问位 R 近似 LRU，实现简单且性能接近 LRU
简单 CLOCK：$R=1$→置0跳过，$R=0$→淘汰
改进型 CLOCK 增加修改位 M，优先淘汰未访问未修改的页面
CLOCK 最多扫描两轮就能找到淘汰页面
实际OS（如Linux）广泛使用 CLOCK 或其变体

记忆卡片 ▾

CLOCK 的核心思想？

用访问位 R 近似 LRU，$R=1$ 给第二次机会（置0跳过），$R=0$ 淘汰。

改进型 CLOCK 增加了什么？

修改位 M（dirty bit），优先淘汰 $R=0,M=0$ 的页面（代价最小）。

CLOCK 最多扫描几轮？

两轮——第一轮清除 R 位，第二轮找到 $R=0$ 的页面淘汰。

为什么优先淘汰 $R=0,M=0$？

未修改的页面不需要写回磁盘，淘汰代价最小。

CLOCK 和 LRU 的关系？

CLOCK 是 LRU 的近似实现，用 1 位访问位代替精确访问时间。

交互动画 · 时钟指针扫描 ▾

点击「扫描一步」，观察时钟指针如何处理访问位并找到淘汰页

每次缺页时指针启动；R=1置0跳过，R=0淘汰

本例 4 页初始 R=[1,0,1,0]；指针从 A 开始。

相关知识点

lru-page-replacement opt-page-replacement

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。