上一篇我们让多条指令在流水线上重叠执行，把吞吐翻了几倍。但流水线有一个天敌：取指、访存要等内存。如果 CPU 每取一条指令、读一个变量都要干等内存几百个周期，流水线再深也救不回来。

这一篇往上抬一级视角，回答一个根本问题——为什么今天的计算机既能"内存很大"又能"访问很快"？ 答案是用层次结构（memory hierarchy）把"快而贵"和"慢而便宜"组合成一套用户看来又大又快的存储系统，而真正的魔法器件就是 Cache。

一句话定位：局部性是因，Cache 是果；命中是常态，缺失是代价。

1. 存储器层次：用金字塔换"又快又大"

CPU 寄存器最快（亚纳秒、在芯片内），但容量只有几百字节；DRAM 主存便宜、能上 GB，但慢几十到上百倍；磁盘更便宜、能上 TB，但慢百万倍。如果只用一个层级，要么快得装不下，要么大得慢死。

寄存器 / L1 ~1ns 最贵 最少(KB) CPU Cache(L2/L3) 数ns 贵 KB~MB 主存 DRAM ~100ns 中 GB SSD / 磁盘 ms 级 廉 TB~PB 速度↑ 造价↑ 容量↓ 速度↓ 造价↓ 容量↑

核心思想：把最近用过的、以及它"邻居"的数据，都顺手搬到更靠近 CPU 的层。这样绝大多数访问命中上层、少量才落到下层。代价只是"偶尔没命中要去下层取"——只要命中率够高，平均访问时间就逼近最快那层。

2. 局部性原理：Cache 为什么成立

Cache 能work，靠的是程序的两类局部性（locality）：

  • 时间局部性（temporal）：刚访问过的地址，很可能马上再被访问。例：循环变量 i、函数栈帧。
  • 空间局部性（spatial）：访问某个地址后，附近地址很可能也被访问。例：数组遍历、顺序取指令（下一条指令就在旁边）。
1
2
3
// 典型双局部性：i 反复用（时间），arr[i]、arr[i+1] 相邻用（空间）
for (int i = 0; i < N; i++)      // i：时间局部性
    sum += arr[i];               // arr：空间局部性（一次取一整块进 Cache）

反例：链表随机跳、哈希表稀疏访问——空间局部性差，Cache 命中率会明显下滑。这也是"数组比链表缓存友好"的底层原因。

3. Cache 基本术语

  • 块 / 行（block / line）：Cache 与主存之间搬运的最小单位，典型 32~64 字节。一次缺失会把一整块搬进来（顺手利用空间局部性）。
  • 命中（hit）：要的数据已在 Cache。
  • 缺失（miss）：不在 Cache，得去下一层取，取到后填回 Cache。
  • 命中率（hit rate） = 命中次数 / 总访问次数；缺失率 = 1 − 命中率。
  • 平均访问时间（AMAT） = 命中时间 + 缺失率 × 缺失代价。
CPU Cache 下一层存储 命中→快 缺失→慢 取整块填回

4. 地址怎么拆：tag / index / offset

Cache 怎么知道"主存地址 A 在不在我这儿、在哪"？把地址切成三段：

tag（标记） index offset bit 31 … 6 bit 5~4 bit 3~0 判断是不是同一块 哪一组 块内第几字节 ← 组相联时 组内再比 tag
  • offset：块内偏移，由块大小决定。块 16 字节 → 占 4 位。
  • index：组索引，"这个块该住在哪一组"。4 组 → 占 2 位。
  • tag：剩下的高位，用来确认"这一组里躺着的到底是不是我要的那个地址"。

5. 三种映射方式

把主存块放进 Cache，放哪有讲究，对应三种策略：

直接映射 direct-mapped mem block → 固定 set = (addr>>4) & (S-1)　每组仅 1 空位 ✓ 硬件最简、查找最快　　✗ 易冲突缺失 组相联 set-associative 每组 E 个空位（2/4/8-way），块可放组内任意空位 ✓ 缓解冲突　　✗ 组内要比较 E 个 tag 全相联 fully-associative 整 Cache 是一组，块可放任意位置（如 TLB 小表） ✓ 冲突最小　　✗ 比较所有 tag、硬件最贵

冲突缺失（conflict miss） 是直接映射的软肋：两块映射到同一组时，会互相把对方挤掉。例：块 16 字节、4 组时，地址 0 与 64 的 index 都是 (x>>4)&3 = 0，交替访问就反复缺失（所谓"抖动"）。组相联用多个空位直接消掉这类冲突。

6. 跑一个直接映射 Cache 仿真

下面这段 C 程序实现 4 组、块 16 字节的直接映射 Cache，并跑一条体现局部性的访问序列。注意 index = (addr>>4)&3、tag = addr>>6 和上面地址拆分完全对应。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <stdbool.h>

#define NUM_SETS    4      // 组数：index 占 2 位
#define BLOCK_BYTES 16     // 块大小 16 字节：offset 占 4 位

static bool valid[NUM_SETS];
static int  tag[NUM_SETS];

