Article

CH5 存储器层次结构

从局部性原理、Cache 映射方式到 AMAT 与虚拟内存，梳理存储器层次结构的核心逻辑。

April 18, 2026 修考 29 min read

[TOC]

这篇文章在讲什么

存储器层次结构要解决的核心矛盾很直接：

快的存储器通常贵且小
大的存储器通常便宜但慢

因此，这一章始终围绕三个问题展开：

为什么 Cache 能显著提升性能？
数据在 Cache 中是怎么放、怎么找、怎么替换的？
当 Cache 还不够时，虚拟内存又是怎么继续扩展存储层次的？

如果把整章压缩成一句话，那就是：利用局部性，把“经常用的数据”尽量放在离 CPU 更近的地方。

局部性原理

Cache 能有效，不是因为它“猜得准”，而是因为程序访问内存本身就有规律。这种规律就是局部性原理。

程序的局部性主要体现在两方面：

时间局部性：刚访问过的数据，短时间内很可能再次被访问。
空间局部性：与当前地址相邻的数据，很可能很快被访问。

存储器层次结构就是围绕这两点设计的：

利用时间局部性，把最近访问的数据留在上层存储器中。
利用空间局部性，每次不是只搬一个字节，而是把一整块数据一起搬上来。

存储器层次结构

从离 CPU 最近到最远，存储器通常呈现出“越近越快、越远越大”的层次关系。

存储器层次结构示意图

可以这样理解：

寄存器 / Cache：容量小，但极快。
主存 DRAM：容量较大，但比 Cache 慢。
磁盘 / SSD：容量更大，但访问速度远慢于主存。

目标不是让所有数据都常驻最快层，而是让大多数访问都能在高层命中，从而把平均访问时间压低。

常见存储器技术

技术	成本	速度	常见用途
SRAM	高	最快	Cache
DRAM	中	较快	主存
闪存	较低	较慢	SSD、移动设备存储
磁盘	最低	最慢	大容量长期存储

Cache 的核心问题

Cache 本质上是主存的高速缓冲区。理解 Cache，最重要的是搞清楚三件事：

块放在哪里：主存中的一个块可以放到 Cache 的哪些位置？
怎么判断命中：CPU 如何知道要找的数据是否已经在 Cache 中？
缺失时怎么办：如果没命中，要替换谁、怎么写回？

直接映射 Cache

什么是直接映射

在直接映射（direct mapped）Cache 中，每个主存块只能映射到 Cache 中唯一的一行。

常见映射公式是：

\text{Cache 行号} = \text{主存块号} \bmod \text{Cache 行数}

直接映射的优点是结构简单、查找快；缺点是冲突明显，多个块可能被迫争用同一行。

地址如何拆分

直接映射中，一个地址通常拆成三部分：

Tag（标记）：用于确认这一行里是不是目标块。
Index（索引）：用于定位 Cache 的具体行。
Offset（块内偏移）：用于定位块内的具体字节或字。

只要明确了 Cache 行数和块大小，这三部分的位数就可以算出来。

一个具体例子

假设：

内存地址长度为 16 位；
Cache 一共有 8 行；
每个块大小为 4 字节。

那么：

块大小为 $4=2^2$ 字节，所以 Offset 需要 2 位；
Cache 有 $8=2^3$ 行，所以 Index 需要 3 位；
剩余的 11 位就是 Tag。

若访问地址 0x045E：

先转成二进制：0000 0100 0101 1110
从右往左切分：
- Offset：10
- Index：111
- Tag：0000 0100 010
查找过程：
- 先根据 Index 找到第 7 行；
- 再比较该行中的 Tag 是否等于 0000 0100 010；
- 若 Tag 匹配且有效位为 1，则命中；
- 否则缺失，需要把对应主存块装入第 7 行。

这里最关键的直觉是：直接映射先靠 Index 缩小范围，再靠 Tag 做最后确认。

为什么会冲突

设另一个地址 0x047E 的 Index 也恰好是 111，那么它也必须映射到第 7 行。这就意味着：

即使 Cache 其他行是空的；
这两个块仍然只能争用同一个位置。

这类由于映射规则造成的缺失，通常叫做冲突缺失。

直接映射示意图

可以把 Index 理解成“房间号”，把 Tag 理解成“住户姓名”，把 Offset 理解成“房间里的具体床位”。

标记位、有效位和脏位

既然多个主存块可能映射到同一行，Cache 就不能只存数据本身，还必须存一些控制信息。

Tag

Tag 的作用是：在通过 Index 选中某一行后，再判断这一行中存放的是不是当前要找的块。

直接映射本质上是“多个主存块可能对应同一条 Cache 行”，所以只靠 Index 还不够，必须再用 Tag 区分“这一行里现在装的是哪一个块”。

Valid bit

有效位（Valid bit）表示这一行当前内容是否有效：

