计算机系统 - 存储系统

This post is not yet available in English. Showing the original version.

April 23, 2026 Notes 学习 / 计算机系统 zh-CN

Table of Contents

前面几章把 CPU 怎么"算"讲清楚了，这一章聚焦 CPU 身边那一层层"放东西的地方"——从寄存器旁边的 Cache，到主板上插的内存条，再到机箱里的硬盘。重点不是软件视角下的"内存地址"，而是这些存储到底是怎么造出来的，以及为什么 SRAM 快、DRAM 便宜、Flash 要先擦后写。

一、存储器的分类视角

1.1 按易失性（Volatility）

类别	断电数据	代表器件	典型用途
易失性（Volatile）	丢失	SRAM、DRAM	Cache、主存
非易失性（Non-volatile）	保留	ROM、Flash、磁盘	BIOS、SSD、机械硬盘

1.2 按存取方式（Access Method）

存取方式	特点	代表器件
随机存取 RAM	任意地址的访问时间相同	SRAM、DRAM、ROM
顺序存取	必须从头按序读，位置越远越慢	磁带
直接存取	先定位到块，再在块内顺序访问	磁盘
相联存取	按"内容"查询，而非按"地址"	Cache 的 tag、TLB

"RAM"这个名字有歧义：字面意思是 Random Access（任意地址等时），但现在口语里 RAM 往往单指主存里的 DRAM。ROM 其实也是随机存取的。

1.3 按在系统中的位置

flowchart TB
    subgraph CPU["CPU 芯片内部"]
        REG["寄存器<br/>SRAM · 几十 × 64 位"]
        L1["L1 Cache · SRAM"]
        L2["L2 Cache · SRAM"]
        L3["L3 Cache · SRAM"]
    end
    subgraph BOARD["主板"]
        MEM["主存 · DRAM 内存条"]
    end
    subgraph BOX["机箱 / 外设"]
        SSD["辅存 · SSD / HDD"]
        OFFLINE["离线 · 磁带 / 光盘"]
    end
    REG --> L1 --> L2 --> L3 --> MEM --> SSD --> OFFLINE

⬆ 越往上：速度快 / 单价高 / 容量小 ⬇ 越往下：反之

整个层次是靠局部性原理支撑的——不是每一层都要大，而是"经常用的小块"放上层，"偶尔用的大块"放下层。

1.4 关键性能指标

容量：常以 B / KB / MB / GB 表示；芯片级常写成 字数 × 位数（如 1K × 8 表示 1024 个字、每字 8 位）。
存取时间 $T_A$ ：一次读/写从发起到完成的时间。
存取周期 $T_C$ ：连续两次访问之间的最小间隔， $T_C \geq T_A$ （DRAM 因为要重写，周期明显大于访问时间）。
带宽：单位时间能传多少字节，如 DDR4-3200 的 25.6 GB/s。

二、SRAM：用触发器存一位

2.1 6 管单元结构

SRAM 的一位由 6 个 MOS 管构成一个双稳态触发器（两个反相器头尾相连），外加两个传输门接到位线：

flowchart TB
    WL(["字线 WL"])
    BL(["位线 BL"])
    BLN(["反位线 BL'"])
    T5["T5<br/>传输管"]
    T6["T6<br/>传输管"]
    INV1["反相器 ①<br/>（T1 + T2）"]
    INV2["反相器 ②<br/>（T3 + T4）"]

    WL --> T5
    WL --> T6
    BL <--> T5
    BLN <--> T6
    T5 <--> INV1
    T6 <--> INV2
    INV1 <-->|"交叉耦合"| INV2

两个反相器交叉耦合后有两个稳态：一个存 0、一个存 1，只要加电就一直保持，不需要刷新——这就是"静态（Static）"的由来。

2.2 读写过程

读：字线 WL 拉高 → 传输门导通 → 内部状态通过 BL/BL' 出现电位差 → 灵敏放大器（Sense Amplifier）判断出 0/1。读是非破坏性的。
写：把想写的值强行驱动到 BL 和 BL'（一高一低）→ 拉高字线 → 覆盖内部状态。

2.3 SRAM 的工程取舍

优点	代价
不需要刷新	一位要 6 管，集成度低
速度快（ns 级）	单价高
接口简单（直接给地址就能读）	功耗相对较高

所以 SRAM 只用于对延迟敏感、容量小的场合：寄存器文件、Cache、TLB、片上暂存。主存用不起。

三、DRAM：用电容存一位

3.1 1 管 1 电容结构

flowchart LR
    WL(["字线 WL"]) --> T["T<br/>MOS 管"]
    BL(["位线 BL"]) <--> T
    T <--> C["C<br/>存储电容"]
    C --> GND(["GND"])

每个存储单元只有 1 个 MOS 管 + 1 个电容：电容里充电为 1，放电为 0。这种极简结构让 DRAM 的集成度远高于 SRAM，价格也便宜得多——代价来自电容本身的物理特性。

3.2 三个"麻烦事"

① 电容会漏电 → 必须刷新

室温下电容里的电荷几毫秒就会漏光。DRAM 规定每个单元必须在一个刷新周期（典型 2 ms 或 64 ms）内被读出再写回一次。"动态（Dynamic）"的名字就来自这里。

常见刷新策略：

策略	做法	优缺点
集中刷新	在 2 ms 末尾集中刷整片	简单，但刷新期间 CPU 无法访问（"死区"）
分散刷新	每个存取周期后紧跟一次刷新	无死区，但每周期都加长一倍
异步刷新	2 ms 均匀分成 N 次，每隔 `2ms/N` 刷一行	折中方案，现代 DRAM 的实际做法

② 读出是破坏性的 → 必须重写

读一位时，电容上的电荷会被位线分走一部分——读完后电容电压已经变了。所以每次读操作都必须在灵敏放大器判断出结果后，立刻把原值重新写回。这就是为什么 DRAM 的 $T_C > T_A$ 。

③ 行列复用地址 → RAS/CAS 分两步