int main(void) {
    int seq[] = {0,4,8,12, 0,4,16,20,24,28, 0,4,8,12, 32,36,40,44, 0,4};
    int n = sizeof(seq) / sizeof(seq[0]);
    int hits = 0, misses = 0;

    for (int i = 0; i < n; i++) {
        int a   = seq[i];
        int idx = (a >> 4) & (NUM_SETS - 1); // 组索引
        int tg  = a >> 6;                    // 标记
        if (valid[idx] && tag[idx] == tg) {
            hits++;
            printf("addr=%2d  set=%d  tag=%2d  -> HIT\n", a, idx, tg);
        } else {
            misses++;
            valid[idx] = true;
            tag[idx] = tg;
            printf("addr=%2d  set=%d  tag=%2d  -> MISS\n", a, idx, tg);
        }
    }

    int total = hits + misses;
    printf("\nTotal accesses : %d\n", total);
    printf("Hits           : %d\n", hits);
    printf("Misses         : %d\n", misses);
    printf("Hit rate       : %.1f%%\n", hits * 100.0 / total);
    printf("Miss rate      : %.1f%%\n", misses * 100.0 / total);
    return 0;
}

输出（序列里 0,4,8,12 同属一块、16~28 同属一块……空间局部性让第二次起全命中）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
addr= 0  set=0  tag= 0  -> MISS
addr= 4  set=0  tag= 0  -> HIT
addr= 8  set=0  tag= 0  -> HIT
addr=12  set=0  tag= 0  -> HIT
addr= 0  set=0  tag= 0  -> HIT
addr= 4  set=0  tag= 0  -> HIT
addr=16  set=1  tag= 0  -> MISS
addr=20  set=1  tag= 0  -> HIT
addr=24  set=1  tag= 0  -> HIT
addr=28  set=1  tag= 0  -> HIT
addr= 0  set=0  tag= 0  -> HIT
addr= 4  set=0  tag= 0  -> HIT
addr= 8  set=0  tag= 0  -> HIT
addr=12  set=0  tag= 0  -> HIT
addr=32  set=2  tag= 0  -> MISS
addr=36  set=2  tag= 0  -> HIT
addr=40  set=2  tag= 0  -> HIT
addr=44  set=2  tag= 0  -> HIT
addr= 0  set=0  tag= 0  -> HIT
addr= 4  set=0  tag= 0  -> HIT

Total accesses : 20
Hits           : 17
Misses         : 3
Hit rate       : 85.0%
Miss rate      : 15.0%

20 次访问只 3 次冷缺失（每组第一次），其余全靠空间+时间局部性命中——这正是 Cache 日常工作的缩影。

7. 替换策略：组内满了怎么办

组相联 / 全相联里，组内位置用完又来了新块，必须挑一个踢出去：

  • LRU（最近最少使用）：踢"最久没被访问"的，最符合局部性，命中率通常最好，但要维护访问顺序。
  • 随机（Random）：硬件简单，大容量下和 LRU 差距不大。
  • FIFO / RR：按进入顺序踢，实现简单但可能踢掉正热的块（Belady 异常相关）。

硬件里 LRU 常用"伪 LRU（tree-PLRU）"近似，用几位比特模拟顺序，省面积。

8. 写策略：写命中时怎么处理

读缺失只需"取回来"，写缺失还涉及"什么时候写回下层"：

  • 写直达（write-through）：每次写都同时写 Cache 和下层。简单、下层数据总一致；但每次写都访问下层，带宽压力大。
  • 写回（write-back）：只写 Cache，并且给块打"脏位（dirty）"，只有被替换且脏时才写回下层。写带宽小得多，是 L1/L2 主流；代价是要维护脏位、一致性更复杂。
写直达 write-through CPU写 Cache 下层存储 每次都写下层 写回 write-back CPU写 Cache 标脏位 dirty 下层存储 仅替换且脏时写回

9. 三类缺失：知道自己为什么慢

  • 强制缺失（compulsory / cold）：第一次碰到这块，必然缺失，无法避免（除非预取）。
  • 容量缺失（capacity）：Cache 太小，装不下工作集，有用的块被挤出又取回。
  • 冲突缺失（conflict）：直接映射下多块抢同一组，即使总容量够也缺失；改组相联可消除。

诊断时把缺失拆成这三类，才能对症下药：容量不够就加 Cache，冲突多就加相联度，强制缺失靠预取（prefetch）。

10. 小结：AMAT 才是真正的指标

回到开头那句话——Cache 不是"命中就赢"，而是把平均访存时间 AMAT = 命中时间 + 缺失率 × 缺失代价 压到接近最快那层。局部性好 → 缺失率低 → AMAT 低 → 流水线不用干等 → 整机就快。它和上一篇的流水线、下一篇的虚拟内存是同一套"用一层骗过另一层"的思想：CPU 以为自己拥有"又大又快"的单一内存，其实是 Cache 与 MMU 在底下齐心搬砖。

维度 直接映射 组相联 全相联
组内位置数 1 E（如 8） 全部
查找速度 最快 中 最慢
冲突缺失 最多 少 最少
典型用途 L1 常客 L2/L3 TLB 小表

🐾 一句话收尾：Cache 不是魔法，是"局部性 + 层次 + 搬砖"三件套；命中率是它的命门，AMAT 是它的体温计。