首页/计算机组成原理/存储器/Cache替换算法和写策略 🔗 在 Obsidian 中打开
计算机组成原理 · 存储器

Cache替换算法和写策略

重要度 ⭐⭐⭐⭐⭐存储器层次结构LRUFIFO写直达写回Cache存储器
速查
Cache 满时需替换算法决定淘汰哪一行（FIFO / LRU / LFU / 随机）；CPU 写 Cache 时需写策略维持一致性：写回法（只改 Cache、换出时写回）vs 写直达（同时写主存）。命中率 90% 以上，公式 $T_a = H \cdot T_c + (1-H) \cdot T_m$。

速查 ▾

项目值
替换算法FIFO、LRU、LFU、随机
写回法只修改 Cache，换出时写回主存
全写法同时写 Cache 和主存

概述 ▾

当 Cache 满或发生冲突时，需要替换算法决定替换哪一行。当 CPU 写 Cache 时，需要写策略决定如何保持 Cache 与主存的一致性。

直接映射无需替换直接映射每个主存块只能放在固定 Cache 行，新数据直接覆盖旧数据，无需选择。替换算法只在全相联和组相联（目标位置已被占用）时才需要。

替换算法 ▾

常见替换算法包括 LRU、FIFO、LFU 与随机替换，下面逐一说明。

LRU（最近最少使用） ▾

算法思想

替换最久没有被访问的行。

实现方式

计数器法：每行维护一个计数器；命中时该行清 0、其余 +1；替换时选计数器最大的行。

栈算法：维护访问栈，命中时该行移到栈顶，替换时选栈底（最久未访问）。

2 路组相联示例

访问序列：A B C A D B E
访问 A → 组0=[A,空]   未命中
访问 B → 组0=[A,B]    未命中
访问 C → 组0=[C,B]    替换 A（LRU）未命中
访问 A → 组0=[C,A]    替换 B 未命中
访问 D → 组0=[D,A]    替换 C 未命中
访问 B → 组0=[D,B]    替换 A 未命中
访问 E → 组0=[E,B]    替换 D 未命中
注意命中率较高、接近最优；但4 路以上 LRU 硬件成本高，常用近似 LRU（如时钟算法：每行 1 个引用位，循环扫描，引用位为 0 则替换）。

FIFO（先进先出） ▾

替换最早进入 Cache的行。每行记录进入时间或维护队列，新装入行排队尾，替换时选队首。

  • 实现简单
  • 命中率不如 LRU
  • 可能出现 Belady 异常（增加 Cache 行数反而降低命中率）

LFU / 随机替换 ▾

LFU（最不经常使用）

替换访问次数最少的行。每行维护访问计数器，访问 +1，替换时选最小者。需要较大计数器，历史数据可能过时，实际较少使用。

随机替换（Random）

随机选一行替换。实现最简单、命中率不稳定，用于某些 TLB。

替换算法对比 ▾

算法命中率实现复杂度Belady 异常
LRU高较复杂无
FIFO中简单有
LFU高复杂无
Random低最简单无
OPT最高不可实现无
OPT最优算法：替换未来最长时间内不会被访问的行。理论上最优但无法实现，用作对比基准。

写策略 ▾

写命中

写直达（Write Through）：同时写 Cache 和主存，二者始终一致；每次写都访存、速度慢，写缓冲（Write Buffer）可缓解。

写回（Write Back）⭐：只写 Cache，设脏位=1；该行被替换且脏位=1 时才写回主存。写速度快但可能不一致，现代 Cache 常用。

特性写直达写回
写速度慢快
数据一致性好差
主存写入次数多少
硬件复杂度低高（脏位）
典型应用早期系统现代 Cache

写未命中

  • 写分配：先调入 Cache 再写，常与写回配合
  • 非写分配：直接写主存、不调入，常与写直达配合
组合写直达 + 非写分配；写回 + 写分配（最常见）。

多级 Cache 一致性 ▾

多核 CPU 每个核有私有 L1/L2 Cache、共享 L3，需保证同一数据在各 Cache 中的一致性。解决方案：MESI 协议（Modified/Exclusive/Shared/Invalid）、MOESI、监听协议（Snooping）、目录协议（Directory-based）。

Cache 优化技术 ▾

  • 降低缺失率：增大块大小 / 增大 Cache 容量 / 提高相联度 / 编译器优化（循环交换、分块）
  • 降低缺失代价：多级 Cache / 关键字优先（Critical Word First）/ 提前重启（Early Restart）
  • 减少命中时间：小而简单的 L1 / 路预测 / 流水线化 Cache 访问

易错点 ▾

必记
  1. 直接映射不需要替换算法
  2. LRU 不一定是全局最优（只是近似最优）
  3. 写回需要脏位，写直达不需要
  4. 写分配是先调入再写，非写分配是直接写主存
  5. Belady 异常只在 FIFO 中出现，LRU 不会
  6. 写直达需要写缓冲来减少等待时间
  7. 多级 Cache 一致性用 MESI 等协议解决

记忆卡片 ▾

直接映射需要替换算法吗？
不需要，每块固定位置，直接覆盖。
LRU 和 FIFO 谁有 Belady 异常？
只有 FIFO 有；LRU 无。
写回和写直达的硬件差异？
写回需脏位；写直达无需脏位但需写缓冲。
OPT 算法能实现吗？
不能，仅作理论最优基准。
写回常配哪种写不命中策略？
写分配（先调入 Cache 再写）。
多级 Cache 一致性靠什么？
MESI / MOESI 等一致性协议。

交互动画 · 2 路组相联 LRU 追踪 ▾

组 0（2 路） 路 0空 路 1空 橙色 = 刚装入；灰底 = 当前 LRU（下次优先被替换）
点击「播放」或「下一步」，逐步查看 LRU 在 2 路组相联下的替换过程
访问序列：A B C A D B E

相关知识点

cache-mapping-methods cache-memory

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。