为了减少引脚数，DRAM 把地址分成行地址和列地址，分两拍送进来：

sequenceDiagram
    autonumber
    participant CPU as CPU / 内存控制器
    participant DRAM as DRAM 芯片
    Note over CPU,DRAM: 第一拍：送行地址
    CPU->>DRAM: 地址线 = 行地址
    CPU->>DRAM: RAS 拉低（锁存）
    DRAM->>DRAM: 激活一整行到行缓冲区<br/>（读出 + 重写）
    Note over CPU,DRAM: 第二拍：送列地址
    CPU->>DRAM: 地址线 = 列地址
    CPU->>DRAM: CAS 拉低（锁存）
    DRAM-->>CPU: 从行缓冲区输出对应列的数据

RAS（Row Address Strobe）有效时，锁存行地址 → 激活一整行到行缓冲区（同时完成读出 + 重写）
CAS（Column Address Strobe）有效时，锁存列地址 → 从行缓冲区挑出一个位输出

这个机制是现代 DDR 内存"突发读"（burst read）的基础：一旦某行被激活，同一行内的连续列访问极快——这就是为什么按行顺序遍历数组比按列遍历快得多。

3.3 SDRAM 与 DDR 简介

SDRAM（Synchronous DRAM）：与 CPU 时钟同步，不再依赖异步握手。
DDR（Double Data Rate）：时钟的上升沿和下降沿都传数据，带宽直接翻倍；DDR2/3/4/5 是频率 + 预取位宽的逐代翻倍。
HBM（High Bandwidth Memory）：多层 DRAM 堆叠 + 硅通孔（TSV），用在 GPU / AI 芯片上。

四、SRAM vs DRAM 对比

维度	SRAM	DRAM
单元结构	6 个 MOS 管	1 管 1 电容
集成度	低	高（6× 左右）
是否刷新	不需要	必须周期性刷新
读出是否破坏	否	是（需重写）
存取周期 $T_C$	= $T_A$	> $T_A$
速度	快（ns 级）	慢（几十 ns）
成本	高	低
典型用途	Cache、寄存器	主存、显存

五、ROM 家族

ROM（Read-Only Memory）原本指"出厂后内容固定"的非易失存储，但后来衍生了很多"可擦写"的变种，名字保留了下来。

类型	编程方式	擦除方式	典型寿命	场景
MROM	厂商在生产时用掩膜决定	不能	—	大批量固定代码（早期游戏卡带）
PROM	用户一次性烧熔丝	不能	—	小批量定制
EPROM	电写入	紫外线照射擦除（石英窗）	百次级	老式 BIOS
EEPROM	电写入	电擦除，字节级	万次级	参数存储、智能卡
Flash	电写入	电擦除，块级	万~十万次	SSD、U 盘、手机存储

Flash 的关键特性

读以字节/页为单位，但 擦除以块（Block）为单位——通常一块有几十到几百 KB。
写之前必须先擦：写只能把 1 变 0，要想把 0 变回 1 必须整块擦除。
磨损有限：每个块的擦写次数有限，所以 SSD 控制器需要磨损均衡（Wear Leveling），把写操作均匀分散到所有块上。
NOR Flash：按字节随机读，速度快，容量小，用来放代码（可直接 XIP，Execute In Place）。
NAND Flash：按页读写，容量大，价格便宜，用来放数据（SSD、U 盘）。

六、存储芯片的内部结构

6.1 存储矩阵（Storage Array）

芯片内部的存储单元排成二维矩阵，不是一条长线。给定一个地址后，要拆成"行地址 + 列地址"去选中对应的单元：

行译码器地址高位
列译码器 · C0 C1 C2 … C(n-1)
R0
●
●
●
●
●
●
R1
●
★
●
●
●
●
R2
●
●
●
●
●
●
…
●
●
●
●
●
●
R(m-1)
●
●
●
●
●
●
读写电路（含灵敏放大器） → D0..D7

图中打★的单元 = "R1 行 × C1 列"被同时选中，是这次访问的目标。

地址引脚数量 = $\log_2(行数 \times 列数)$
选片信号 CS（Chip Select）：多片芯片共享总线时用来决定"这次访问归谁"
读写控制 OE（Output Enable）、WE（Write Enable）

6.2 单译码 vs 双译码

单译码：一个译码器直接选一个单元。地址 n 位就要有 $2^n$ 根输出线——当容量大时线太多，版图面积爆炸。
双译码（行列译码）：地址劈成两半分别译码，选中一行 + 一列交叉的单元。例如 10 位地址（1024 单元），双译码只需要 2 × 32 根输出线，而不是 1024 根。

这也是前面 DRAM 用 RAS/CAS 行列复用的物理动机——矩阵结构本来就是按行列组织的。

6.3 芯片容量的记法

1K × 8、4K × 4、256K × 1 这种写法里：

前一个数（1K）是字数，对应地址线位数 $\log_2(字数)$
后一个数（8）是字长，对应数据线位数

规格	地址线	数据线	总容量
1K × 8	10	8	1 KB
4K × 1	12	1	4 Kb = 512 B
256K × 4	18	4	128 KB

七、存储器扩展：从一片到一组

实际系统需要的"内存大小 × 总线宽度"通常远超单片芯片的规格，所以要多片组合。

7.1 位扩展（Bit Expansion）——扩宽度

情景：CPU 数据总线 8 位，但手上只有 1K × 4 的芯片。
做法：两片并联，共享所有地址线和控制线，各出 4 位数据拼成 8 位。

flowchart TB
    ADDR["地址总线 A0..A9（共享）"]
    CTRL["CS / R·W（共享）"]
    U0["片 U0<br/>1K × 4<br/>（低 4 位 D3..D0）"]
    U1["片 U1<br/>1K × 4<br/>（高 4 位 D7..D4）"]
    BUS["数据总线 D7..D0"]

    ADDR --> U0
    ADDR --> U1
    CTRL --> U0
    CTRL --> U1
    U0 -->|D3..D0| BUS
    U1 -->|D7..D4| BUS

