前言
本节围绕 Cache 三大核心问题展开学习：

1. 主存块与 Cache 块如何建立映射关系（三种映射方式）
2. Cache 空间存满后，淘汰哪一块数据（四种置换算法）
3. CPU 修改 Cache 数据后，如何保证 Cache 与主存数据一致（写策略）

基础概念铺垫：

1. Cache 存放主存数据块的副本，CPU 优先访问高速 Cache，缺失才访问低速主存；
2. 数据传输单位为块，Cache 块大小 = 主存块大小；
3. Cache 行组成：数据区 + 标记 Tag + 有效位 Valid（置换算法额外加计数器，写回法加脏位）

￮有效位：0 = 该行数据无效，标记无意义；1 = 标记有效，当前存储有效主存块副本

一、Cache 与主存的三种映射方式
统一例题条件（全程举例）
主存总空间 256MB，按字节编址，地址 28 位；Cache 共 8 行（块），块大小 64B=2⁶B，块内地址 6 位。
主存总块数：2²⁸ / 2⁶ = 2²² 块，主存块号占 22 位。

1.全相联映射
规则
任意主存块，可以存入 Cache任意一行，无位置限制。
地址拆分
整个 22 位主存块号全部作为标记 Tag，地址结构：【22 位 Tag 标记 | 6 位块内地址】
CPU 访存流程

1. 取出地址高 22 位 Tag；
2. 遍历 Cache所有行，逐行对比标记；
3. 找到标记匹配 + 有效位 = 1 → Cache 命中，用低 6 位块内地址取数据；
4. 全部标记不匹配 / 有效位为 0 → 不命中，从主存调入目标块，随机选空闲 Cache 行存放。

优缺点
•优点：空间利用率高，只要 Cache 有空位就能存入，命中率最高；
•缺点：查找时需要对比全部 Cache 行，硬件并行比较电路复杂，访问速度最慢。

2.直接映射
规则
主存块只能固定存入 Cache 唯一一行；
计算公式：Cache 行号 = 主存块号 % Cache 总行数

例：Cache 共 8 行 (2³)，主存块 1、9：1%8=1，9%8=1，只能放入 Cache 第 1 行。
二进制简化原理
Cache 行数为 2ⁿ，取主存块号末尾 n 位直接作为 Cache 行号，无需除法电路。
例题 8=2³，取主存块号低 3 位为行号，标记只需剩余 19 位。
地址结构：【19 位 Tag 标记 | 3 位 Cache 行号 | 6 位块内地址】
CPU 访存流程

1. 取主存块号低 3 位，直接锁定唯一 Cache 行；
2. 仅对比这一行的 Tag 标记 + 判断有效位；
3. 匹配且有效位 = 1 → 命中；否则不命中，直接覆盖当前行原有数据。

优缺点
•优点：仅对比一行标记，查找速度最快，硬件最简单；
•缺点：空间利用率极低，不同主存块会争抢同一 Cache 行，频繁覆盖，命中率最低。

3. 组相联映射（折中方案，工程最常用）
规则

1. 将 Cache 所有行均等分组，每组包含 N 行，称为N 路组相联；
2. 主存块只能存入指定组内任意一行；

计算公式：组号 = 主存块号 % 总组数

例题：8 行 Cache 分为 4 组，每组 2 行（二路组相联），主存块 1、9 对 4 取余 = 1，只能放入第 1 组。
二进制简化原理
总组数 = 2ⁿ，主存块号低 n 位为组号；例题 4=2²，低 2 位是组号，标记剩余 20 位。
地址结构：【20 位 Tag 标记 | 2 位组号 | 6 位块内地址】
CPU 访存流程
1.取主存块号低 2 位锁定唯一分组；
2.仅遍历当前组内所有行，对比 Tag + 有效位；
3.组内匹配成功则命中；组内无空闲行时，执行置换算法淘汰本组某一块。
优缺点
综合全相联、直接映射的优势，平衡硬件成本与命中率，实际 CPU 普遍使用。

三种映射对比总结

二、Cache 四种置换算法
使用前提
•直接映射：固定位置覆盖，不需要置换算法；
•全相联：整个 Cache 满才置换；
•组相联：对应分组全部占满才置换。
统一测试场景：Cache 共 4 行，访问序列：1,2,3,4,1,2,5,1,2,3,4,5

1.随机置换算法（RAND）
规则
Cache 空间不足时，随机任选一块淘汰，无任何逻辑判断。
优缺点
实现最简单；完全不考虑程序局部性，命中率不稳定，实际极少使用。

2.先进先出算法（FIFO）
规则
优先淘汰最早调入 Cache的块，按调入时间排序。
硬件实现
用队列记录调入顺序，循环 0、1、2、3 行依次轮换淘汰。
缺陷

