Cache 替换算法

考情分析

替换算法的命中率比较是 408 选择题常见考点。LRU 和 FIFO 的手算模拟、Belady 异常的判定是必考要点。Cache 写策略（写直达/写回）已拆为独立文章，见「Cache 写策略」一文。

替换算法

Cache 满时，需要替换一行以装入新的数据块，由此引出替换算法。

直接映射没有替换选择（新块只能放在固定行），替换算法主要针对全相联和组相联映射。

LRU（最近最少使用）

替换最长时间未被访问的行。

• 效果：最接近 Belady 最优算法，命中率最高
• 实现：需要硬件维护每行的访问时间戳或 LRU 计数器
• 具有栈性质：路数 $k$ 增大时命中率不会下降（不会出现 Belady 异常）

术语说明：「Belady 最优算法」在很多教材和资料里写作 OPT（最优替换算法，Optimal，也记作 MIN），是同一个算法——每次替换"将来最长时间不会被用到"的块，命中率是所有算法的理论上界。因为它需要预知未来的访问序列，实际无法实现，只用作衡量其他算法好坏的标尺。

注意别和下文的「Belady 异常」搞混：两者都源自同一人（László Bélády），但 OPT 是一个理想算法，Belady 异常则是 FIFO 等算法"容量变大反而缺失增多"的反常现象，是两件不同的事。

手算示例（4路组相联，追踪访问序列）：

维护一个按最近访问顺序排列的队列，队头是最近使用，队尾是最久未用。新块装入时替换队尾，命中时将该块移到队头。

FIFO（先进先出）

替换最早装入 Cache 的行，与访问频率无关。

• 实现简单：维护一个循环指针
• 命中率低于 LRU
• 没有栈性质：可能出现 Belady 异常（路数增加反而命中率下降）

LFU（最不经常使用）

替换访问次数最少的行。

• 需要计数器，硬件开销较大
• 对周期性的大量数据访问效果差（新装入的块计数为 0，容易被替换）

随机替换（RAND）

随机选择一行替换，最简单，命中率最低，但实现开销极小。

替换算法对比

算法	命中率	实现复杂度	Belady 异常
LRU	最高	中等（计数器）	无（具栈性质）
FIFO	低	简单（指针）	有
LFU	较高	较复杂	—（408 不考查此性质）
随机	最低	最简单	—（408 不考查此性质）

Belady 异常：一个能复现的数字反例

"FIFO 有 Belady 异常"光背结论记不牢，亲手数一遍这个经典序列（访问块号）：

$$123412512345$$

3 个槽位（FIFO）：

访问	1	2	3	4	1	2	5	1	2	3	4	5
结果	缺	缺	缺	缺	缺	缺	缺	中	中	缺	缺	中

缺失 9 次（命中 3 次）。

4 个槽位（FIFO）：

访问	1	2	3	4	1	2	5	1	2	3	4	5
结果	缺	缺	缺	缺	中	中	缺	缺	缺	缺	缺	缺

缺失 10 次（命中 2 次）——容量变大，缺失反而变多，这就是 Belady 异常。根因：FIFO 淘汰"来得最早的"，而来得早不代表用得少；序列后半段 1、2 在 4 槽位时恰好刚被换出又被访问。LRU 按"最近使用"淘汰，具有栈性质（大容量的内容恒包含小容量的内容），不会出现此异常。

交互可视化

加载可视化中...

例题：LRU 替换手算

Cache 2 路组相联，初始为空，访问序列：A B C A D A B C D

步骤	访问	组0（2路）	命中?
1	A	[A, -]	Miss
2	B	[B, A]	Miss
3	C	[C, B]（替换 A）	Miss
4	A	[A, C]（替换 B）	Miss
5	D	[D, A]（替换 C）	Miss
6	A	[A, D]	Hit
7	B	[B, A]（替换 D）	Miss
8	C	[C, B]（替换 A）	Miss
9	D	[D, C]（替换 B）	Miss

命中率 = 1/9 ≈ 11%（2路 LRU，初始冷启动效果差）

考点清单

• LRU 命中率最高，有栈性质（路数增加命中率不会下降）
• FIFO 可能出现 Belady 异常（路数增加反而命中率下降），LRU/LFU/随机无此异常
• LFU 对周期性突发访问效果差（新装入块计数 0 容易被替换）
• 直接映射没有替换选择，替换算法主要用于组相联和全相联
• 写策略（写直达/写回、写分配/非写分配）见独立文章「Cache 写策略」

上一篇Cache 地址映射（直接/组相联/全相联）下一篇Cache 写策略

真题练习