结果：1K × 8，地址数不变，数据线加倍。

7.2 字扩展（Word Expansion）——扩容量

情景：CPU 要接 4K × 8 内存，只有 1K × 8 芯片。
做法：四片并联数据线，但地址高位经译码器分别控制各片的片选 CS。

flowchart TB
    HIGH["地址高 2 位<br/>A11 A10"]
    DEC["2-4 译码器"]
    LOW["地址低 10 位 A0..A9（共享）"]
    DATA["数据总线 D7..D0（共享）"]
    U0["片 0 · 1K×8<br/>0x000 ~ 0x3FF"]
    U1["片 1 · 1K×8<br/>0x400 ~ 0x7FF"]
    U2["片 2 · 1K×8<br/>0x800 ~ 0xBFF"]
    U3["片 3 · 1K×8<br/>0xC00 ~ 0xFFF"]

    HIGH --> DEC
    DEC -->|CS0| U0
    DEC -->|CS1| U1
    DEC -->|CS2| U2
    DEC -->|CS3| U3
    LOW --> U0 & U1 & U2 & U3
    U0 <--> DATA
    U1 <--> DATA
    U2 <--> DATA
    U3 <--> DATA

任意时刻四根片选只有一根有效，高 2 位地址决定"这次该哪片说话"。

地址分配（以 12 位地址为例）：

片	高 2 位地址	覆盖地址范围
片 0	`00`	`0x000` ~ `0x3FF`
片 1	`01`	`0x400` ~ `0x7FF`
片 2	`10`	`0x800` ~ `0xBFF`
片 3	`11`	`0xC00` ~ `0xFFF`

7.3 字位同时扩展

既不够宽也不够大时，先按位扩成一组够宽，再把多组按字扩展。

考点模板：给"CPU 总线 x 位 / 要求 y KB 内存 / 现有 z 规格芯片"，问"需要几片？怎么接？"——先算片数 = 目标容量 / 单片容量，然后判断是位扩、字扩还是组合扩。

八、存储器与 CPU 的连接

8.1 三组总线

地址总线（Address Bus）：CPU → 存储，单向。位数决定最大可寻址空间（32 位地址 → 4 GB）。
数据总线（Data Bus）：双向，决定一次能搬多少字节。
控制总线（Control Bus）：包含 MREQ（访存请求）、R/W（读写方向）、READY（存储器就绪）等。

8.2 片选译码方式

多片芯片挂在同一总线上时，要用地址的高位生成片选信号。常见三种：

方式	做法	优缺点
全译码	用上所有高位地址，每片地址唯一	地址空间利用率 100%，但译码电路复杂
部分译码	只用部分高位地址，剩下悬空	同一物理单元对应多个地址（"地址混叠"），节省逻辑
线选法	直接用高位地址线中的某一根当 `CS`	最简单，但浪费地址空间，且片数 ≤ 可用线数

课程题里默认用全译码，工程上小系统常用线选。

8.3 一次读/写事务走过的总线

前面讲的是"存储器怎么连"，这里讲"一次访存在系统里实际是怎么流动的"。以 CSAPP 的经典示意为准——movl A, %eax（把内存地址 A 的 4 字节读进 %eax）走过的路径：

CPU 芯片
寄存器文件
含 %eax
ALU
▲ ▼ 片内总线
Bus interface
总线接口
◀ ▶System Bus
I/O bridge
北桥 / IMC
◀ ▶Memory Bus
Main Memory
主存（DRAM）

I/O bridge 早期是主板上的"北桥芯片"，把 CPU 的系统总线协议翻译成内存总线协议；现代 CPU 已经把它做进了芯片里（集成内存控制器 IMC），但分层模型仍然沿用。

读事务：`movl A, %eax`

CPU
I/O bridge
Main Memory
①
把地址 A 放上系统总线
＋「读」信号 →
转发中…
②
地址 A 转到内存总线 →
接收地址…
③
DRAM 取出地址 A 处的
4 字节数据 x
④
← 中转
← x 放回内存总线
⑤
← 接收
← x 放回系统总线
⑥
x 写入 %eax ✓

CPU 这一侧只看见"我把地址丢上总线 → 过一会儿数据回来"。
中间的 I/O bridge 做协议转换，把系统总线的请求翻成 DRAM 控制器能懂的 RAS/CAS 时序（这就回扣到第三节 DRAM 的行列复用）。
主存这一侧按 DRAM 内部机制完成"激活行 → 读列 → 重写"后，把数据放回内存总线。

写事务：`movl %eax, A`

CPU
I/O bridge
Main Memory
①
把地址 A 放上系统总线
＋「写」信号 →
转发中…
②
地址 A 转到内存总线 →
接收地址…
③
%eax 的值 y
放上系统总线 →
转发中…
④
y 放到内存总线 →
接收数据…
⑤
把 y 写入地址 A ✓

写事务的"地址"和"数据"是分两拍送出的：先占据总线送地址，再送数据。这也是为什么一次访存即使命中 DRAM 行缓冲区，也至少要若干个总线周期。

关键观察

层级	经手的事情	代价量级
CPU 内部（ALU ↔ 寄存器）	纯片内信号	< 1 ns
系统总线（Bus interface ↔ I/O bridge）	过片界、跨时钟域	几 ns
内存总线（I/O bridge ↔ DRAM）	跨芯片、RAS/CAS 时序	几十 ns

所以即使命中主存、没掉到 Cache 以下，一次访存的绝大部分时间都消耗在"跨越边界"上——这也是为什么 L1/L2/L3 Cache 要尽量把数据留在 CPU 芯片内。

九、磁盘存储器（HDD）

虽然现在 SSD 普及了，但磁盘的概念是很多术语的原型（扇区、块、寻道时间……）。

9.1 物理结构

盘片（Platter）
多层叠起来；不同盘面上半径相同的磁道在空间上构成一个 柱面（Cylinder）。

同柱面切换磁头不用移动臂，寻道代价为零——所以数据排布以柱面优先。