1：该行存放的是有效数据；
0：该行内容无效，不能作为命中使用。

例如刚开机时，Cache 虽然可能有随机残留内容，但都会被视为无效。

Dirty bit

如果采用写回（write-back）策略，通常还需要一个脏位（Dirty bit）：

1：表示该块在 Cache 中被修改过，但尚未写回下一级存储器；
0：表示该块与下一级存储器一致。

Cache 的读操作

Cache 读操作的流程可以概括为：

用 Index 选中某一行或某一组；
比较 Tag；
检查有效位；
命中则直接按 Offset 取出数据；
缺失则到下一级存储器取回整个块。

Cache 读操作示意图

例如读取地址 00011：

用低位索引选中对应行；
用高位 Tag 去比较；
若匹配且有效，则命中；
否则就是缺失。

这个过程的本质并不复杂：先定位，再核对，最后取数。

直接映射 Cache 的容量计算

考试里经常会区分两个容量概念：

名义容量：只统计数据区；
实际硬件位数：数据区 + Tag + 有效位等控制位。

直接映射 Cache 位数计算示意图

设：

地址长度为 32 位；
Cache 有 $2^n$ 行；
每块有 $2^m$ 个字；
每个字为 32 位，也就是 4 字节。

地址拆分

32 位地址可以拆成：

Tag： $32-(n+m+2)$ 位
Index： $n$ 位
Offset： $m+2$ 位

其中额外的 2 位来自：1 个字 = 4 字节，需要 2 位字节偏移。

每行位数

每行包含：

数据区： $2^m \times 32$ 位
Tag： $32-n-m-2$ 位
Valid：1 位

因此每行总位数为：

2^m \times 32 + (32-n-m-2)+1 = 2^m \times 32 + 31 - n - m

整个 Cache 的总位数为：

2^n \times \left(2^m \times 32 + 31 - n - m\right)

一张表记住

组成部分	位数	说明
数据	$2^m \times 32$	实际存放的数据
Tag	$32-n-m-2$	地址匹配信息
Valid	$1$	该行是否有效
每行总位数	$2^m \times 32 + 31 - n - m$	数据位加控制位
整个 Cache 总位数	$2^n \times (2^m \times 32 + 31 - n - m)$	硬件总开销
Cache 命名容量	$2^n \times 2^m \times 4$ 字节	只统计数据区

Cache 缺失时怎么处理

当访问的数据不在 Cache 中，就发生 Cache miss。此时控制器需要：

到下一层存储器中读取目标块；
若当前位置已被占用，则按替换策略选一个块换出；
将新块装入 Cache；
更新 Tag、有效位，必要时更新脏位；
重新完成原来的读写请求。

如果是指令 Cache 缺失，可以把流程简单理解为：

先根据当前 PC 去下一级取指令所在块；
装入 Cache；
再重新取一次指。

写策略

写操作比读操作复杂，因为它涉及 Cache 和主存内容的一致性。

写直达

写直达（write-through）表示：

每次写 Cache 时，同时也写下一级存储器。

优点：

一致性好维护；
设计相对简单。

缺点：

每次写都可能拖慢执行；
写流量大。

写缓冲

为了减轻写直达的等待，可以加入写缓冲区（write buffer）：

CPU 先把数据写入 Cache 和写缓冲；
缓冲区再异步把数据写回主存。

这样做能减少 CPU 直接等待主存的时间，但如果写缓冲满了，处理器仍然会阻塞。

写回

写回（write-back）表示：

写操作先只更新 Cache，不立即更新下一级存储器。

只有当该块将来被替换出去时，才在必要时写回。它通常需要脏位配合判断是否真的发生过修改。

优点：

写流量更小；
平均性能通常更好。

缺点：

控制逻辑更复杂；
一致性处理更麻烦。

Cache 性能指标

CPU 时间

CPU 时间可以拆成两部分：

理想执行时间；
因为等待存储系统而额外损失的时间。

可以写成：

\text{CPU 时间} = \text{指令数} \times (\text{理想 CPI} + \text{存储器停顿周期/指令}) \times \text{时钟周期}

也就是说，Cache 优化的目标就是尽量减少 memory stall。

AMAT

分析单级 Cache 时，最常用的指标是 AMAT（Average Memory Access Time，平均存储器访问时间）：

\text{AMAT}=\text{命中时间}+\text{缺失率}\times\text{缺失代价}

这个公式必须会背，也必须会解释：

命中时间：访问 Cache 并完成命中的时间；
缺失率：访问中未命中的比例；
缺失代价：发生缺失后，从下一级取回数据所多花的时间。

AMAT 低，不一定意味着 Cache 很大，而是意味着：

命中时间不能太长；
缺失率不能太高；
缺失代价也不能太大。

多级 Cache 的意义