1. 不考虑块是否频繁访问，早期调入但高频使用的块会被强制淘汰；
2. 抖动现象：刚被淘汰的块立刻又被访问，重复频繁换入换出，大幅降低效率。

3. 近期最少使用算法（LRU，考试 / 工程重点）
核心思想：遵循时间局部性，近期很少访问的块，未来大概率不用，淘汰最久未访问块。
1）手动做题快速方法
从当前访问位置向前遍历访问序列，淘汰最晚出现的 Cache 内块。
2）硬件实现（计数器方案）
每行配置独立计数器，Cache 总行数为 2ᵏ，仅需 k 位计数器；
计数器规则：

1. 新块调入空闲行：该行计数器置 0，其余非空行计数器 + 1；
2. 命中某行：该行计数器清零，所有更小计数器的值 + 1；大计数器保持不变；
3. 需要置换：选择计数器数值最大（最久未访问）的行淘汰。

优缺点
命中率四种算法中最高；硬件实现复杂度中等，是现代 Cache 标准置换算法。

局限
若活跃主存块数量 > Cache 总行数，依然会产生抖动。

4. 最不经常使用算法（LFU）
规则
每行计数器记录总访问次数，淘汰访问次数最少的块；
若多块次数相同，默认淘汰行号更小 / 调入更早的块。
计数器规则：块每命中一次，计数器 + 1。

缺陷
只统计全局总访问次数，忽略时间局部性：
曾经高频访问、现在长期不用的块计数器数值很大，长期无法被淘汰，浪费 Cache 空间，实际效果差。

四种置换算法对比

三、Cache 写策略（解决 Cache 与主存数据一致性）
基础说明
读操作不会修改数据，不存在一致性问题；仅写操作需要策略区分，分两类场景：写命中、写不命中。
场景 1：写命中（要写入的块已在 Cache 中）
（1）写回法（回写法）

1. 操作：仅修改 Cache 副本，不立刻同步主存；
2. 新增硬件标记：脏位（Dirty）
   ￮脏位 = 0：该行数据和主存一致，淘汰时无需写回；
   ￮脏位 = 1：该行被修改过，淘汰时必须整块写回主存；
3. 搭配方案：通常和写分配法配合使用；
4. 优缺点：减少访存次数，写速度快；存在数据不一致风险。

（2）全写法（写直通法 Write-through）

1. 操作：写 Cache 的同时，同步写入主存，二者数据时刻一致；
2. 优化：增设写缓冲（FIFO 队列，SRAM 高速）
   CPU 把写入数据丢进写缓冲即可继续执行，后台硬件异步同步主存；
   弊端：大量连续写操作会填满写缓冲，CPU 阻塞等待；
3. 搭配方案：通常和非写分配法配合使用；
4. 优缺点：数据永远一致，无需脏位；每次写都访问主存，速度慢。

场景 2：写不命中（要写入的块不在 Cache 中）
（1）写分配法
先把目标主存块调入 Cache，再修改 Cache 副本；
适配：写回法。

（2）非写分配法
不加载主存块到 Cache，直接修改主存；
适配：全写法。

标准搭配组合

1. 高性能 CPU Cache ↔ 写回法 + 写分配法；
2. 简单设备 / 多级 Cache 高层 ↔ 全写法 + 非写分配法。

拓展：多级 Cache（L1/L2/L3 Cache）

1. 层级规则：越靠近 CPU，速度越快、容量越小、成本越高；L1 < L2 < L3；
2. 层级副本关系：L1 存放 L2 的部分副本，L2 存放主存部分副本；各级之间同样存在一致性；
3. 同步规则：各级 Cache 内部采用全写法 + 非写分配；Cache 与主存采用写回 + 写分配。

四、整体知识框架复盘
1.三大模块

1. 映射方式：全相联、直接、组相联 → 解决 “块放哪”
   配套硬件：标记 Tag + 有效位 Valid
2. 置换算法：RAND、FIFO、LRU、LFU → 解决 “满了删谁”
   仅全相联、组相联需要，LRU 最优
3. 写策略：写命中（写回 / 全写）、写不命中（写分配 / 非写分配）→ 解决 “数据同步”
   配套硬件：脏位、写缓冲

2. 核心做题结论

1. 地址拆分关键：2ⁿ块 / 组，对应 n 位行号 / 组号，剩余高位为标记；
2. 性能优先级：命中率 LRU>FIFO>RAND；查找速度：直接 > 组相联 > 全相联；
3. 工程标配：二路 / 四路组相联映射 + LRU 置换 + 写回法 + 写分配法。