磁头（Head）：每个盘面一个，读写时悬浮在盘片上方几纳米。
柱面（Cylinder）：同一半径上所有盘面的磁道集合——同柱面切换磁头不用移动臂，所以数据排布时同一柱面优先。

9.2 访问时间三分量

T_{\text{访问}} = T_{\text{寻道}} + T_{\text{旋转}} + T_{\text{传输}}

分量	含义	典型值（7200 RPM 机械盘）
寻道时间 $T_s$	磁头臂移动到目标磁道	几 ms
旋转延迟 $T_r$	等待目标扇区转到磁头下	平均 ≈ 半圈 = 4.17 ms
传输时间 $T_t$	扇区数据读出	每扇区几十 μs

寻道是瓶颈——这就是为什么数据库/文件系统都努力让连续读落在同柱面。

9.3 CHS 与 LBA

CHS（Cylinder / Head / Sector）：三维物理地址，早期 BIOS 用。
LBA（Logical Block Addressing）：线性一维块号，从 0 开始。现代操作系统只看 LBA，CHS 的转换交给磁盘控制器。

十、固态硬盘（SSD）

10.1 组成

SSD = NAND Flash 芯片阵列 + 控制器（SSD Controller）+ DRAM 缓存。没有机械部件，随机访问延迟从 ms 级降到 μs 级。

10.2 读写单位错配

操作	单位	典型大小
读	页 Page	4 ~ 16 KB
写	页 Page	4 ~ 16 KB
擦	块 Block	128 ~ 512 页

写放大（Write Amplification）：用户只改了一个字节，但底层可能要：先把整块读到缓存 → 擦整块 → 带着改动写回。所以一次"小写"在物理层可能变成几百倍的数据移动。

10.3 关键机制

磨损均衡（Wear Leveling）：把写操作均匀分散到所有块上，避免某些块提前"写死"。
垃圾回收（GC）：后台把零散有效页合并到新块里，腾出整块可擦除空间。
TRIM：OS 告诉 SSD "这些 LBA 我已经删了"，SSD 才敢把对应的物理页当作垃圾回收。

十一、回到存储层次

把这一章讲的器件填进层次结构里：

层级	器件	访问时间（量级）	容量（量级）
寄存器	SRAM（CPU 内）	~0.3 ns（1 cycle）	几十 × 64 位
L1 Cache	SRAM	~1 ns	几十 KB
L2 / L3 Cache	SRAM	几 ns ~ 几十 ns	几百 KB ~ 几十 MB
主存	DRAM（DDR）	~60 ns	几 GB ~ 几十 GB
SSD	NAND Flash	~50 μs	几百 GB ~ 几 TB
HDD	磁盘	~5 ms	几 TB

一个有用的直觉：相邻两层的速度差常常是 10×~100×。局部性原理能起作用，正是因为只要把最近访问的一小部分"提一层"，就能平均下来拿到上一层的速度。

到这里，从 CPU 到内存条到硬盘的硬件存储链条就连起来了。接下来我们把视角对准层次结构中最关键的一环——Cache。

十二、局部性原理（Locality）

Cache 能起作用的全部根基在于程序访问数据存在规律性。这个规律性被称为局部性原理，分两种。

生活类比：你在写作业时，最常翻的那几页教材会摊开放在桌上（而不是每次都走到书架上找）。桌面就是你的"Cache"——容量小，但伸手就到。你之所以敢只放几页在桌上，是因为你知道短时间内你只会反复查同一小部分内容。这就是局部性。

12.1 时间局部性（Temporal Locality）

如果一个数据刚被访问过，那它很快会再被访问。

🎯 类比：你刚查了一个单词的意思，过几分钟做下一道题时又遇到了同一个词——不用再翻词典，因为你还记得。

典型场景：循环变量、计数器、频繁调用的函数。

// sum 和 arr[i] 在循环中被反复访问 → 时间局部性
int sum = 0;
for (int i = 0; i < N; i++)
    sum += arr[i];

12.2 空间局部性（Spatial Locality）

如果一个数据被访问了，它附近地址的数据也很可能被访问。

🎯 类比：你翻到课本第 42 页查一个公式，接下来大概率还要看第 43、44 页的例题——所以干脆把第 42~45 页都摊开在桌上，而不是只看完一行就合上书。

典型场景：数组顺序遍历、结构体成员依次读取、指令的顺序执行。

// arr[i] → arr[i+1] → arr[i+2]... 地址连续 → 空间局部性
for (int i = 0; i < N; i++)
    process(arr[i]);

12.3 局部性与 Cache 的关系

局部性类型	Cache 利用方式
时间局部性	把最近访问的数据留在 Cache 里，下次命中
空间局部性	每次不只搬一个字节，而是搬一整个Cache 行（Block），邻近数据也跟着上来

反面教材：按列遍历二维数组。C 语言中 a[i][j] 按行优先存储，按列遍历（外层 j、内层 i）每次跳跃一整行的距离，空间局部性极差，Cache 命中率骤降。

十三、Cache 的基本概念

13.1 Cache 是什么

Cache（高速缓冲存储器）是 CPU 和主存之间的一层 SRAM 缓冲，由硬件自动管理，对程序员透明。

整体类比——书桌、书架与图书馆：

寄存器 = 你手里正在写的那张草稿纸（容量极小，速度极快）

L1 Cache = 书桌上摊开的几页笔记（伸手就到）

L2 / L3 Cache = 书桌旁的小书架（站起来转身就能够到）

主存（DRAM） = 房间里的大书柜（要走几步过去翻找）

硬盘 = 校图书馆（要出门走一趟，慢得多，但书很全）

Cache 做的事就是：提前把你大概率要用的书页从书柜搬到桌面上，这样大部分时候你都不用起身。

flowchart LR
    CPU["CPU"] <-->|"~1 ns"| L1["L1 Cache<br/>SRAM"]
    L1 <-->|"几 ns"| L2["L2 Cache"]
    L2 <-->|"~十几 ns"| L3["L3 Cache"]
    L3 <-->|"~60 ns"| MEM["主存 DRAM"]

