缓存算法 #03：Clock 与 CLOCK-Pro

Clock 算法是操作系统页面置换的经典算法，用一个循环缓冲区和"引用位"近似实现 LRU，避免了 LRU 精确实现的大量链表操作开销。CLOCK-Pro 在此基础上引入冷热页分类，接近最优置换。本文深入伪代码级别，追踪指针运动轨迹。

相关文章：LRU（最近最少使用） · LFU（最少使用频率） · ARC（自适应替换缓存）

目录

问题背景

操作系统管理物理内存页（page frame），当发生缺页中断时需要选一个页驱逐：

精确 LRU 的问题：
  每次内存访问都需要更新链表（移到头部）
  内存访问频率极高（每条指令都可能访问内存）
  → 链表操作的开销比页面读写本身还大 → 不实用

Clock 的解法：
  不维护精确顺序，只记录每页的"引用位"（1 bit）
  用一个时钟指针定期扫描，找到引用位=0 的页驱逐
  命中时只需设置引用位=1，极低开销
  代价：近似 LRU，不是精确 LRU，但工程上足够好

Clock 算法

数据结构

Frame {
    page_id:  int    // 存储的页编号（-1 表示空帧）
    ref_bit:  0|1    // 引用位：最近是否被访问过
}

ClockCache {
    frames:  Frame[N]   // N 个页帧，排列成环
    hand:    int        // 时钟指针，指向下一个候选驱逐帧，初始=0
    page_map: HashMap<page_id, frame_index>  // 快速定位某页在哪个帧
}

关键约定：

• 页被访问（读/写）时：ref_bit = 1
• 时钟指针扫描到某帧时：若 ref_bit=1，置为 0 并跳过；若 ref_bit=0，驱逐该帧

完整伪代码

access(page_id)（页面访问入口）

access(page_id):
    if page_id in page_map:
        // 命中（Cache Hit）
        frame_idx = page_map[page_id]
        frames[frame_idx].ref_bit = 1    // 仅设置引用位，不移动指针
        return frames[frame_idx]

    else:
        // 缺页（Cache Miss）
        evict_and_load(page_id)

evict_and_load(page_id)（核心：找到驱逐帧）

evict_and_load(page_id):
    // 时钟指针扫描，找 ref_bit=0 的帧
    while True:
        frame = frames[hand]

        if frame.page_id == -1:
            // 空帧，直接使用（冷启动阶段）
            break

        if frame.ref_bit == 0:
            // 引用位=0，可以驱逐
            break

        if frame.ref_bit == 1:
            // 引用位=1：给它一次机会，清零后继续扫描
            frame.ref_bit = 0
            hand = (hand + 1) % N    // 指针前进

    // 驱逐当前帧指向的页（如果有）
    if frame.page_id != -1:
        del page_map[frame.page_id]  // 从 page_map 移除
        // 如果该页是脏页（被修改过），此处需要写回磁盘

    // 加载新页
    frame.page_id = page_id
    frame.ref_bit = 1               // 新加载的页标记为"已引用"
    page_map[page_id] = hand

    hand = (hand + 1) % N           // 指针前进，下次从下一帧开始

执行追踪

N=4 个帧，初始全空， 依次访问页：1, 2, 3, 4, 1, 5, 2

初始状态：
  帧:   [空(-), 空(-), 空(-), 空(-)]
  ref:  [ 0,    0,    0,    0   ]
  hand: 0

access(1)：缺页，hand=0，帧0为空 → 直接用
  帧:   [1(↑),  空,   空,   空  ]   ↑表示hand指向此处
  ref:  [ 1,    0,    0,    0  ]
  hand: 1

access(2)：缺页，hand=1，帧1为空
  帧:   [1,    2(↑),  空,   空  ]
  ref:  [1,    1,    0,    0   ]
  hand: 2

access(3)：缺页，hand=2 → 帧2空
  帧:   [1,    2,    3(↑),  空  ]
  ref:  [1,    1,    1,    0   ]
  hand: 3

access(4)：缺页，hand=3 → 帧3空
  帧:   [1,    2,    3,    4(↑) ]
  ref:  [1,    1,    1,    1   ]
  hand: 0（回绕）

access(1)：命中！frame[0].ref_bit = 1（已经是1，保持）
  帧:   [1(↑), 2,    3,    4   ]
  ref:  [1,    1,    1,    1   ]   ← 全部=1！
  hand: 0（不移动，命中不移动指针）

