Appearance
408
计算机组成原理
CO-03-10 Cache替换算法与写策略
一、定位信息
| 项目 | 内容 |
|---|---|
| 所属圈层 | 核心层 |
| 前置知识回顾 | 需了解Cache映射方式（CO-03-09），特别是组相联和全相联映射下，一个主存块有多个可选的Cache位置，需要替换算法决定替换哪一行 |
| 知识网络定位 | 本单元是Cache映射方式（CO-03-09）的配套机制——映射方式决定"放哪里"，替换算法决定"替换谁"，写策略决定"怎么写回"。三者共同构成Cache的完整工作机制 |
| 考点热度等级 | H级 — 替换算法（特别是LRU）和写策略是高频考点，近5年出现≥4次，常以选择题或计算题形式出现 |
二、知识点讲解
2.1 为什么需要替换算法
- 直接映射：每个主存块只能放在唯一的Cache行，不需要替换算法（新数据直接替换旧数据）。
- 全相联/组相联映射：一个主存块有多个可选位置，当这些位置都被占用时，需要替换算法决定替换哪一行。
2.2 常见替换算法
（1）先进先出算法（FIFO）
规则：替换最早进入Cache的行。
实现：为每组维护一个FIFO队列，新进入的行排在队尾，替换时选择队首的行。
优点：实现简单 缺点：不考虑访问频率和最近使用情况，可能替换掉频繁使用的行
（2）近期最少使用算法（LRU, Least Recently Used）
规则：替换最长时间没有被访问的行。
实现：为每行维护一个计数器或栈，记录访问顺序。每次命中时更新计数器；替换时选择计数器值最大的行（最久未访问）。
2路组相联的LRU实现：只需1位"使用位"。访问组内第0行时置0，访问第1行时置1。替换时选择使用位为0（或1）的行。
4路组相联的LRU实现：可以用2位计数器记录访问顺序（00, 01, 10, 11），或使用栈结构。
优点：利用了时间局部性，命中率通常较高 缺点：硬件实现较复杂（路数多时计数器/栈的维护开销大）
（3）随机替换算法（Random）
规则：随机选择一行进行替换。
优点：实现最简单 缺点：不稳定，可能替换掉频繁使用的行，命中率不可预测
（4）最不经常使用算法（LFU, Least Frequently Used）
规则：替换访问次数最少的行。
优点：考虑了访问频率 缺点：需要维护访问计数器，实现复杂；可能因早期频繁访问但后期不再使用的行占位
2.3 写策略
Cache的写操作比读操作复杂，需要考虑如何保持Cache和主存中数据的一致性。
写命中时的策略
（1）写直达（Write Through / Write Through）
每次写操作同时写Cache和主存。
- 优点：Cache和主存始终一致，实现简单
- 缺点：每次写都要访问主存，速度慢；写操作频繁时总线压力大
- 优化：使用写缓冲（Write Buffer），将写操作暂存到缓冲区，CPU不用等待主存写入完成
（2）写回（Write Back / Write Allocate）
只写Cache，不立即写主存。当Cache行被替换时，如果该行被修改过（脏位=1），才写回主存。
- 优点：减少对主存的写操作，速度快
- 缺点：Cache和主存可能不一致，实现复杂（需要脏位）
- 脏位（Dirty Bit）：标记该行是否被修改过
写未命中时的策略
（1）写分配（Write Allocate / Fetch on Write）
先将主存块调入Cache，再在Cache中执行写操作。
- 通常与写回策略配合使用
- 理由：既然要修改这个块，就把它调入Cache，后续可能还会访问
（2）非写分配（No Write Allocate / Write Around）
直接写主存，不调入Cache。
- 通常与写直达策略配合使用
- 理由：写直达每次都写主存，没必要再调入Cache
2.4 常见的写策略组合
| 组合 | 说明 | 常见程度 |
|---|---|---|
| 写直达 + 非写分配 | 每次写都写主存，写未命中时不调入Cache | 常见 |
| 写回 + 写分配 | 只写Cache，替换时写回；写未命中时调入Cache | 最常见 |
三、记忆与理解辅助
3.1 口诀记忆
替换算法口诀："FIFO看先后，LRU看最近，Random靠运气"
写策略口诀："直达同时写，回写脏了补；写分配调入，非写分配跳过"
3.2 对比表：三种替换算法
| 算法 | 替换依据 | 实现复杂度 | 命中率 | 特点 |
|---|---|---|---|---|
| FIFO | 最早进入 | 低 | 中等 | 可能替换频繁使用的行 |
| LRU | 最久未用 | 高 | 高 | 利用时间局部性，实际效果好 |
| Random | 随机 | 最低 | 低且不稳定 | 实现简单但不可靠 |
3.3 对比表：写策略对比
| 策略 | 写命中时 | 写未命中时 | 一致性 | 速度 | 脏位 |
|---|---|---|---|---|---|
| 写直达 | 同时写Cache和主存 | 通常不调入 | 始终一致 | 慢 | 不需要 |
| 写回 | 只写Cache | 通常调入 | 可能不一致 | 快 | 需要 |
3.4 LRU算法执行过程示例
假设某2路组相联Cache，某组有行0和行1，初始为空。访问序列：A, B, A, C, B, D
| 访问 | 命中？ | 行0 | 行1 | 替换行 | 说明 |
|---|---|---|---|---|---|
| A | 未命中 | A | - | - | 空位直接放入行0 |
| B | 未命中 | A | B | - | 空位直接放入行1 |
| A | 命中 | A | B | - | A在行0，命中 |
| C | 未命中 | A | C | B | B最久未用，替换行1的B |
| B | 未命中 | B | C | A | A最久未用，替换行0的A |
| D | 未命中 | B | D | C | C最久未用，替换行1的C |
四、例题与精解
例题1（基础）
题目：某Cache采用2路组相联映射和LRU替换算法，共有4组，每组2行。初始Cache为空。给出以下主存块访问序列对应的组号：0, 1, 0, 2, 1, 0, 3, 1（每个数字为"主存块号 mod 4"的结果，即组号）。写出每次访问后的Cache状态。
命题意图：考查LRU替换算法的执行过程。
审题分析：4组，每组2行。访问序列的组号为：0, 1, 0, 2, 1, 0, 3, 1。每个访问的主存块可以唯一标识为主存块号。
解题思路：逐次模拟，记录每组的两行内容和LRU状态。
完整步骤：
设主存块号为：B0, B1, B2, B3, B4, B5, B6, B7（对应组号0, 1, 0, 2, 1, 0, 3, 1）
| 访问 | 组号 | 命中？ | 组0（行0,行1） | 组1 | 组2 | 组3 | 说明 |
|---|---|---|---|---|---|---|---|
| B0 | 0 | 未中 | B0,- | -,- | -,- | -,- | 组0空，放行0 |
| B1 | 1 | 未中 | B0,- | B1,- | -,- | -,- | 组1空，放行0 |
| B2 | 0 | 未中 | B0,B2 | B1,- | -,- | -,- | 组0行1空，放行1 |
| B3 | 2 | 未中 | B0,B2 | B1,- | B3,- | -,- | 组2空，放行0 |
| B4 | 1 | 未中 | B0,B2 | B1,B4 | B3,- | -,- | 组1行1空，放行1 |
| B0 | 0 | 命中 | B0,B2 | B1,B4 | B3,- | -,- | B0在组0行0，命中 |
| B5 | 3 | 未中 | B0,B2 | B1,B4 | B3,- | B5,- | 组3空，放行0 |
| B6 | 1 | 未中 | B0,B2 | B4,B6 | B3,- | B5,- | 组1中B1最久未用，替换 |
方法反思：LRU的关键是跟踪每组中各行的"最近使用时间"。命中时要更新该行的时间戳。2路LRU只需要1位标记即可。
例题2（中等）
题目：某Cache采用直接映射，块大小为16字节，共4行。主存地址为12位。初始Cache全部有效位为0。给出以下地址访问序列（十六进制）：020, 024, 028, 02C, 040, 044, 020, 040。假设采用写回策略。 （1）判断每次访问是否命中。 （2）如果地址020处的数据被修改过（脏），当访问040时会发生什么？
命题意图：考查直接映射的命中判断和写回策略的工作机制。
审题分析：直接映射，块大小16B（Offset 4位），4行（Index 2位），地址12位。Tag = 12 - 2 - 4 = 6位。
地址划分：[6位Tag | 2位Index | 4位Offset]
解题思路：将每个地址拆分为Tag和Index，逐次判断。
完整步骤：
地址拆分：
| 地址 | 二进制 | Tag(高6位) | Index(中2位) | Offset(低4位) | Cache行 |
|---|---|---|---|---|---|
| 020H | 0000 0010 0000 | 000000 | 10 | 0000 | 行2 |
| 024H | 0000 0010 0100 | 000000 | 10 | 0100 | 行2 |
| 028H | 0000 0010 1000 | 000000 | 10 | 1000 | 行2 |
| 02CH | 0000 0010 1100 | 000000 | 10 | 1100 | 行2 |
| 040H | 0000 0100 0000 | 000001 | 00 | 0000 | 行0 |
| 044H | 0000 0100 0100 | 000001 | 00 | 0100 | 行0 |
| 020H | 0000 0010 0000 | 000000 | 10 | 0000 | 行2 |
| 040H | 0000 0100 0000 | 000001 | 00 | 0000 | 行0 |
逐次分析：
| 访问 | 行 | 命中？ | Cache行0(行0) | Cache行2(行2) | 说明 |
|---|---|---|---|---|---|
| 020H | 2 | 未中 | - | Tag=00, 有效 | 首次访问，从主存调入块（地址020~02F） |
| 024H | 2 | 命中 | - | Tag=00, 有效 | 与020H在同一块内（Index相同，Tag相同） |
| 028H | 2 | 命中 | - | Tag=00, 有效 | 同上 |
| 02CH | 2 | 命中 | - | Tag=00, 有效 | 同上 |
| 040H | 0 | 未中 | Tag=01, 有效 | Tag=00, 有效 | 行0空闲，调入新块 |
| 044H | 0 | 命中 | Tag=01, 有效 | Tag=00, 有效 | 与040H在同一块内 |
| 020H | 2 | 命中 | Tag=01, 有效 | Tag=00, 有效 | 行2中仍是020块，命中 |
| 040H | 0 | 命中 | Tag=01, 有效 | Tag=00, 有效 | 行0中仍是040块，命中 |
（2）写回策略下的行为：
如果地址020处的数据被修改过，行2的脏位被置为1。当后续某个访问需要替换行2时（即某个映射到行2的不同Tag的地址被访问），硬件会先将行2的数据写回主存（因为脏位=1），然后再从主存调入新块。
在本题的序列中，没有发生行2的替换，所以不会触发写回。
方法反思：
- 同一Cache块内的连续地址（只Offset不同）第一次未命中，后续全部命中——这就是空间局部性的体现。
- 写回策略下，脏位的维护对Cache一致性至关重要。
- 直接映射的命中判断：先看Index定位行，再看Tag是否匹配且有效位=1。
五、考情分析
| 项目 | 内容 |
|---|---|
| 近5年考查频次 | ≥4次 |
| 常见题型 | 选择题（写策略对比）、计算题（LRU执行过程模拟、命中率计算） |
| 分值占比 | 选择题2分，计算题5–8分 |
| 命题趋势 | LRU替换过程的模拟和写策略的对比是经典题型。近年趋势是将替换算法、写策略与映射方式结合，出完整的Cache访问过程分析大题 |
六、易错点提醒
易错点1
- 错误表现：LRU替换时，忘记更新命中行的时间戳
- 错误原因：只关注替换逻辑，忽略了命中时也需要更新状态
- 正确做法：每次访问（无论命中还是未命中）都要更新该行的LRU计数器/时间戳。命中时更新是为了标记"刚被使用过"
易错点2
- 错误表现：混淆"写回"和"写直达"的含义
- 错误原因："写回"容易误解为"写回到主存"，实际恰恰相反
- 正确做法：写回（Write Back） = 只写Cache，等替换时再写回主存。写直达（Write Through） = 同时写Cache和主存。"回"字指的是"替换时才回写"
易错点3
- 错误表现：直接映射下误以为也需要替换算法
- 错误原因：没有理解直接映射的唯一确定性
- 正确做法：直接映射中每个主存块只能放在唯一位置，新数据直接覆盖旧数据，不需要替换算法"选择"替换谁
易错点4
- 错误表现：写回策略下忘记检查脏位，直接替换
- 错误原因：忽略了脏位的作用
- 正确做法：写回策略下，替换前必须检查脏位。若脏位=1，先将旧数据写回主存，再装入新数据。若脏位=0，直接替换即可
七、来源标注
- 依据2026考研统考大纲（408-计算机组成原理-第三章"存储器层次结构"）
- 依据大学本科经典教材共识：唐朔飞《计算机组成原理》、白中英《计算机组成原理》、Patterson & Hennessy《计算机组成与设计》