Appearance
Cache替换算法与写策略
考情分析
替换算法的命中率比较和写策略的适用场景是 408 选择题常见考点。LRU 和 FIFO 的手算模拟、写直达与写回的区别要掌握。
替换算法
Cache 满时，需要替换一行以装入新的数据块，由此引出替换算法。
直接映射没有替换选择（新块只能放在固定行），替换算法主要针对全相联和组相联映射。
LRU（最近最少使用）
替换最长时间未被访问的行。
- 效果：最接近 Belady 最优算法，命中率最高
- 实现：需要硬件维护每行的访问时间戳或 LRU 计数器
- 具有栈性质：路数
增大时命中率不会下降（不会出现 Belady 异常）
手算示例（4路组相联，追踪访问序列）：
维护一个按最近访问顺序排列的队列，队头是最近使用，队尾是最久未用。新块装入时替换队尾，命中时将该块移到队头。
FIFO（先进先出）
替换最早装入 Cache 的行，与访问频率无关。
- 实现简单：维护一个循环指针
- 命中率低于 LRU
- 没有栈性质：可能出现 Belady 异常（路数增加反而命中率下降）
LFU（最不经常使用）
替换访问次数最少的行。
- 需要计数器，硬件开销较大
- 对周期性的大量数据访问效果差（新装入的块计数为 0，容易被替换）
随机替换（RAND）
随机选择一行替换，最简单，命中率最低，但实现开销极小。
替换算法对比
| 算法 | 命中率 | 实现复杂度 | Belady 异常 |
|---|---|---|---|
| LRU | 最高 | 中等（计数器） | 无 |
| FIFO | 低 | 简单（指针） | 有 |
| LFU | 较高 | 较复杂 | 无 |
| 随机 | 最低 | 最简单 | 无 |
写策略
Cache 中的数据发生写操作时，如何保持 Cache 与主存的一致性？
写命中时
写直达（Write Through）
每次写 Cache，同时写主存。
- 优点：Cache 和主存始终一致，实现简单
- 缺点：每次写都要访问主存，速度慢（通常配合写缓冲器缓解）
写回（Write Back）
只写 Cache，不立即写主存。被替换时，若该行被修改过（脏位 Dirty=1），才写回主存。
- 优点：减少主存访问次数，速度快
- 缺点：Cache 与主存可能不一致；若 Cache 损坏会丢失数据
- 需要**脏位（Dirty Bit）**标记该行是否被修改过
写不命中时
写分配（Write Allocate）
将主存中的对应块调入 Cache，然后在 Cache 中执行写操作。
配合写回策略使用。
非写分配（No Write Allocate）
不将块调入 Cache，直接写主存。
配合写直达策略使用。
搭配规则
| 写命中策略 | 搭配的写不命中策略 |
|---|---|
| 写直达 | 非写分配 |
| 写回 | 写分配 |
交互可视化
例题：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 异常
- 写直达：写 Cache 同时写主存，始终一致；写回：只写 Cache，替换时才写回
- 写直达 + 非写分配；写回 + 写分配（固定搭配）
- 脏位（Dirty Bit）用于写回策略，标记该 Cache 行是否被修改
- 写缓冲器可以缓解写直达策略对主存带宽的冲击