access(5)：缺页，hand=0，开始扫描：
  frame[0] ref=1 → 置0，hand=1
  frame[1] ref=1 → 置0，hand=2
  frame[2] ref=1 → 置0，hand=3
  frame[3] ref=1 → 置0，hand=0（回绕）
  frame[0] ref=0 → 驱逐页1，加载页5
  帧:   [5(↑), 2,    3,    4   ]
  ref:  [1,    0,    0,    0   ]
  hand: 1

  注意：页1刚才被access(1)设了ref=1，
        但扫描时被清零，最终还是被驱逐
        ← 这是 Clock 近似 LRU 的精度损失之处

access(2)：命中，frame[1].ref_bit = 1
  帧:   [5,    2(↑), 3,    4   ]
  ref:  [1,    1,    0,    0   ]

Clock vs LRU

CLOCK-Pro

Clock 的局限：引用位是单 bit，无法区分"频繁访问"和"偶尔访问一次"。

CLOCK-Pro 的改进：引入冷热页分类，解决一次性顺序扫描造成的缓存污染。

核心思想

每个页有两种属性：
  热页（hot）：被访问过至少 2 次（短时间内）
  冷页（cold）：只被访问过 1 次或长时间未访问

驱逐策略：优先驱逐冷页（仅访问一次的页，未来重用概率低）

数据结构扩展

Frame {
    page_id:   int
    hot:       bool    // true=热页，false=冷页
    ref_bit:   0|1     // 引用位
    test_bit:  0|1     // 测试位：刚被驱逐的页保留短时记忆
}

三个时钟指针（对应三个环形扫描区）：
  hand_hot：扫描热页，将久未被再访问的热页降级为冷页
  hand_cold：扫描冷页，找 ref_bit=0 的冷页驱逐
  hand_test：清理测试期结束的页

CLOCK-Pro 访问逻辑

access(page_id)：

  if page_id 在缓存（热页或冷页）：
    if 热页：  ref_bit = 1（保持热）
    if 冷页：  ref_bit = 1，标记为热页候选（下次扫描时升级）

  elif page_id 在 test 区（刚被驱逐，还有记忆）：
    // 被驱逐后又很快访问 → 说明驱逐失误 → 升级为热页
    升级为热页
    运行 hand_hot 降级一个热页（保持热页数量平衡）

  else：
    // 全新缺页，作为冷页加载
    运行 hand_cold 找一个冷页驱逐
    加载新页为冷页，ref_bit=0，进入测试期

异常场景

所有帧的 ref_bit 全为 1

场景：工作集大小 = 缓存大小，所有页都在反复使用

Clock 行为：
  手指需要完整扫描一圈（N 步），将所有 ref_bit 清 0
  再扫一圈找到 ref_bit=0 的帧驱逐
  最坏情况：2N 步才能完成一次驱逐

影响：驱逐开销从 O(1) 退化到 O(N)
优化：
  如果扫描一圈后还是全为 1，直接驱逐 hand 当前位置的页
  （此时随机驱逐，近似于随机置换 RAND）

缓存抖动（Thrashing）

场景：工作集 = 100 页，缓存只有 80 帧

无论用什么算法，缺页率都趋近于 100%
（物理内存不够装下完整工作集）

Clock 无法解决，根本原因是缓存容量不足
解法：增加物理内存，或减少并发进程数，或使用 mlock 固定关键页

工程应用

PostgreSQL Clock-Sweep 细节

// PostgreSQL 的 usagecount 是 0~5 的计数器，而非单 bit
// 命中时：usagecount = min(usagecount+1, 5)
// 扫描时：usagecount > 0 → usagecount -= 1，跳过
//         usagecount = 0 → 驱逐

// 比单 bit 引用位更精细：
//   热门页（usagecount=5）需要被扫描 5 次才能被驱逐
//   冷门页（usagecount=1）被扫描 1 次即驱逐

参考资料

• Jiang, S. & Zhang, X. (2005). CLOCK-Pro: An Effective Improvement of the CLOCK Replacement
• PostgreSQL Buffer Manager: https://www.postgresql.org/docs/current/storage-buffer.html
• 《Operating Systems: Three Easy Pieces》Ch.22 — Beyond Physical Memory: Policies