Appearance
Cache 替换算法
考情分析
替换算法的落点是命中率比较：LRU 与 FIFO 的手算模拟、Belady 异常的判定。两件事都要能在草稿纸上一步步走完，光记结论不够。Cache 写策略（写直达/写回）已拆为独立文章，见「Cache 写策略」一文。
大纲定位
考纲第三章（六）「高速缓冲存储器（Cache）」第 3 条：Cache 中主存块的替换算法。
要求到什么程度：能手算 LRU/FIFO 的替换过程并统计命中率，知道 LRU 计数器实现占几位（要计入 Cache 容量），能判定 Belady 异常。
替换算法
Cache 满时，需要替换一行以装入新的数据块，由此引出替换算法。
直接映射没有替换选择（新块只能放在固定行），替换算法主要针对全相联和组相联映射。
LRU（最近最少使用）
替换最长时间未被访问的行。
- 效果：最接近 Belady 最优算法，命中率最高
- 实现：需要硬件维护每行的访问时间戳或 LRU 计数器
- 具有栈性质：路数
增大时命中率不会下降（不会出现 Belady 异常）
术语说明：「Belady 最优算法」在很多教材和资料里写作 OPT（最优替换算法，Optimal，也记作 MIN），是同一个算法——每次替换"将来最长时间不会被用到"的块，命中率是所有算法的理论上界。因为它需要预知未来的访问序列，实际无法实现，只用作衡量其他算法好坏的标尺。
注意别和下文的「Belady 异常」搞混：两者都源自同一人（László Bélády），但 OPT 是一个理想算法，Belady 异常则是 FIFO 等算法"容量变大反而缺失增多"的反常现象，是两件不同的事。
LRU 的两种实现
栈（队列）法：维护一个按最近访问顺序排列的队列，队头是最近使用，队尾是最久未用。新块装入时替换队尾，命中时将该块移到队头。
编者注（卷面）：队列画成"左边是最近使用"还是"左边是最久未用"，两种约定都有人用，不同资料的画法可能相反。卷面上怎么画都行，但必须先声明一句（如"下表中每组内容按最近使用在左排列"），并全程保持一致——否则改卷时无法判断你淘汰的是哪一端。
计数器法（更需要掌握，因为它直接关系到 Cache 容量的计算）：
- 每行配一个计数器，
路组相联需 位（2 路 1 位、4 路 2 位、8 路 3 位） - 命中时：命中行的计数器清 0，同组中原计数值小于它的行各加 1，其余不变
- 未命中且组内有空行：装入该行，计数器清 0，同组其余行加 1
- 未命中且组已满：替换计数器最大的那一行，新行计数器清 0，其余加 1
计数器占的位要计入 Cache 总容量——这是容量计算题的常见漏项。
图 7.33 LRU 替换算法示例
教材这张图同时给了 3 行/组、4 行/组、5 行/组三种情形对同一访问序列的驻留情况。横向对比能直接看出栈性质：组内行数增加时，小容量的驻留集始终是大容量驻留集的子集，所以命中的次数只增不减。
FIFO（先进先出）
替换最早装入 Cache 的行，与访问频率无关。
- 实现简单：维护一个循环指针
- 命中率低于 LRU
- 没有栈性质：可能出现 Belady 异常（路数增加反而命中率下降）
LFU（最不经常使用）
替换访问次数最少的行。
- 需要计数器，硬件开销较大
- 对周期性的大量数据访问效果差（新装入的块计数为 0，容易被替换）
随机替换（RAND）
随机选择一行替换，最简单，命中率最低，但实现开销极小。
替换算法对比
| 算法 | 命中率 | 实现复杂度 | Belady 异常 |
|---|---|---|---|
| LRU | 最高 | 中等（计数器） | 无（具栈性质） |
| FIFO | 低 | 简单（指针） | 有 |
| LFU | 较高 | 较复杂 | —（408 不考查此性质） |
| 随机 | 最低 | 最简单 | —（408 不考查此性质） |
Belady 异常：一个能复现的数字反例
"FIFO 有 Belady 异常"光背结论记不牢，亲手数一遍这个经典序列（访问块号）：
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 替换手算
真题不会直接给你 A、B、C 这样的块符号，给的是字节地址序列。所以第一步永远是换算，不是画表。
题：Cache 共 4 行、2 路组相联、块大小 2 B，按字节编址，初始为空，LRU 替换。访问的字节地址依次为 0, 4, 8, 2, 0, 6, 8, 4。求命中率。
Step 1. 先算组数。
Step 2. 列换算表——地址 → 块号 → 组号，这一步做完题就做完一半了：
| 字节地址 | 0 | 4 | 8 | 2 | 0 | 6 | 8 | 4 |
|---|---|---|---|---|---|---|---|---|
| 块号 | 0 | 2 | 4 | 1 | 0 | 3 | 4 | 2 |
| 组号 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Step 3. 按组分栏模拟。两个组各有独立的 LRU 队列，访问落到哪个组就只动哪一栏，另一栏原样不动。
约定：下表每组内容按 最近使用在左 排列，替换时淘汰最右端。
| 步骤 | 地址 | 块号 | 落在 | 组 0 | 组 1 | 命中? |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 组0 | [0, -] | [-, -] | Miss |
| 2 | 4 | 2 | 组0 | [2, 0] | [-, -] | Miss |
| 3 | 8 | 4 | 组0 | [4, 2] 淘汰块0 | [-, -] | Miss |
| 4 | 2 | 1 | 组1 | [4, 2] | [1, -] | Miss |
| 5 | 0 | 0 | 组0 | [0, 4] 淘汰块2 | [1, -] | Miss |
| 6 | 6 | 3 | 组1 | [0, 4] | [3, 1] | Miss |
| 7 | 8 | 4 | 组0 | [4, 0] | [3, 1] | Hit |
| 8 | 4 | 2 | 组0 | [2, 4] 淘汰块0 | [3, 1] | Miss |
注意第 7 步：块 4 命中后队列顺序也要更新（从 [0, 4] 变成 [4, 0]），所以第 8 步淘汰的是块 0 而不是块 4。命中不更新顺序是这类题最常见的错法。
编者注（易错）：漏掉 Step 2 直接拿字节地址当块号，是这类题的头号失分点——地址 0 和 1 其实在同一块里。看到"块大小"这三个字就要想到先做除法。
考点清单
- LRU 命中率最高，有栈性质（路数增加命中率不会下降）
- FIFO 可能出现 Belady 异常（路数增加反而命中率下降），LRU/LFU/随机无此异常
- LFU 对周期性突发访问效果差（新装入块计数 0 容易被替换）
- 直接映射没有替换选择，替换算法主要用于组相联和全相联
- 写策略（写直达/写回、写分配/非写分配）见独立文章「Cache 写策略」