现代处理器通常不只有一级 Cache，而是会配置 L1、L2，甚至 L3。

这样做的核心目的是：降低 miss penalty。

L1 追求极快，重点降低命中时间；
L2/L3 容量更大，重点降低下层访问代价和总体缺失率。

对于两级 Cache，可以这样理解 AMAT：

\text{AMAT} = \text{L1 命中时间} + \text{L1 缺失率} \times (\text{L2 命中时间}+\text{L2 缺失率}\times\text{主存代价})

所以，多级 Cache 并不是“层数越多越好”，而是要在命中时间、缺失率和硬件复杂度之间折中。

更灵活的块放置方式

直接映射简单，但冲突明显。为了减少冲突，可以提高相联度。

全相联

全相联（fully associative）允许一个主存块放到 Cache 的任意一行。

优点：

冲突最少。

缺点：

查找代价高；
硬件实现复杂。

组相联

组相联（set associative）是直接映射和全相联之间的折中。

它的思路是：

主存块先映射到某一组；
再在该组内部的若干行中比较 Tag。

例如 4 路组相联，表示每组有 4 行，主存块只能进入某一固定组，但可在组内 4 行中任选一行放置。

组相联示意图

可以简单比较三种结构：

结构	放置范围	查找成本	冲突情况
直接映射	唯一一行	最低	最明显
组相联	唯一一组内若干行	中等	较少
全相联	任意行	最高	最少

替换策略

当 Cache 缺失且目标位置已满时，就必须替换已有块。

直接映射：没有选择，直接覆盖指定行。
组相联：只在命中的那一组内部选一行替换。
全相联：在整个 Cache 中选择替换对象。

LRU

经典替换策略是 LRU（Least Recently Used），即：

把最近最少使用的块替换出去。

它利用的仍然是时间局部性：最近常用的数据，大概率还会继续用到；很久没用的数据，更适合被淘汰。

除了 LRU，实际硬件中还会使用更简单的近似策略，因为严格维护 LRU 在高相联度下成本不低。

虚拟内存：为什么还需要下一层

前面讲的是 CPU、Cache、主存之间的层次。

但即使有 Cache，主存容量仍然有限。于是还需要在主存和磁盘之间再建立一层更大的层次，这就是虚拟内存。

虚拟内存的目的主要有两个：

让每个程序都拥有独立的地址空间；
让程序使用的地址空间可以大于实际物理内存容量。

严格来说，虚拟内存属于计算机组成原理和操作系统的交叉内容。这里的重点不是系统实现细节，而是理解它仍然是一种“存储器层次结构”。

地址转换

处理器发出的不是物理地址，而是虚拟地址。虚拟地址需要经过地址转换，才能得到真正访问主存用的物理地址。

这样做带来的好处是：

不同程序可以使用相同的虚拟地址；
系统负责把它们映射到不同的物理位置；
从而实现保护、共享和重定位（relocation）。

虚拟地址的组成

分页系统中，虚拟地址一般拆成：

\text{虚拟地址}=\text{虚拟页号}+\text{页内偏移}

虚拟地址与物理地址的页式转换

地址转换时：

虚拟页号经过页表映射，得到物理页号；
页内偏移保持不变；
最终拼成物理地址。

页表与页缺失

页表（page table）的作用是记录：

某个虚拟页是否已经装入主存；
如果在主存中，它对应哪个物理页；
如果不在主存中，它在磁盘上的哪个位置。

页表地址转换示意图

页表项中常见的控制信息包括：

有效位：该页是否在主存中；
脏位：该页是否被修改过；
引用位：该页最近是否被访问过；
物理页号：若在主存中，它映射到哪里。

什么是缺页

如果处理器访问的虚拟页当前不在主存中，就会发生 page fault（缺页）。

缺页与页表映射示意图

缺页代价远高于 Cache miss，因为：

Cache miss 通常只是访问下一级存储器；
缺页往往意味着要从磁盘把一整页调入主存。

处理缺页的一般流程是：

用虚拟地址查页表，发现该页不在主存；
触发异常，由操作系统接管；
选择一个物理页框作为装入位置；
若被换出的页是脏页，则先写回磁盘；
从磁盘读入新页；
更新页表；
重新执行引发缺页的指令。

由于缺页代价太大，虚拟内存系统通常会：

使用较大的页以利用空间局部性；
使用写回机制减少磁盘写流量；
借助 LRU 或近似 LRU 的思路选择替换页。

TLB：页表的 Cache

如果每次地址转换都要先访问主存中的页表，再访问真正的数据，那么一次内存访问会变成两次，代价太高。因此，处理器会用一个更小更快的结构缓存最近使用的页表项，这就是 TLB（Translation Lookaside Buffer）。

TLB 与页表的关系

TLB 可以理解成：

