Appearance
CLOCK 与改进 CLOCK 算法
LRU 的想法是对的，但它太贵了
LRU 的规则本身没问题，问题在代价压错了地方：为了知道"谁最后一次访问最早"， 它必须在每一次访存（包括命中）时更新时间戳或调整链表。 而访存次数比缺页多好几个数量级——把开销放在最热的路径上，这笔账划不来。
上一节末尾那条"精度换开销"的轴已经指明了方向：少记一点。 附加引用位法用
所以 CLOCK 不是另起炉灶，它是这条轴上最省的一档。 换个角度看，它也可以说成是 FIFO 打了两个补丁：
FIFO 的病根是"命中不留痕" ⇒ 加 1 位访问位 A，让命中留下痕迹， 轮到某页被淘汰时若 A=1 就放它一马、给第二次机会（这就是二次机会算法）⇒ 可"放一马"意味着要把它从队头搬到队尾，搬页很麻烦 ⇒ 把队列改成环形、用指针移动代替搬页，得到简单 CLOCK。
再补一刀就是改进 CLOCK：淘汰时除了考虑"还用不用"（A）， 再考虑"脏不脏"（M）——脏页要多写一次磁盘。两个比特分出四类， 而这四类的淘汰优先级怎么排，是本节唯一真正需要理解的东西， 它靠的不是记忆，是比较两种"选错"各自的代价。
交互可视化
一、CLOCK 是怎么从 FIFO 长出来的
不要把 CLOCK 当成一个新算法去背，它是在 FIFO 上打了两个补丁的结果，推导链只有三步：
- FIFO 的病根是"命中不留痕"——页面被访问一万次和一次，在队列里位置完全一样，热点页照样被排到队头淘汰（FIFO 篇）。
- 那就让命中留下痕迹，但只留最便宜的那一点。精确记录"最后访问时刻"要软件在每次访存时写内存（LRU 篇），太贵；退而求其次只记 1 个比特——这一页从上次被检查以来有没有被访问过。这个比特就是页表项里的访问位 A，由硬件在地址变换成功时自动置 1。
- 把这个比特接进 FIFO 的淘汰规则：队头页若 A=1，说明它虽然"住得久"但"最近还在用"，把它的 A 清 0、放回队尾，给它第二次机会。
二次机会与 CLOCK 的淘汰规则完全相同，差别只在数据结构：二次机会用线性队列，"给第二次机会"要把结点真的从队头摘下接到队尾；CLOCK 用环形队列 + 一个指针，页面原地不动，只让指针前移一格。所以"CLOCK 是二次机会的环形实现"是准确的说法。
二、访问位 A 的生命周期
这一格信息量很小，但它的时间语义是理解 CLOCK 的关键。
| 动作 | 由谁做 | 什么时候做 | 开销 |
|---|---|---|---|
| A ← 1 | 硬件（MMU） | 每次通过该页表项完成地址变换时自动置位 | 0（与访存合并） |
| A ← 0 | 软件（置换算法本身） | 只在指针扫过这一页时清 | 摊在缺页处理里 |
| M ← 1 | 硬件（MMU） | 该页被写时置位 | 0 |
| M ← 0 | 软件 | 该页被写回磁盘之后 | 摊在写盘里 |
第二行推出两个性质：缺页越频繁，指针转得越快，A 的时间分辨率越细——这是一个不需要调参的自适应窗口；反过来，内存充裕、长时间不缺页时指针几乎不动，A 位就几乎没有区分度，CLOCK 会退化，但那时也无所谓，因为根本不需要置换。
三、简单 CLOCK（NRU）
所有页框组成一个循环链表（想象成钟表），一个时钟指针像秒针一样绕圈扫描，每个页面配一个访问位 A。
算法必然终止的理由在最坏情况上：指针转一整圈回到起点时，起点页的 A 已经在这一圈开头被自己清成 0，于是淘汰起点页。这一圈清零同时也是一次"全局重新计时"——把所有页的历史抹掉，只保留从此刻起的访问信息。
3 个页框的简单 CLOCK 完整走查，含每步指针位置与缺页次数（想把"转满一圈"和"指针跨次保留"看在具体数据上时展开）
3 个页框，引用串 1, 2, 3, 1, 4, 2, 5, 1, 2, 3。页框按 框0 → 框1 → 框2 → 框0 环形排列，指针初始指向框 0，装入新页时该页 A=1。
| 访问 | 扫描过程 | 框0 | 框1 | 框2 | 指针停在 | 结果 |
|---|---|---|---|---|---|---|
| 1 | 有空闲框，不扫描 | 1(A=1) | — | — | 框0 | 缺页，装入 |
| 2 | 有空闲框，不扫描 | 1(A=1) | 2(A=1) | — | 框0 | 缺页，装入 |
| 3 | 有空闲框，不扫描 | 1(A=1) | 2(A=1) | 3(A=1) | 框0 | 缺页，装入 |
| 1 | 不扫描 | 1(A=1) | 2(A=1) | 3(A=1) | 框0 | 命中，页1 的 A 置 1 |
| 4 | 框0 页1：A=1→0，前移；框1 页2：A=1→0，前移；框2 页3：A=1→0，前移；回到框0 页1：A=0 → 淘汰 | 4(A=1) | 2(A=0) | 3(A=0) | 框1 | 缺页，淘汰页1，转满一圈 |
| 2 | 不扫描 | 4(A=1) | 2(A=1) | 3(A=0) | 框1 | 命中 |
| 5 | 框1 页2：A=1→0，前移；框2 页3：A=0 → 淘汰 | 4(A=1) | 2(A=0) | 5(A=1) | 框0 | 缺页，淘汰页3 |
| 1 | 框0 页4：A=1→0，前移；框1 页2：A=0 → 淘汰 | 4(A=0) | 1(A=1) | 5(A=1) | 框2 | 缺页，淘汰页2 |
| 2 | 框2 页5：A=1→0，前移；框0 页4：A=0 → 淘汰 | 2(A=1) | 1(A=1) | 5(A=0) | 框1 | 缺页，淘汰页4 |
| 3 | 框1 页1：A=1→0，前移；框2 页5：A=0 → 淘汰 | 2(A=1) | 1(A=0) | 3(A=1) | 框0 | 缺页，淘汰页5 |
缺页次数：8 次。 三处要点：
- 第 4 行（命中）只做了一件事——把页 1 的 A 置 1，没有改变任何页在环上的位置。
- 第 5 行是"转满一圈"的完整演示：三页 A 全是 1，指针依次清零走完一圈回到起点框 0，此时页 1 的 A 已被自己清成 0，于是淘汰起点页 1，不是别的页。
- 第 5 行之后指针停在框 1，第 7 行就从框 1 开始扫，不回到框 0。
四、改进 CLOCK
简单 CLOCK 只看页面是否被访问，没看它是否被修改。脏页换出时必须写回磁盘，代价比干净页多一次磁盘写。改进 CLOCK 把置换代价也纳入决策：
| 类别 | (A, M) | 含义 | 淘汰优先级 |
|---|---|---|---|
| 第 1 类 | (0, 0) | 未访问、未修改 | 最优先淘汰 |
| 第 2 类 | (0, 1) | 未访问、已修改 | 次优先 |
| 第 3 类 | (1, 0) | 已访问、未修改 | 再次 |
| 第 4 类 | (1, 1) | 已访问、已修改 | 最后淘汰 |
为什么 (0,1) 排在 (1,0) 前面
这是四类里唯一需要论证的一处——凭直觉很容易觉得"干净页更该走"，从而把 (1,0) 排到前面。判据是比较两种"选错"的代价：
| 选错了什么 | 直接代价 | 会不会连锁 |
|---|---|---|
| 淘汰了 (1,0)：访问位选错 | 这一页近期还在被用，很可能马上又缺页 | 会：一次缺页 = 一次中断 + 一次磁盘读，而且换它回来还要再淘汰另一页，可能引发下一轮 |
| 淘汰了 (0,1)：修改位选错 | 换出时多一次磁盘写 | 不会：写完就结束，这一页近期不再被访问，不会被要回来 |
"访问位"预测的是未来会不会再缺页，"修改位"只决定本次淘汰的一次性开销：前者可能连锁放大，后者是封顶的。所以先按 A 分成两大档，档内再按 M 排序。反过来记也行——先看"还用不用"，再看"脏不脏"。
扫描过程：最多 4 轮
第 3、4 轮必然成功：第 2 轮把扫过的所有页的 A 都清成了 0，于是原来的 (1,0) 全部变成 (0,0)、(1,1) 全部变成 (0,1)；而原本的 (0,0)、(0,1) 在第 1、2 轮就会被抓走，所以第 2 轮走完时环上只剩 (0,0) 和 (0,1) 两类，第 3 轮找前者、第 4 轮找后者，必有其一命中。
三组不同 (A,M) 初值分别走 2 轮 / 3 轮 / 4 轮的完整扫描（想看清"第 2 轮清零为什么是必要条件""4 轮上界怎么取到"时展开）
5 个页框，环形排列 P0 → P1 → P2 → P3 → P4 → P0，指针初始指向 P0，现发生缺页且无空闲页框。
| 页框 | 情形一 (A,M) | 情形二 (A,M) | 情形三 (A,M) |
|---|---|---|---|
| P0 | (1,1) | (1,1) | (1,1) |
| P1 | (1,0) | (1,0) | (1,1) |
| P2 | (0,1) | (1,1) | (1,1) |
| P3 | (1,1) | (1,1) | (1,1) |
| P4 | (1,0) | (1,0) | (1,1) |
情形一：2 轮结束，淘汰 P2
第 1 轮（找 (0,0)，不改任何位）：P0(1,1) 否、P1(1,0) 否、P2(0,1) 否、P3(1,1) 否、P4(1,0) 否——一圈无 (0,0)。第 1 轮不改位是为了保住 (0,1) 这一类的可识别性：一旦此时清了 A，后面就分不清"本来就没被访问"和"被我清掉了"。
第 2 轮（找 (0,1)，把扫过的页 A 清 0）：指针回到 P0 继续
| 检查 | 检查时 (A,M) | 是 (0,1)? | 动作 | 之后 (A,M) |
|---|---|---|---|---|
| P0 | (1,1) | 否 | 清 A，前移 | (0,1) |
| P1 | (1,0) | 否 | 清 A，前移 | (0,0) |
| P2 | (0,1) | 是 | 淘汰 P2，扫描结束 | — |
这一组数据的意义：环上同时存在 P1=(1,0)（干净但近期用过）和 P2=(0,1)（脏但近期没用过），算法选了 P2——宁可多写一次盘，也不动那个近期还在用的页。
情形二：3 轮结束，淘汰 P1（把 P2 初值改成 (1,1)，环上一个 (0,*) 都没有了）
- 第 1 轮：无 (0,0)，不改位。
- 第 2 轮：逐个清 A —— P0→(0,1)、P1→(0,0)、P2→(0,1)、P3→(0,1)、P4→(0,0)。检查时它们的 A 都还是 1，所以一个 (0,1) 都没匹配上，一圈走完仍失败。
- 第 3 轮：指针回到 P0，环上是 P0(0,1)、P1(0,0)、P2(0,1)、P3(0,1)、P4(0,0)。P0 不是 (0,0) 跳过；P1 是 (0,0) → 淘汰 P1。
P1 原来是 (1,0)，是第 2 轮的清零把它变成 (0,0) 才被抓住的。第 2 轮清 A 不是"顺手"，它是让第 3、4 轮能够成功的必要条件。
情形三：走满 4 轮，淘汰 P0（五页全是 (1,1)）
- 第 1 轮：无 (0,0)，不改位，失败。
- 第 2 轮：全部清 A → 五页全变 (0,1)；但检查时 A 都还是 1，无匹配，失败。
- 第 3 轮：五页现在全是 (0,1)，找 (0,0)，仍然失败。
- 第 4 轮：找 (0,1)，指针回到 P0，第一格就命中 → 淘汰 P0。
这一组说明"最多 4 轮"这个上界能被取到，也说明第 4 轮的落点——回到起点、淘汰起始页，与简单 CLOCK 转满一圈的结局一致。
五、四种页面置换算法对比
| 算法 | 决策依据 | 判断"该淘汰谁"的可操作方法 | 每次访存开销 | 需要的硬件 | 平均性能 | Belady 异常 |
|---|---|---|---|---|---|---|
| OPT | 未来最久不用 | 各页向后扫，取下次出现最晚者 | — | 不可实现 | 最优（逐串最优） | 无（栈算法） |
| LRU | 过去最久没用 | 各页比最后访问时刻，取最早者 | 写时间戳 / 改链表 | 计数器或栈 | 接近 OPT | 无（栈算法） |
| CLOCK | 近期有没有被访问 | 指针扫，A=0 就淘汰、A=1 清零跳过 | 0 | 1 位访问位 | 接近 LRU | 可能 |
| FIFO | 最早进入内存 | 取队头 | 0 | 无 | 最差 | 有 |
最该横着读的是第四、五列：CLOCK 用"1 位访问位 + 零访存开销"换来了"接近 LRU 的性能"，代价只是丢掉了栈算法性质。这就是它在真实系统里胜出的全部理由——访存每秒上亿次，置换只在缺页时发生，把开销从访存路径挪到缺页路径上永远划算。
简单 CLOCK 与改进 CLOCK 的分工则在另一维：后者多要一个修改位，换来的是减少写回次数这一项 I/O 优化，代价是最多扫 4 轮而不是 2 圈。Unix／Linux 的页面置换机制正是以 CLOCK 的变体为主——这条事实本身就是上面那笔账的验收结果：真实系统选的不是性能最好的算法，而是"性能够用且访存路径不花钱"的那个。
考点速记
- 简单 CLOCK 规则：指针所指页 A=0 就淘汰（新页装入此框、置 A=1、指针前移）；A=1 就清 0、指针前移、继续扫。它又称 NRU（Not Recently Used），因为只能区分"最近用没用过"。
- 转满一圈的结局：回到起点时，起点页的 A 已在这一圈开头被自己清成 0 ⇒ 淘汰起点页。扫描不超过
格——这就是"最多 2 圈"的来历。 - ⚠️指针位置跨次缺页保留：下一次缺页从上次停下的地方接着扫，不回到框 0。手算时最容易漏的一步。
- 命中时只把该页的 A 置 1，不改变任何页在环上的位置。 这是 CLOCK 与 LRU 的分野——LRU 会把它移到栈顶、彻底改变淘汰次序。
- 二次机会与 CLOCK 是同一个算法，只是线性队列与环形队列两种实现，任何引用串上缺页次数都相同。
- A 位没有固定周期的清零：置 1 由硬件（MMU 地址变换时自动，软件零开销）；清 0 只由置换算法自己做（指针扫过时）。所以 A 记录的窗口是"从指针上次扫过这一页到现在"，随缺页频率自适应伸缩——与 LRU 附加引用位法"按固定周期由时钟中断清零"截然不同。
- 改进 CLOCK 的淘汰优先级：(0,0) ＞ (0,1) ＞ (1,0) ＞ (1,1)。
- 为什么 (0,1) 排在 (1,0) 前面——比较两种"选错"的代价：淘汰 (1,0) 选错 ⇒ 这页近期还在用 ⇒ 再缺一次页（中断 + 磁盘读，换它回来还要再淘汰一页，可能连锁）；淘汰 (0,1) 选错 ⇒ 只多一次磁盘写，写完就完，不连锁。⇒ A 的权重必须高于 M：先看"还用不用"，再看"脏不脏"。
- 改进 CLOCK 最多 4 轮：第 1 轮找 (0,0) 不动任何位（动了就分不清"本来 A 就是 0"和"被我清成 0"，(0,1) 这一类会被污染）；第 2 轮找 (0,1) 并清扫过页的 A；清零把 (1,0)→(0,0)、(1,1)→(0,1)，故第 3 轮必抓前者、第 4 轮必抓后者。每轮从上一轮停下处继续扫。
- CLOCK 会出现 Belady 异常：判据不看"它近似谁"，只看排序依不依赖页框数——环上位置由装入时刻决定，装入时刻依赖
⇒ 不是栈算法，简单 CLOCK 与改进 CLOCK 都可能出现。
这一节在真题里被考过的形式：
改进 CLOCK 的出题密度高于简单 CLOCK，而且考法很整齐： 要么直接问四类的淘汰次序，要么把它嵌进一道地址变换题里当中间步骤。
- 直接问改进型 CLOCK 淘汰页的次序（2016-26）。答 (0,0), (0,1), (1,0), (1,1)。⚠️ 唯一的干扰点就是 (0,1) 和 (1,0) 谁在前——四个选项里有两个专门在这里做文章。别去背，用速记第八条推：淘汰错一个还要用的页，代价是再缺一次页并可能连锁；淘汰错一个脏页，代价只是多写一次盘。所以 A 位的权重高于 M 位。
- 给页表和 (A, M) 状态，先做地址变换、缺页后用改进 CLOCK 选受害者、再拼物理地址（2021-28）。流程是拆地址 → 查页表发现存在位为 0 → 跑改进 CLOCK 选淘汰页 → 用腾出的页框号拼物理地址。⚠️ 这类题把本章三节的内容串成一条链，任何一环错都全错；尤其注意页内偏移在拼接时原样保留、不参与任何计算。
- 给页表和 CLOCK 指针初始位置，求物理地址（2010-46 第 3 问；第 1、2 问的 FIFO 部分见 FIFO 算法）。⚠️ 这一问的关键是指针从题目指定的位置开始扫，而不是从 0 号页框——题面特意写明"当前指向 2 号页框"就是为此。表中四页访问位全是 1，所以第一圈全在清零，转回起点时淘汰的正是起点那一页（速记第二条）。
复习优先级：必须拿满，且要能手算。 四类淘汰次序是送分题， 但一定要用第八条那个代价比较去推而不是背，因为背反的概率很高。 手算时盯死两处：指针跨次缺页保留位置、第 1 轮不清 A 位。 速记第十条（CLOCK 也会 Belady）是性质考点，容易因为"CLOCK 近似 LRU"而误判。
易错：把改进 CLOCK 的次序记成 (0,0), (1,0), (0,1), (1,1)。A 的权重高于 M，所以 (0,1) 在 (1,0) 之前。
易错：手算时每次缺页都让指针从 0 号页框重新开始。指针位置跨次缺页保留。
易错：改进 CLOCK 第 1 轮就清访问位。第 1 轮不动任何位，否则 (1,0) 会被误当成 (0,0)、污染分类。
易错：认为 CLOCK 近似 LRU 所以不会 Belady 异常。判据是排序依不依赖页框数——环上位置由装入时刻定，会出现。
易错：认为 CLOCK 命中时要调整页在环上的位置。命中只置 A=1，位置不动。
易错：认为 A 位由操作系统定期清零。置 1 由硬件，清 0 只在指针扫过时由置换算法做，没有固定周期。
易错：认为二次机会算法和 CLOCK 是两种算法。淘汰规则完全相同，任何引用串上缺页次数都一样。
教材出处
- 简单 Clock 置换算法的访问位、循环队列、"A=1 则置 0 并给予该页第二次驻留内存的机会"、以及它又称 NRU（Not Recently Used）：汤小丹《计算机操作系统》5.3.3 节「简单的 Clock 置换算法」，p166
- 改进型 Clock 的置换代价考虑、(A,M) 四类页面的划分与含义、三步执行过程（第一轮不改访问位、第二轮将扫描过的页访问位置 0、第三步返回重复前两步）：同书 5.3.3 节「改进型 Clock 置换算法」，p167
相关知识
FIFO 页面置换算法｜LRU 页面置换算法｜OPT 最佳置换算法｜页框分配与回收｜页面置换模拟器