13.2 核心术语

术语	含义
Cache 行 / 块（Line / Block）	Cache 的最小存储单位，通常 64 字节（现代 x86）
命中（Hit）	CPU 要的数据恰好在 Cache 中
未命中 / 缺失（Miss）	数据不在 Cache，需要去下一层取
命中率（Hit Rate）	命中次数 / 总访问次数
命中时间（Hit Time）	Cache 命中时的访问延迟
缺失代价（Miss Penalty）	缺失后去主存取数据的额外延迟

13.3 平均访问时间

T_{\text{avg}} = T_{\text{hit}} + (1 - h) \times T_{\text{miss}}

其中 $h$ 为命中率。例如： $T_{\text{hit}} = 1\text{ ns}$ ， $h = 95\%$ ， $T_{\text{miss}} = 60\text{ ns}$ ：

T_{\text{avg}} = 1 + 0.05 \times 60 = 4\text{ ns}

95% 的命中率就能把 60 ns 的主存延迟压到 4 ns——这就是 Cache 的威力。

13.4 Cache 的三种缺失（3C）

类型	英文	原因	能否避免
冷启动缺失	Compulsory (Cold)	数据第一次被访问，Cache 里当然没有	不能（预取可缓解）
容量缺失	Capacity	工作集超过 Cache 容量，被换出后又要用	换更大的 Cache
冲突缺失	Conflict	多个地址映射到同一 Cache 位置，互相驱逐	提高相联度

🎯 用书桌类比 3C 缺失：

冷启动：这学期第一次上某门课，桌上当然还没有那门课的教材——必须去书柜拿一趟。

容量：期末周同时复习 8 门课，桌面摆不下所有教材，只能不断换进换出。

冲突：桌面有固定区域放不同科目，但"数学"和"物理"被分到同一个格子里，两本书互相挤占。

十四、Cache 地址映射

CPU 发出一个内存地址后，Cache 怎么判断数据在不在自己里面？需要一套映射规则。

类比预告：接下来的三种映射方式，可以用「储物柜」来理解。想象你进了一个有 100 个储物柜的更衣室，你拿到一件行李（一个主存块），问题是：这件行李可以放进哪个柜子？

14.1 地址的拆分

假设主存地址有 $m$ 位，Cache 共有 $S$ 个组（Set），每组有 $E$ 个行（Way），每行存 $B$ 字节数据：

\underbrace{\text{标记 (Tag)}}_{\text{t 位}} \;\; \underbrace{\text{组索引 (Set Index)}}_{\text{s 位}} \;\; \underbrace{\text{块内偏移 (Block Offset)}}_{\text{b 位}}

$b = \log_2 B$ （定位数据在块内的第几个字节）
$s = \log_2 S$ （定位数据应该去哪个组）
$t = m - s - b$ （区分映射到同一组的不同主存块）

查找过程：用 s 位选组 → 在该组的所有行中逐一比较 Tag → 匹配且有效位=1 → 命中；否则缺失。

14.2 直接映射（Direct-Mapped）

每组只有 1 行（ $E = 1$ ），每个主存块只能放在唯一确定的一行。

🎯 类比：对号入座的电影院。你的票号决定了你只能坐第 N 排（ $N = \text{票号} \mod \text{排数}$ ）。简单高效——服务员不用搜索，直接看票号就知道你坐哪。但如果两张票恰好对应同一排同一座，后来的人就会把先来的人挤走。

\text{Cache 行号} = \text{主存块号} \mod S

Cache 行

Tag

Data（Block）

行 0

0x3A

64 字节数据…

行 1

—

空

行 2

0x1F

64 字节数据…

…

优点	缺点
硬件简单、查找快（只比较 1 个 Tag）	冲突缺失严重：两个常用地址若映到同一行，互相驱逐（抖动/ping-pong）

抖动示例：两个数组 a[] 和 b[] 的首地址恰好相差 Cache 容量的整数倍，交替访问时会反复驱逐对方，命中率趋近于 0。

14.3 全相联映射（Fully Associative）

没有组的概念（ $S = 1$ ， $E =$ 全部行数），主存块可以放在 Cache 的任意一行。

🎯 类比：自由入座的自习室。你可以坐任何空位。找人的时候要逐个位置扫一遍才知道某人在不在——人少时无所谓，人多了就很慢。

\text{地址} = \underbrace{\text{Tag}}_{\text{t 位}} \;\; \underbrace{\text{Block Offset}}_{\text{b 位}}

没有 Set Index 位——所有行都是一个"大组"。

优点	缺点
冲突缺失最少（只剩容量缺失和冷启动缺失）	每次查找要并行比较所有行的 Tag，硬件代价极高（需要比较器 × 行数）

全相联只用在容量很小、查找频率极高的场景：如 TLB（页表缓存，通常只有 32~64 项）。

14.4 组相联映射（Set Associative）— 主流方案

折中方案： $S$ 个组，每组 $E$ 路（Way）。主存块根据 Set Index 定位到某一组，然后可以放在该组的任意一路。

🎯 类比：分区自由入座的食堂。食堂分成若干个用餐区（组），你的学院决定了你在哪个区（Set Index），但在你的区内可以随便挑座位（Way）。找人时只需要在对应区域扫一圈，不用搜遍全食堂。——这就是组相联在"冲突少"和"查找快"之间的平衡。

\text{地址} = \underbrace{\text{Tag}}_{\text{t 位}} \;\; \underbrace{\text{Set Index}}_{\text{s 位}} \;\; \underbrace{\text{Block Offset}}_{\text{b 位}}

常见配置：

名称	每组路数 $E$	每次比较的 Tag 数
2 路组相联	2	2
4 路组相联	4	4
8 路组相联	8	8

直接映射 = 1 路组相联，全相联 = 只有 1 组的 N 路组相联。组相联是通用的描述框架。

