Appearance
Cache 替换算法
考情分析
替换算法的命中率比较是 408 选择题常见考点。LRU 和 FIFO 的手算模拟、Belady 异常的判定是必考要点。Cache 写策略（写直达/写回）已拆为独立文章，见「Cache 写策略」一文。
替换算法
Cache 满时，需要替换一行以装入新的数据块，由此引出替换算法。
直接映射没有替换选择（新块只能放在固定行），替换算法主要针对全相联和组相联映射。
LRU（最近最少使用）
替换最长时间未被访问的行。
- 效果：最接近 Belady 最优算法，命中率最高
- 实现：需要硬件维护每行的访问时间戳或 LRU 计数器
- 具有栈性质：路数
增大时命中率不会下降（不会出现 Belady 异常）
手算示例（4路组相联，追踪访问序列）：
维护一个按最近访问顺序排列的队列，队头是最近使用，队尾是最久未用。新块装入时替换队尾，命中时将该块移到队头。
FIFO（先进先出）
替换最早装入 Cache 的行，与访问频率无关。
- 实现简单：维护一个循环指针
- 命中率低于 LRU
- 没有栈性质：可能出现 Belady 异常（路数增加反而命中率下降）
LFU（最不经常使用）
替换访问次数最少的行。
- 需要计数器，硬件开销较大
- 对周期性的大量数据访问效果差（新装入的块计数为 0，容易被替换）
随机替换（RAND）
随机选择一行替换，最简单，命中率最低，但实现开销极小。
替换算法对比
| 算法 | 命中率 | 实现复杂度 | Belady 异常 |
|---|---|---|---|
| LRU | 最高 | 中等（计数器） | 无 |
| FIFO | 低 | 简单（指针） | 有 |
| LFU | 较高 | 较复杂 | 无 |
| 随机 | 最低 | 最简单 | 无 |
交互可视化
例题：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 写策略」