CO-3 存储系统（Cache 与存储层次）

这一部分为什么存在？

CPU 每纳秒级就能完成一次运算，而 DRAM 主存一次访问要几十纳秒——速度差约两个数量级。如果没有存储层次，CPU 绝大部分时间都在等内存（“存储墙”）。同时存在三个不可兼得的需求：

• 要快 → 用 SRAM，但贵、密度低；
• 要大 → 用 DRAM/磁盘，但慢；
• 要便宜 → 容量和速度都妥协。

存储系统的总回答是层次化 + 局部性：程序在短时间内的访问集中在小范围（时间局部性：刚用过的还会用；空间局部性：用了这个还会用邻居），因此用小而快的 SRAM（Cache）缓存“当前热区”，用大而慢的 DRAM 存全体，用磁盘做后备。Cache → 主存 → 外存构成速度递减、容量递增、单位成本递减的金字塔。

没有 Cache 会怎样：CPU 主频再高也被主存拖死，CPI 恶化一个数量级以上，后面 CO-5 流水线的所有优化都会失去意义。

flowchart TD
    A["CPU 与主存速度差<br/>+ 局部性原理"] --> B["引入 Cache"]
    B --> C["Cache 容量有限<br/>→ 主存块放到哪里？<br/>地址映射"]
    C --> D1["直接映射"]
    C --> D2["全相联"]
    C --> D3["组相联"]
    D2 & D3 --> E["多个块竞争同一位置<br/>→ 替换算法<br/>随机 / FIFO / LRU"]
    B --> F["写操作 → Cache 与主存不一致<br/>→ 写策略：写直达 / 写回"]
    A --> G["主存自身也要扩容提速<br/>字位扩展 / 多体交叉"]

核心概念：

来源：复习资料 P2 §1–2；王道 2027 计组 存储系统章。

1. 地址三段式（一切 Cache 计算的起点）

主存地址统一切分为：[ 标记 Tag | 组号/行号 Index | 块内地址 Offset ]。任何题先算三步（来源：复习资料 P2 §1）：

1. 定块内：块大小 $=2^b$ B → 块内地址 $b$ 位；
2. 定组号/行号：组数 $=2^c$ → $c$ 位（直接映射：组数=行数；$n$ 路组相联：组数 = 总块数 / $n$；全相联：无此字段）；
3. 定标记：Tag = 地址总位数 $- c - b$。

命中判定：按 Index 定位 → 比较有效位 = 1 且 Tag 相等。

2. 三种映射在解决什么权衡

Cache 容量远小于主存，必须回答“主存块可以放哪、怎么找”。三种方案是硬件成本与冲突概率之间的三个折中点：

为什么演化：直接映射简单但“异块同号”时颠簸；全相联消灭冲突但 $N$ 个比较器太贵；组相联把“全相联的自由”限制在组内，用 $n$ 个比较器换来接近全相联的命中率——组相联是直接映射与全相联的折中，$n=1$ 即直接映射，组数=1 即全相联。

高频陷阱：组相联的 Tag 字段不含组号（组号单独占字段），算 Tag 位数时要先减组号位（来源：复习资料 P2 §8 陷阱清单；2015 年 15 题、2021 年 16 题、2022 年 16 题均在此设坑）。

3. 替换算法

位置冲突时淘汰谁：随机（硬件最省）、FIFO（队列）、LRU（最久未使用，命中率高，$n$ 路组相联需 $\lceil\log_2 n\rceil$ 位/行的 LRU 计数位）。LRU 是真题默认考点（2012 年 17 题：2 路组相联 + LRU，地址序列 0,4,8,2,0,6,8,6,4,8 数命中次数）。

4. 写策略：读容易写难

读操作只查 Cache；写操作制造了两份数据（Cache 与主存）可能不一致的问题，两条路线：

为什么 Cache 可以用写直达，而虚存页面换出总是“写回式”？（2016 年 45 题第 4 问）因为 Cache 的下级是主存，一次写几十纳秒，穿得住；而页面的下级是磁盘，一次写毫秒级，若每改一次页面都写磁盘，系统会被 I/O 拖死，所以只能攒到换出时写。同一思想，不同层，写直达可行与否取决于上下级速度差。

5. Cache 容量计算（别漏控制位）

$\text{总容量} = \text{行数} \times (\text{数据位} + \text{Tag位} + \text{有效位} + [\text{脏位}] + [\text{LRU位}] + \dots)$

题目说“不计一致性维护和替换控制位”就只算 数据+Tag+有效位；说“采用写回”就必须加脏位。典型：2015 年 15 题（直接映射 + 写回，4K 字 Cache 至少多少位）、2021 年 16 题（32KB 直接映射写回，Cache 行位数 275 = 256 数据 + 18 Tag + 1 有效 + 1 脏）。

6. 数组访问命中率分析（大题固定套路）

套路三步：① 每块装 $N$ = 块大小/元素大小 个元素；② 行优先连续访问 → 每块第 1 个 miss、后 $N-1$ 个 hit，命中率 $= 1 - 1/N$；③ 列优先跨行访问 → 步长 = 行距，可能每次 miss（Cache 装不下工作集时颠簸）。

• 2010 年 44 题：a[256][256]、块 64B（16 个 int）、8 行直接映射——按行命中率 15/16，按列命中率≈0，按行的程序执行更短。
• 2024 年 43 题：a[24][64]、块 32B（8 个 int）、4 路组相联 8KB——按行、按列命中率均为 7/8 = 87.5%（组相联 + 工作集可容纳时，访问顺序不再致命）。

7. 主存侧：字位扩展与多体交叉

