03 存储系统
存储系统是计组的心脏章节——Cache 的三映射、LRU、写策略是全 408 考频最高的知识点之一。整章围绕一个矛盾展开：又快又大的存储器不存在（SRAM 快但贵、DRAM 便宜但慢），于是工程师用金字塔把它们摞起来用。
一、存储金字塔与局部性
寄存器 最快（<1ns） 最贵 ┐
L1 Cache ~1ns │ 容量小、速度快
L2/L3 Cache ~4-40ns │ CPU 内/旁边
主存 DRAM ~100ns ┘
SSD/磁盘 ~100μs / ~10ms
磁带/云归档 慢且便宜
撑起金字塔的是局部性原理（硬件速览埋过伏笔）：
- 时间局部性：刚访问过的东西，很快会再访问（循环、热点变量）
- 空间局部性：访问某地址后，附近的地址大概率被访问（数组遍历、顺序取指）
💡 Cache 的全部逻辑就是一句：用局部性"赌"你下次要的数据我已经提前搬到楼上了。赌对（命中）就是天价速度，赌错（缺失）就要下楼下一次。
分类速记
| 分类角度 | 类别 |
|---|---|
| 按介质 | 半导体（主存/Cache）、磁表面（磁盘）、光介质 |
| 按可改写 | RAM（随机读写）/ ROM（只读为主）；易失 vs 非易失（断电丢不丢） |
| 按访问方式 | 随机存取（内存）、顺序存取（磁带）、直接存取（磁盘：先定位磁道再顺序） |
⚠️ 磁盘是"直接存取"不是"随机存取"；CD-ROM 是"只读"半导体闪存属于 ROM 家族（Flash=电可擦写 ROM）。
二、主存：SRAM vs DRAM
| 维度 | SRAM（静态） | DRAM（动态） |
|---|---|---|
| 存储原理 | 触发器（6 个晶体管锁 1 位） | 电容存电荷（1 管 1 电容） |
| 刷新 | 不需要 | 需要定期刷新（电荷会漏） |
| 速度 | 快（1ns 级） | 慢（几十 ns） |
| 成本/集成度 | 贵/低 | 便宜/高 |
| 用途 | Cache | 主存（内存条）、显存 |
DRAM 刷新方式三种（考点）：
- 集中刷新：一段时间集中刷，期间死时间（访存"死区"）
- 分散刷新：每次读写后顺带刷一行，无死区但系统变慢
- 异步刷新：折中——隔一小段刷一行，2ms 内每行都刷到，死时间最短（现代 DDR 采用）
💡 SDRAM → DDR 演化：SDRAM（同步 DRAM，与时钟同步）→ DDR（Double Data Rate，时钟上下沿各传一次）→ DDR2/3/4/5（预取位数翻倍、频率提升）。买内存条的"DDR4-3200"意思就是第 4 代、3200 MT/s（每秒百万次传输）。
ROM 家族
MROM（厂家掩膜）→ PROM（一次编程）→ EPROM（紫外线擦）→ EEPROM（电擦，字节级）→ Flash（块级电擦：NOR 用于 BIOS/嵌入式，NAND 用于 SSD/U 盘）→ SSD = NAND Flash 阵列 + 控制器（详见 09-磁盘与固态硬盘）。
⚠️ BIOS 芯片是 Flash（历史上是 EPROM）——所以"BIOS 是 ROM"这句话在现代语境下要说成"BIOS 固件存在 Flash 芯片里"。
三、主存容量扩展与编址
1. 位扩展（加大"宽度"）
1 片 8K×1 位的芯片不够宽？8 片并联拼成 8K×8 位——地址线共用、数据线各出一位。
2. 字扩展（加大"深度"）
1 片 8K×8 位不够深？4 片轮流上拼成 32K×8 位——用高位地址（2 位）经译码器选片，低位地址片内寻址。
3. 字位同时扩展
总片数 = (总容量/单片容量) 完整套路：位扩展定"每组几片"，字扩展定"共几组"。
💡 例：用 16K×4 位芯片组成 64K×8 位存储器 → 位方向 8/4=2 片/组，字方向 64K/16K=4 组 → 共 8 片；需片选译码的地址线数 = log₂4 = 2 根。
4. 交叉编址（多体并行）
低位交叉编址：连续地址轮流分布在不同存储体——正好吃掉空间局部性，流水式访问。
- 设总线传送周期 τ、存储周期 T（T > τ），m 体低位交叉流水读取 m 个字：
💡 例：4 体交叉，T=8τ → 连续读 4 个字耗时 8τ + 3τ = 11τ（顺序编址则要 4T = 32τ）。
⚠️ 高位交叉是"每体连续编址"（扩展容量用），低位交叉才能提速——别混。
四、Cache 映射：三选一的坐标问题
主存块往 Cache 里放，核心问题是"放哪、怎么找到"。设 Cache 共 2ᶜ 块，每块 2ᵇ 字节，主存地址共 n 位。
1. 直接映射：一块只有唯一座位
主存第 j 块 → Cache 第 (j mod 2ᶜ) 号行。
地址划分（从高到低）：标记 tag | Cache 行号 c 位 | 块内偏移 b 位
- 优点：硬件最简单，查找一次就定位
- 缺点：冲突率高——第 0 块和第 2ᶜ 块抢同一个座位
2. 全相联：随便坐
任何块可放 Cache 任意行。地址划分：标记 tag（n−b 位）| 块内偏移 b 位
- 优点：最灵活，冲突最低
- 缺点：要和所有行的标记并行比较（相联存储器），硬件贵——只适合小容量（TLB 用它）
3. 组相联：分组内随便坐（折中赢家）
Cache 分 2^q 组，每组 2^r 块（r 路）。主存第 j 块 → 第 (j mod 2^q) 组，组内随便放。
地址划分：标记 tag | 组号 q 位 | 块内偏移 b 位
- r=1 退化为直接映射；r=组数（单组）退化为全相联
- 现代 CPU 的 L1 一般 8 路、L2/L3 更高路数
手算例题（408 真题风格）
主存 4GB（32 位地址）、按字节编址，Cache 数据容量 64KB、块大小 16B、4 路组相联：
- 块内偏移：16B = 2⁴ → b=4
- Cache 行数：64KB/16B = 4096 行；4 路 → 4096/4 = 1024 组 → q=10
- 标记：32 − 10 − 4 = 18 位
- 访问地址 0x12345678：组号 = (0x12345678 >> 4) & 0x3FF，标记 = 高 18 位——命中比较只在这 1 组的 4 行里进行
⚠️ 地址划分从低位往高位切：先偏移、再组号、剩下全给标记。直接映射则中间是行号。"组号/行号取中间"是铁律——偏移必须在最低位。
五、替换算法与写策略
1. 替换算法（直接映射不需要——座位唯一）
| 算法 | 做法 | 特点 |
|---|---|---|
| RAND | 随机换 | 实现最简单，命中率不稳定 |
| FIFO | 先进先出 | 可能淘汰"最老但最热"的块 |
| LRU | 最久未被访问的先换 | 408 必考手算；硬件用计数器实现 |
| LFU | 访问次数最少 | 统计成本高，可能误伤新块 |
LRU 手算例题：Cache 3 块，访问序列 1, 2, 3, 1, 4, 1, 2, 5：
| 访问 | 1 | 2 | 3 | 1 | 4 | 1 | 2 | 5 |
|---|---|---|---|---|---|---|---|---|
| Cache 状态 | [1] | [2,1] | [3,2,1] | [1,3,2] | 淘汰2→[4,1,3] | [1,4,3] | 淘汰3→[2,1,4] | 淘汰4→[5,2,1] |
逐步逻辑：每次访问把该块提到"最新"；满了之后，最久没碰的（从最新往里数排最后的）被换出。命中 3 次（1、1、2），缺失 5 次，命中率 3/8。
2. 写命中策略
| 策略 | 写命中时 | 优点 | 缺点 | 需要 |
|---|---|---|---|---|
| 全写法（写穿透 write-through） | 同时写 Cache 和 主存 | 主存永远一致 | 每次写都访存，慢 | 写缓冲 |
| 回写法（write-back） | 只写 Cache，标记脏位；换出时才写回主存 | 写速度快 | 主存暂时"过时" | 脏位 |
⚠️ 考点三连：① 回写法需要脏位（dirty bit）判断换出时是否写回；② 写缺失处理分"写分配"（配回写法：把块调上来再写）与"非写分配"（配全写法：直接写主存不调块）；③ 多核 Cache 一致性问题（MESI 协议思想：一个核写了，别的核的副本要失效）——这是回写法的深层代价。
3. Cache 性能算术
- 命中率 h = 命中次数/总访问次数
- 平均访存时间 = h × tc + (1−h) × tm（tc 是 Cache 访问时间，tm 是主存访问时间）
- 💡 例：tc=10ns，tm=100ns，h=95% → 0.95×10 + 0.05×100 = 9.5 + 5 = 14.5ns——比 100ns 快了近 7 倍，全靠局部性把 h 撑高
六、虚拟存储 vs Cache：同一套思想
内存管理 讲过：OS 用页表把虚拟地址翻译成物理地址，把"大虚拟空间"映射到"小物理内存"。对照一下：
| 维度 | Cache | 虚拟存储 |
|---|---|---|
| 谁管 | 硬件全自动 | OS + 硬件（MMU） |
| 缺失代价 | 几十 ns | 缺页 → 磁盘 I/O，百万倍 |
| 块大小 | 64B 级 | 4KB 级 |
| 映射 | 组相联为主 | 页表（全相联思想：任何页进任何页框） |
TLB（快表）：页表太大、查一次页表要多访存一次，于是把最热的页表项缓存进 MMU 里的小 SRAM——它就是"页表的 Cache"，用全相联（或组相联）。TLB 命中 → 地址翻译 1 次访存搞定；TLB 缺失 → 再查页表。完整流程：TLB → 页表 → Cache → 主存 → 磁盘，每一级都是同一套"金字塔 + 局部性"思想。
⚠️ 408 高频题：给 TLB 命中率、Cache 命中率，算"访问一次数据的平均耗时"——把这条链的时间相加即可，注意"TLB 和 Cache 同时命中最快"这条捷径。
七、盲点自测
- SRAM 和 DRAM 的存储原理、用途各是什么？（触发器/电容；Cache/主存）
- 4 体低位交叉编址、T=8τ，读 4 个字要多久？（T+3τ=11τ）
- 直接映射的地址三段怎么切？（标记|行号|偏移，行号在中，偏移在底）
- LRU 和 FIFO 的区别用一句话说？（LRU 看"最久未用"，FIFO 看"最早进来"——最老的块可能最热）
- 回写法为什么需要脏位？（区分"改过要写回"与"没改直接扔"）
- TLB 缓存的是什么？它在金字塔的哪一层？（页表项/页框号；MMU 内的 SRAM，比 L1 更小更快）
- 平均访存时间公式里 (1−h) 为什么直接用 tm 不用 tc+tm？（近似：缺失时数据直接从主存来；严格式为 tc+(1−h)tm，注意题目口径）
八、动手玩
# 看 CPU 的 Cache 结构（macOS）
sysctl -a | grep -i cache
# hw.l1icachesize / hw.l1dcachesize / hw.l2cachesize / hw.l3cachesize
# Linux 更详细
lscpu | grep -i cache # L1d/L1i/L2/L3 的容量与映射关系
注意输出里 L1i 和 L1d 是分开的——这就是 01-系统概述 里说的"现代 CPU 的 L1 是哈佛结构"，为了取指和取数不打架。
参考资料
- 王道《计算机组成原理考研复习指导》第 3 章
- CSAPP 第 6 章《存储器层次结构》——本章的"黄金完整版"，六组相联映射讲得最透
- 01-计算机硬件速览——金字塔的感性版；06-内存管理——虚拟存储的 OS 视角
💬 评论