02. 存储金字塔与 Cache 组相联映射机制

💡 交互图解

本章理论对应的动态微观仿真位于：👉 CS 10 图全屏走查 · FIG 02 Cache 组相联映射与 LRU

1. 存储金字塔与局部性原理

计算机存储系统的设计面临速度、容量与成本的不可能三角：

存储层级	典型容量	访问延迟 (约等)	时钟周期 (约等)
通用寄存器 (Regs)	32~64 个 (数百字节)	0.25 ns	1 周期
L1 高速缓存	32~64 KB / 核	1~1.5 ns	4 周期
L2 高速缓存	512 KB~2 MB / 核	3~5 ns	12~14 周期
L3 高速缓存 (共享)	16~96 MB	10~20 ns	40~60 周期
主存 (DRAM)	16~256 GB	60~100 ns	150~250 周期
固态硬盘 (NVMe SSD)	1~4 TB	10~50 µs	30,000+ 周期

局部性原理（Principle of Locality）：

• 时间局部性：被访问过的内存单元在不久的将来很可能再次被访问（如循环变量、高频函数）。
• 空间局部性：被访问过的内存单元其相邻单元在不久的将来很可能被访问（如连续数组遍历、顺序指令）。

---

2. 物理地址的切分三部曲

为了在硬件上高速检索 Cache，处理器将 32 位或 64 位物理地址拆分为三个连续比特段：

$$\text{Physical Address}=[\underset{t\text{ 位}}{\underbrace{\text{Tag (标记)}}}\mid \underset{s\text{ 位}}{\underbrace{\text{Set Index (组索引)}}}\mid \underset{b\text{ 位}}{\underbrace{\text{Block Offset (块内偏移)}}}]$$

1. Block Offset（$b$ 位）：取决于 Cache 行大小（Cache Line，通常为 64 字节，故 $b={\log }_{2}64=6$ 位）。
2. Set Index（$s$ 位）：决定 Cache 一共有多少个组（$S=2^s$）。硬件使用这 $s$ 位直接作为译码器输入，0 延迟定位到特定组。
3. Tag（$t$ 位）：剩余高位，用于在该组内部并行比对是否命中。

---

3. 三种映射方式对比

在 $k$ 路组相联 Cache 中，定位到 Set Index 后，硬件启动 $k$ 个硬件比较器并行 比对各 Way 的 Tag，并检查 Valid 有效位：

• 若任意一行匹配且有效：Cache HIT，多路选择器根据 Block Offset 取出目标数据，通常仅需 4 周期。
• 若所有行均不匹配：Cache MISS，触发主存总线事务，从内存加载包含该地址的整块 64 字节 数据。

---

4. 替换策略与写策略

替换策略（Eviction Policy）

当目标组的 $k$ 个槽位全部被占满时，发生冲突必须剔除一个牺牲槽位：

• LRU（Least Recently Used，最近最久未使用）：利用硬件计数器记录最近访问顺序，淘汰最久未读写的行。
• FIFO（先进先出） / RANDOM（伪随机）。

写策略（Write Policy）

• Write-Through（全写法 / 直写）：写 Cache 的同时无条件写穿到主存。实现简单但极耗带宽。
• Write-Back（写回法）：只写 Cache 行，将行标记为 Dirty（脏行）。只有当该脏行被淘汰替换出 Cache 时，才一次性刷回主存。现代 CPU 普遍采用此方案。

---

5. 生产级避坑：伪共享（False Sharing）

现代多核 CPU 的缓存一致性协议（MESI 协议）以 Cache Line（64 字节）为最小单位 进行失效广播。

// 危险结构体：两个不相关的变量紧挨在一起
struct Counter {
    volatile long count_thread_a; // 线程 A 负责累加 (8 字节)
    volatile long count_thread_b; // 线程 B 负责累加 (8 字节)
};

虽然线程 A 只读写 count_thread_a，线程 B 只读写 count_thread_b，但在物理内存上它们共享了同一条 64B Cache Line！ 当核 1 修改 a 时，会通过总线向核 2 发送 Cache Invalidate 信号，核 2 的整行缓存瞬间失效；紧接着核 2 修改 b，又让核 1 的缓存失效——这被称为 Cache 颠簸（Ping-Pong Effect），导致多核性能甚至暴跌至单核的十分之一以下！

工程破解之道： 使用内存对齐填充（Cache Line Padding）：

// Java 8 @Contended 注解，或手动填充 56 字节无意义数据撑满 64 字节
public class SafeCounter {
    volatile long a;
    long p1, p2, p3, p4, p5, p6, p7; // 填充行 (Padding)
    volatile long b;
}

著名的无锁高性能环形队列 Disruptor 与 Netty 高性能组件就是靠 Cache Padding 实现百万级单机吞吐。