• 字位扩展（来源：复习资料 P2 §3）：位扩展 = 几片拼位宽（地址、片选并联，数据分位）；字扩展 = 几片拼容量（高位地址经译码器产生片选，低电平有效）。芯片数公式：$(\text{总容量}/\text{单片容量}) \times (\text{总位宽}/\text{芯片位宽})$（2009 年 15 题：2 片 ROM + 30 片 RAM）。
• 多体交叉存储：低位交叉编址，$m$ 个体轮流启动，带宽约提 $m$ 倍——主存自身对“慢”的补偿手段（2012 年 43 题第 4 问：四体低位交叉、体周期 50ns，最大带宽计算）。

已在上方按问题分段比较（三种映射表、写策略表）。此处集中两个易混对：

Cache vs TLB：为什么易混——都是 SRAM 小缓存、都靠局部性、都有组相联和标记。本质区别——Cache 缓存数据，TLB 缓存地址映射；Cache 用物理地址（也可虚存 addressed，408 默认物理），TLB 用虚页号。判别线索：题目给“主存块/行”是 Cache，给“虚页号/页框号”是 TLB（2020 年 15 题：两者都由 SRAM 组成、命中率都与局部性有关）。

Cache-主存层 vs 主存-外存层（虚存）：映射思路上 Cache 层用直接/组相联，虚存层页面放置是全相联（任意页框）——2024 年 16 题考点（“主存-外存层次通常采用直接映射”为错误项）；缺失处理上 Cache miss 硬件解决，缺页必须 OS 软件处理；写策略上 Cache 可写直达，虚存只能写回式。

形态一：地址划分与容量计算（每年必考，选择或大题小问）

• 2009-14：2 路组相联，129 号单元 → 组号（块号 129/32=4，4 mod 4 = 0… 按 8 组算）。
• 2015-15：直接映射 + 写回，Cache 总容量位数（数据 + Tag + 有效 + 脏位）。
• 2021-16：32KB 直接映射写回，Cache 行至少 275 位。
• 2022-16：8 路组相联，比较器 8 个、20 位（Tag = 32 − 组号 6 − 块内 6 = 20）。
• 2019-46：4 路组相联 64 行，问块内/组号/Tag 各是地址哪几位，call 指令只可能命中哪组。

形态二：命中率与访问序列模拟

• 2009-21：访存 1000 次缺失 50 次 → 命中率 95%。
• 2012-17：2 路组相联 + LRU，序列 0,4,8,2,0,6,8,6,4,8，数命中次数。
• 2016-15：a[k]=a[k]+32 循环，直接映射 1KB/16B，缺失率约 12.5%（每块 4 个 int，读 4 次写 4 次共 8 次访问仅首读 miss）。

形态三：综合大题（Cache + 数组 + 常联合虚存/流水线）

• 2010-44：分离 Cache + 数组按行/按列，命中率对比与执行时间。
• 2012-43：命中率 → 带宽 → 缺页 → DMA → 多体交叉（与 X-1、X-3 串联）。
• 2020-44：8 路组相联 + 直写 + LRU 全要素大题。
• 2024-43：请求调页 + 4 路组相联 + 二维数组，缺页次数与命中率联合计算（X-1 形态）。

做题触发词：看到“直接映射/组相联 + 地址位数”→ 立即三段切分；看到“写回/Write Back”→ 容量加脏位；看到“数组 a[i][j] + 行优先”→ 算每块元素数；看到“只可能在哪组命中”→ 块号 mod 组数。

来源：真题markdown/2009-2024统考真题.md 对应题号；复习资料 P2 §1–3、§7–8。

• 向前依赖：CO-1 数据表示（地址位数、编址单位、大端小端——2016 年 14 题小端存放紧邻本节考点）；CO-0 性能指标（CPI、MIPS 与命中率联合，2012-43）。
• 向后引出：
  • Cache 是“地址转换完成后”的那一环 → 接 X-1 完整访存链；
  • 写缓冲、访存时序影响流水线 MEM 段 → CO-5；
  • 主存经总线与 CPU 交换 → CO-6 总线带宽匹配（2012-43 主存带宽计算）；
  • 外存层（磁盘）作为虚存后备 → OS-6、OS-8；
  • 同一“局部性 + 缓存”思想延伸到 TLB、OS 页面缓冲、DNS/HTTP 缓存（X-7）。

1. 为什么需要 Cache？（CPU-主存速度差 + 局部性）
2. 为什么按“块”而不是按字节取数？（空间局部性，摊薄取数代价）
3. Cache 容量有限，主存块放哪里？（三种映射）
4. 三种映射各自怎么切分地址？比较器要几个？（Tag|Index|Offset；1 / 全部 / $n$）
5. 为什么组相联是折中？$n=1$ 和组数=1 各退化成什么？
6. 替换算法在哪种映射下才需要？为什么直接映射不需要？
7. LRU 要付出什么硬件代价？（每行 $\lceil\log_2 n\rceil$ 计数位，算容量别漏）
8. 写操作为什么麻烦？两条路线各牺牲什么？（写直达费带宽、写回要脏位）
9. 为什么 Cache 能写直达、虚存页面只能“写回式”？（下级速度差：主存纳秒级 vs 磁盘毫秒级）
10. Cache 总容量怎么算？哪些控制位按题意取舍？（有效位必算、写回加脏位、组相联加 LRU 位）
11. 数组按行访问命中率怎么推？按列为什么可能全 miss？组相联 + 大 Cache 时呢？
12. 主存自己太慢/太小怎么办？（字位扩展扩容量、多体交叉提带宽）
13. Cache 这一环如何嵌入“虚拟地址 → 物理地址 → 数据”的完整链条？（接 X-1）