flowchart TB
    ADDR["CPU 地址"] --> SPLIT["拆分: Tag | Set Index | Offset"]
    SPLIT --> SET["用 Set Index 选中组 i"]
    SET --> CMP["并行比较组 i 中 E 路的 Tag"]
    CMP -->|"某路匹配 且 V=1"| HIT["命中 ✓ → 取 Offset 处的数据"]
    CMP -->|"全部不匹配"| MISS["缺失 ✗ → 从主存取块，替换某一路"]

现代 CPU 的实际配置（典型）：

层级	容量	相联度	行大小
L1 I-Cache	32 KB	8 路	64 B
L1 D-Cache	32 KB	8 路	64 B
L2 Cache	256 KB	4~8 路	64 B
L3 Cache	8~32 MB	16 路	64 B

14.5 实战：手算 Cache 命中与缺失

理论讲完了，最有效的理解方式是拿一组具体地址走一遍。

题设

一个直接映射 Cache，参数如下：

参数	值	推导
Cache 总容量	32 字节	—
块大小 $B$	8 字节	$b = \log_2 8 = 3$ 位
组数 $S$	$32 / 8 = 4$ 组	$s = \log_2 4 = 2$ 位
相联度 $E$	1（直接映射）	—
地址位数 $m$	8 位	$t = 8 - 2 - 3 = 3$ 位 Tag

8 位地址的拆法：

\underbrace{a_7 \; a_6 \; a_5}_{\text{Tag (3 位)}} \;\; \underbrace{a_4 \; a_3}_{\text{Set (2 位)}} \;\; \underbrace{a_2 \; a_1 \; a_0}_{\text{Offset (3 位)}}

初始状态

Cache 全空（所有 Valid = 0）：

组	Tag	数据（8 字节）
0	—	—
1	—	—
2	—	—
3	—	—

依次访问地址序列：`0x00`, `0x0B`, `0x08`, `0x1A`, `0x00`

① 访问 0x00 = 0000 0000

Tag	Set	Offset	组号	判定
`000`	`00`	`000`	0	组 0 的 V=0 → 缺失（冷启动）

从主存加载块 [0x00–0x07] 到组 0：

组	V	Tag	数据
0	1	000	Mem[0x00–0x07]
1	0	—	—
2	0	—	—
3	0	—	—

② 访问 0x0B = 0000 1011

Tag	Set	Offset	组号	判定
`000`	`01`	`011`	1	组 1 的 V=0 → 缺失（冷启动）

加载块 [0x08–0x0F] 到组 1：

组	V	Tag	数据
0	1	000	Mem[0x00–0x07]
1	1	000	Mem[0x08–0x0F]
2	0	—	—
3	0	—	—

③ 访问 0x08 = 0000 1000

Tag	Set	Offset	组号	判定
`000`	`01`	`000`	1	组 1 的 V=1 且 Tag=`000` 匹配 → 命中 ✓

0x08 和 0x0B 在同一块里（0x08–0x0F），第 ② 步加载的块把 0x08 也顺带带进了 Cache——这就是空间局部性的收益。

④ 访问 0x1A = 0001 1010

Tag	Set	Offset	组号	判定
`000`	`11`	`010`	3	组 3 的 V=0 → 缺失（冷启动）

加载块 [0x18–0x1F] 到组 3：

组	V	Tag	数据
0	1	000	Mem[0x00–0x07]
1	1	000	Mem[0x08–0x0F]
2	0	—	—
3	1	000	Mem[0x18–0x1F]

⑤ 访问 0x00 = 0000 0000

Tag	Set	Offset	组号	判定
`000`	`00`	`000`	0	组 0 的 V=1 且 Tag=`000` 匹配 → 命中 ✓

0x00 在第 ① 步被加载后一直留在 Cache 里——这就是时间局部性的收益。

结果汇总

访问	地址	组	Tag 匹配？	结果	原因
①	`0x00`	0	—	Miss	冷启动
②	`0x0B`	1	—	Miss	冷启动
③	`0x08`	1	✓	Hit	空间局部性（同块）
④	`0x1A`	3	—	Miss	冷启动
⑤	`0x00`	0	✓	Hit	时间局部性（再次访问）

命中率 = 2/5 = 40%（冷启动后命中率会逐步提升）。

冲突缺失的演示

如果接着访问 0x20（= 0010 0000）：Tag=001，组号=0。

组 0 当前存的 Tag=000（0x00 的块），但 0x20 的 Tag 是 001 → 不匹配 → 缺失。0x00 的块被 0x20 的块替换掉。

此时如果再访问 0x00，又会缺失（Tag 变回 000，再替换一次）——如此反复就是抖动（ping-pong），这正是直接映射的冲突缺失。如果改用 2 路组相联，组 0 能同时容纳两个块，就不会互相驱逐了。

14.6 参数速算模板

考试常见套路：给出 Cache 容量和块大小，求地址各字段位数。

\begin{aligned} b &= \log_2 B \quad &\text{（Offset 位数）} \\ S &= \frac{\text{Cache 总容量}}{B \times E} \quad &\text{（组数）} \\ s &= \log_2 S \quad &\text{（Set Index 位数）} \\ t &= m - s - b \quad &\text{（Tag 位数）} \end{aligned}

快速例题：32 KB 的 4 路组相联 Cache，块大小 64 B，地址 32 位。

步骤	计算	结果
Offset	$b = \log_2 64 = 6$	6 位
组数	$S = 32\text{KB} / (64 \times 4) = 128$	128 组
Set Index	$s = \log_2 128 = 7$	7 位
Tag	$t = 32 - 7 - 6 = 19$	19 位

十五、替换策略

当 Cache 缺失且目标组已满时，必须选一路替换。选谁换出去？

🎯 类比：你桌上已经堆满了 4 本书（4 路），现在又要用一本新书——必须先把桌上某本书放回书架。放哪本？这就是替换策略要回答的问题。

先总览一下四种策略，然后逐个展开：

策略	全称	一句话	硬件开销
FIFO	First In First Out	谁先来的换谁	低
LRU	Least Recently Used	谁最久没用换谁	中~高
LFU	Least Frequently Used	谁用得最少换谁	高
随机（RND）	Random	随便挑一个换	极低