它缓存的是“虚拟页号到物理页号”的映射；
它是页表的高速副本；
它利用的仍然是时间局部性。

TLB 命中与缺失

处理一个虚拟地址时，流程可以概括为：

先查 TLB；
若 TLB 命中，直接得到物理页号；
若 TLB 缺失，再去查页表；
若页表表明该页在主存中，则把映射装入 TLB；
若页表表明该页不在主存中，则触发缺页。

所以要特别区分两个概念：

TLB miss：TLB 中没有这条映射，但页本身可能还在主存中；
page fault：页本身根本不在主存中，需要从磁盘调页。

这两个缺失不在一个层次上，代价也完全不同。

段式管理

除了分页，还存在段式管理（segmentation）的思想：

\text{地址}=\text{段号}+\text{段内偏移}

段式更强调按逻辑结构组织程序，例如代码段、数据段、栈段。不过在现代体系结构中，考试和工程里更常见、也更核心的还是分页与页表、TLB 这一套机制。

用四个问题理解任意两层存储器

无论讨论的是寄存器和 Cache、Cache 和主存，还是主存和磁盘之间的关系，都可以反复用同一套框架理解：

块放在哪里
如何找到块
替换谁
写操作如何处理

这也是存储器层次结构题目最常见的出题方式。

1. 块放在哪里

这个问题对应的就是映射方式。

不同映射方式对比

直接映射：每个块只能放到唯一位置，实现最简单。
组相联：每个块只能进入某一组，但可放在组内任意一行。
全相联：每个块可以放到任意一行，灵活性最高。

相联度越高，通常越能减少因为“争同一个位置”造成的冲突缺失；但代价是查找和硬件实现都会更复杂。

2. 如何找到块

这个问题对应的是地址匹配方式。

不同结构中的查找方式

直接映射：先用 Index 直接定位到唯一一行，再比较 Tag。
组相联：先用 Index 找到某一组，再在组内并行比较多个 Tag。
全相联：没有固定 Index，需要与所有候选行比较 Tag。

因此，相联度越高，定位自由度越大，但比较器数量和查找成本也通常越高。

这里有一个很容易混淆的点：

严格地说，不是“页表是全相联”，而是虚拟页到物理页框的放置关系近似全相联：一个虚拟页可以装入任意物理页框。至于 TLB，本身常见实现则是全相联或组相联，因为它要尽量降低地址转换的缺失代价。

而有些 Cache 会采用直接映射，原因也很直接：访问路径短、时延低、实现简单。在某些处理器里，命中时间比进一步降低缺失率更关键。

3. 替换谁

这个问题只会在“候选位置不止一个”时真正出现。

直接映射：没有选择，目标行固定，直接覆盖。
组相联：只在目标组内部选择替换对象。
全相联：可以在整个 Cache 中选择替换对象。

常见替换策略有：

LRU：替换最近最少使用的块。
随机替换：硬件实现简单，实际中也并不少见。

考试里要特别分清楚“替换范围”和“替换策略”是两回事：
前者由映射方式决定，后者是在候选集合已经确定后，决定具体换掉哪一块。

4. 写操作如何处理

这个问题对应的是写策略。

Write-through：写 Cache 的同时，也立刻写下一级存储器。
Write-back：先只改 Cache，等块被替换时再决定是否写回。

一般来说：

write-through 更直观，一致性更容易维护；
write-back 更节省写流量，适合缺失代价或下层写入代价较大的场景。

如果再配合写缓冲区，write-through 的等待问题还可以进一步缓解。

3C 缺失模型

分析 Cache 行为时，常用 3C 模型 来理解缺失来源：

强制缺失（Compulsory miss）
第一次访问某个块时发生的缺失，几乎不可避免。
容量缺失（Capacity miss）
Cache 总容量不够大，放不下工作集而导致的缺失。
冲突缺失（Conflict miss）
Cache 还有空余或理论容量足够，但因为映射限制，多个块竞争同一位置而发生的缺失。

3C 缺失模型示意图

这三个概念很有用，因为它们分别提示了不同的优化方向：

强制缺失常靠更大的块或预取来缓解；
容量缺失常靠更大的 Cache 来缓解；
冲突缺失常靠提高相联度来缓解。

小结

这一章最值得记住的不是零散术语，而是一条完整主线：

局部性原理解释了为什么分层存储有效。
Cache 解决的是 CPU 和主存之间的速度差距。
映射方式、替换策略、写策略决定了 Cache 的实现与性能。
AMAT 用来衡量 Cache 设计是否有效。
虚拟内存、页表和 TLB 则继续把这种“分层缓存”的思想扩展到主存与磁盘之间。

如果后续继续复习这一章，最值得单独刷题的内容有两类：

直接映射、组相联、全相联的地址划分与结构对比题；
AMAT、缺失率、多级 Cache、TLB 与缺页相关的综合计算题。