下面用同一组访问序列走四种算法，方便对比。设定：2 路组相联，某一组（组 i）的两路初始为空，依次访问块 A、B、C、A、D。

15.1 FIFO — 先进先出

核心思想：谁最早被装进来的，谁就最先被换出去。不管中间有没有被访问过。

就像排队：排在最前面的（最早来的）先走，不管他中间做了什么。

每路记录一个装入时间戳（或用一个指针轮转）。

FIFO 走一遍

步骤	访问	路 0	路 1	结果	说明
1	A	A ←	空	Miss	空位，装入路 0
2	B	A	B ←	Miss	空位，装入路 1
3	C	A	B	Miss	满了！A 最早进来 → 换 A
		C ←	B
4	A	C	B	Miss	A 刚被换走，又要用 → 缺失！B 最早 → 换 B
		C	A ←
5	D	C	A	Miss	C 最早 → 换 C
		D ←	A

命中次数：0/5。

FIFO 的问题：第 4 步中，A 虽然是第 1 步才用过的"常客"，但 FIFO 不管使用频率，只看装入顺序——所以 A 被换走后立刻又被需要。这种"该留的却被换走"的情况在 LRU 中不会发生。

硬件实现：只需一个指针（或计数器），指向"下一个该被替换的路"。每次装入新块时指针往下移一格。非常便宜。

15.2 LRU — 最近最少使用

核心思想：谁最久没被访问过，谁就最可能以后也不会被访问——换它。

这里的"最近"是指最后一次被使用的时间。不管它是什么时候装进来的，只看上一次用它是什么时候。

每次命中或装入都算"使用"，要更新该路的访问时间。

LRU 走一遍

步骤	访问	路 0	路 1	结果	说明
1	A	A（最近用）	空	Miss	装入路 0
2	B	A（较旧）	B（最近用）	Miss	装入路 1
3	C	A	B	Miss	A 最久没用 → 换 A
		C（最近用）	B（较旧）
4	A	C	B	Miss	B 最久没用 → 换 B
		C（较旧）	A（最近用）
5	D	C	A	Miss	C 最久没用 → 换 C
		D（最近用）	A（较旧）

命中次数：0/5（这个序列本身冲突太多，2 路装不下 4 个块）。

换一个更能体现 LRU 优势的序列：A、B、A、C（2 路）。

步骤	访问	路 0	路 1	结果	说明
1	A	A	空	Miss
2	B	A	B	Miss
3	A	A ✓	B	Hit	A 被访问 → A 变成最新，B 变成 LRU
4	C	A	B	Miss	B 是 LRU → 换 B
		A	C

命中 1 次。如果用 FIFO，第 4 步会换掉 A（因为 A 先进来），结果更差。LRU 保住了"还在用"的 A。

2 路 LRU 的硬件实现

2 路时只需要 1 位（称为 LRU 位）：

访问路 0 时，LRU 位设为 1（意思是"路 1 是 LRU"）
访问路 1 时，LRU 位设为 0（意思是"路 0 是 LRU"）
需要替换时，看 LRU 位：0 → 换路 0；1 → 换路 1

多路时（4 路、8 路），完整 LRU 需要记录所有路的访问顺序—— $E$ 路需要 $\log_2(E!)$ 位，硬件代价快速上升。实际中常用伪 LRU（Pseudo-LRU）：用一棵二叉树的比特位近似追踪，精度略低但硬件便宜得多。

15.3 LFU — 最不经常使用

核心思想：谁被访问的总次数最少，谁就最不重要——换它。

每路维护一个访问计数器，每次命中加 1。

LFU 走一遍

步骤	访问	路 0（计数）	路 1（计数）	结果	说明
1	A	A（1）	空	Miss
2	B	A（1）	B（1）	Miss
3	A	A（2） ✓	B（1）	Hit	A 计数变 2
4	C	A（2）	B（1）	Miss	B 计数=1 最小 → 换 B
		A（2）	C（1）
5	C	A（2）	C（2） ✓	Hit	C 计数变 2
6	D	A（2）	C（2）	Miss	计数相同！按其他规则（如 FIFO）决定 → 换 A
		D（1）	C（2）

命中 2 次。LFU 保住了使用频率高的块。

LFU 的问题

历史惯性：一个早期被疯狂访问的块，计数器累积很高。即使后来完全不用了，它仍然"赖着不走"，因为计数一直压着别人。
硬件上需要为每路维护计数器，且计数器位数有限（溢出后怎么办？衰减？折半？都需要额外逻辑）。

实际 CPU 的 Cache 很少用纯 LFU，主要用在操作系统的页面置换等软件层面（可以灵活实现衰减）。

15.4 随机替换（RND / Random）

核心思想：不分析任何历史信息，随机挑一路换掉。

步骤	访问	路 0	路 1	结果	说明
1	A	A	空	Miss
2	B	A	B	Miss
3	C	A	B	Miss	随机选一路（假设选了路 0）→ 换 A
		C	B
4	A	C	B	Miss	随机选（假设选了路 1）→ 换 B
		C	A

结果完全取决于运气。但统计意义上，随机替换的平均表现并不比 FIFO 差多少。

为什么"随便选"也还行？因为高相联度（8 路、16 路）时，随机选到"重要块"的概率本身就低（7/8 的概率选到不那么重要的）。L3 Cache 经常使用随机替换，因为 16 路的 LRU 硬件太贵，而随机策略几乎不需要任何额外存储。

15.5 四种策略对比总结

	FIFO	LRU	LFU	RND
判据	装入时间	最后访问时间	累计访问次数	无
每路额外存储	顺序指针	访问时间标记	计数器	无
硬件复杂度	低	中（2路）~高（多路）	高	极低
命中率	中	最高（通常）	高（但有历史惯性）	中
实际 Cache 应用	少见	L1 / L2（2~8 路）	几乎不用	L3（高相联度）

考试常考：给一个访问序列和 Cache 配置，用 LRU / FIFO 分别走一遍，数命中次数。关键是搞清楚 LRU 看的是上次使用时间，FIFO 看的是装入时间——两者在"命中后是否更新"这一点上有本质区别：

LRU：命中后该路变成"最新"

FIFO：命中后不更新装入时间，位置不变

十六、写策略

CPU 写数据时，Cache 和主存的内容可能不一致。写策略决定何时更新主存。

🎯 类比：你在草稿纸上改了一道题的答案（Cache 被修改了）。问题是：要不要立刻把改动抄回作业本（主存）？

写直达 = 改完草稿纸就立刻抄回作业本，两份始终同步，但每次都要多抄一遍。

写回 = 先只改草稿纸，等到这张草稿纸要被换走（替换）时，再一口气把所有修改抄回作业本。

16.1 写命中时

策略	做法	优缺点
写直达（Write-Through）	同时写 Cache 和主存	简单、一致性好，但每次写都要访问主存（慢）
写回（Write-Back）	只写 Cache，标记脏位（Dirty Bit），被替换时才写回主存	减少主存写次数，但需要额外的脏位 + 替换时回写

flowchart LR
    subgraph WT["写直达 Write-Through"]
        direction TB
        W1["CPU 写数据"] --> C1["写入 Cache"]
        W1 --> M1["同时写入主存"]
    end
    subgraph WB["写回 Write-Back"]
        direction TB
        W2["CPU 写数据"] --> C2["只写 Cache<br/>设 Dirty=1"]
        C2 -.->|"被替换时"| M2["才写回主存"]
    end

现代 CPU 的 L1 Cache 通常用写回（减少带宽压力），配合**写缓冲区（Write Buffer）**异步刷回下一层。

16.2 写未命中时

策略	做法	常搭配
写分配（Write-Allocate）	先把目标块从主存调入 Cache，再在 Cache 中写	写回（因为后续大概率还会访问该块）
非写分配（No-Write-Allocate）	直接写主存，不调入 Cache	写直达

常见搭配：

写回 + 写分配：现代 CPU 的主流组合
写直达 + 非写分配：简单系统、写少的场景

十七、多级 Cache 体系

17.1 为什么要多级？

单层 Cache 面临矛盾：追求低延迟要容量小（靠近 CPU），追求高命中率要容量大——分层解决这个矛盾。

🎯 类比：你不会把整个图书馆搬到桌上，但你也不甘心只在桌上放一本书。所以你建了一套"就近取材"体系：桌面放最常用的 → 桌边小书架放次常用的 → 房间书柜放再次常用的 → 图书馆放全部藏书。每一层拦截一部分需求，最终真正跑到图书馆的请求就很少了。

层级	典型延迟	典型容量	设计目标
L1	~1 ns（4 cycles）	32~64 KB	极致低延迟
L2	~4 ns（10+ cycles）	256 KB~1 MB	接住 L1 的缺失
L3	~12 ns（40+ cycles）	8~64 MB	多核共享，减少访问主存

17.2 包含性（Inclusion）

策略	含义	典型应用
包含式（Inclusive）	L1 中的内容在 L2 中一定有副本	Intel 早期
排他式（Exclusive）	L1 和 L2 中的内容互不重叠	AMD 某些架构
非包含非排他（NINE）	不做保证，灵活处理	现代 Intel（L2-L3 之间）

17.3 L1 分离：I-Cache 与 D-Cache

L1 Cache 通常分成两个独立的部分：

	I-Cache（指令缓存）	D-Cache（数据缓存）
存什么	机器指令	程序数据
为什么分开	取指和访数据可以同时进行，消除流水线的结构冒险

这就是哈佛架构在 Cache 层的体现：虽然主存仍然是统一的（冯·诺伊曼），但 L1 级别分离指令和数据通道，兼得两种架构的优势。

十八、存储层次全景总结

把全部内容串在一起，形成从寄存器到磁带的完整层次画面：

flowchart TB
    subgraph CPU["CPU 芯片内"]
        REG["寄存器<br/>SRAM · ~0.3 ns"]
        L1["L1 I-Cache + D-Cache<br/>SRAM · ~1 ns · 32-64 KB"]
        L2["L2 Cache<br/>SRAM · ~4 ns · 256 KB-1 MB"]
        L3["L3 Cache（多核共享）<br/>SRAM · ~12 ns · 8-64 MB"]
    end
    subgraph BOARD["主板"]
        MEM["主存 DDR DRAM<br/>~60 ns · 8-64 GB"]
    end
    subgraph STORAGE["外存"]
        SSD["SSD（NAND Flash）<br/>~50 μs · 256 GB-4 TB"]
        HDD["HDD（磁盘）<br/>~5 ms · 1-20 TB"]
    end
    REG --> L1 --> L2 --> L3 --> MEM --> SSD --> HDD

核心设计思想

层次结构能起作用，归根到底靠的是两个不等式：

速度不等式：相邻两层的速度差约 10×~100×
局部性不等式：程序在任意时间窗口内真正活跃的数据（工作集）远小于总数据量

只要工作集能装进上一层，就能以上一层的速度运行——用容量换延迟，用局部性弥合容量。

对程序员的启示

虽然 Cache 对程序员透明，但写出Cache 友好的代码可以显著提升性能：

做法	利用的原理	效果
数组按行遍历而非按列	空间局部性	减少 Cache 缺失
循环内频繁使用的变量放在局部变量	时间局部性	编译器更容易放入寄存器
避免大步长跳跃访问（如链表 vs 数组）	空间局部性	数组连续、链表跳跃
分块矩阵乘法（Blocking / Tiling）	时间 + 空间局部性	经典 CSAPP 优化
结构体成员按访问频率紧凑排列	空间局部性	减少不必要的 Cache 行加载

一个有趣的数字：遍历 1 亿个 int 的数组，Cache 友好的顺序遍历比随机访问快 5~10 倍——这个差距来自 L1/L2 命中率的巨大差异。

Loading comments...