计算机组成原理第 3 章：存储器层次结构

408 计算机组成原理「存储器层次结构」复习：核心知识点、真题题型、通用解法与易错点。

本章重点参考了本站 408 真题 → 计算机组成原理 → 第 3 章“存储器层次结构”，并用 408 模拟选择题 → 第 3 章“存储系统” 补充题型。本站也建议研究 Cache 时按“真题 → 总结命题方式 → 模拟题补充”的顺序学习。(Any Docs)

这一章比第1、2章更重要的一点是：它极容易出综合题。 真题页面实际覆盖了“局部性 → 半导体存储器 → 主存组织 → 外存 → Cache → 虚拟存储器”六大块，而 Cache 又会和程序循环、总线、主存、TLB、页表、缺页异常揉在一起考。下文不是简单按教材抄知识点，而是按“考研看到题以后该怎么做”来讲。

一、第 3 章到底考什么？

可以把整章压缩成下面这张知识地图：

局部性 \to DRAM/SRAM \to 主存组织 \to Cache \to 虚拟存储器

外加一个相对独立的：

磁盘与 RAID

其中最值得投入时间的是：

模块	重要程度	典型考法
局部性原理	★★★	判断程序时间/空间局部性
SRAM、DRAM、ROM、Flash	★★★★	DRAM 地址引脚、刷新
主存扩展	★★★★	字扩展、位扩展、地址范围
多体交叉存储	★★★★	体号、冲突、带宽
磁盘、RAID	★★★	平均访问时间、可靠性
Cache 地址映射	★★★★★	Tag/组号/块内偏移
Cache 命中率	★★★★★	数组、循环、访问序列
Cache 总容量	★★★★★	数据位+Tag+有效位+脏位
Cache 写策略/LRU	★★★★	直写/回写、替换位
虚拟存储器	★★★★★	TLB、Page、Cache 联动
Cache+分页+程序综合	★★★★★	408 大题重点

二、做这一章之前必须掌握的“总公式”

以后看到题，第一件事不是算，而是把单位统一。

如果按字节编址：

2^{n} B

需要的地址位数就是

n

例如：

64 MB = 2^{26} B

所以需要 26 位地址。

主存块大小为：

B = 2^{b} B

则块内偏移位数为：

b = lo g_{2} B

Cache 有 $S = 2^{s}$ 组，则组号位数：

s = lo g_{2} S

若物理地址共 $m$ 位，则：

Tag 位数 = m - s - b

这是整个 Cache 章节最重要的公式。

对于 $E$ 路组相联：

Cache 组数 = \frac{Cache 行数}{E}

某主存块 $j$ 应进入的组号：

j mod S

三、题型1：程序局部性

这是后面 Cache、分页所有题的思想基础。

真题：2017 年局部性题

本站中的 2017 真题给出程序：

for (i = 0; i <= 9; i++) {
    temp = 1;
    for (j = 0; j <= i; j++)
        temp *= a[j];
    sum += temp;
}

问：数组 $a$ 的访问具有时间局部性、空间局部性中的哪些？

答案是：两种都有。

为什么？

空间局部性看：

相邻地址会不会连续访问？

内层循环：

a [0], a [1], a [2], \dots

数组连续存储，所以有空间局部性。

时间局部性看：

刚访问过的数据过一会儿会不会再次访问？

例如：

a [0]

在每一次外层循环里都被重新访问。

因此也有时间局部性。

这种题的统一判断法

不要背“数组有空间局部性”。

直接问两个问题：

问题 A：相邻地址是否被连续访问？

如果是：

\Rightarrow 空间局部性

问题 B：同一个地址是否短时间内被反复访问？

如果是：

\Rightarrow 时间局部性

例如：

for(i=0;i<n;i++)
    sum += a[i];

空间局部性强，但单次扫描的数组元素时间局部性很弱。

而：

for(i=0;i<n;i++)
    sum += a[0];

时间局部性极强，但对数组而言几乎没有体现连续地址访问。

四、题型2：SRAM、DRAM、ROM、Flash 基本性质

这一块选择题很多，难度不高，但极容易丢分。

必须形成这张脑内表

存储器	易失	刷新	速度	典型用途
SRAM	是	否	快	Cache
DRAM	是	是	较慢	主存
SDRAM	是	是	较快	主存
ROM	否	否	—	固件
Flash	否	否	读快写慢	SSD/U盘等

真题：2010 RAM 与 ROM

题目给出四个判断：

RAM 易失、ROM 非易失；RAM 和 ROM 都可随机访问；二者都可做 Cache；二者都需要刷新。

正确的是前两项。本站答案为 A。

这里最容易错的是：

“随机存取”和“可随机写入”不是同一个概念

ROM 虽然不能像 RAM 那样任意改写，但可以按地址直接访问某个单元，因此：

ROM 也属于随机访问

五、题型3：DRAM 地址引脚

这是高频小计算题。

真题：2014 年

题意：

某 DRAM 芯片规格为 $4 M \times 8$ 位，求地址引脚与数据引脚总数。

网站答案是 19。

因为：

4 M = 2^{22}

如果 SRAM 不进行地址复用，一般需要 22 根地址线。

但 DRAM 使用：

行地址 / 列地址复用

于是把：

2^{22}

组织为：

2^{11} \times 2^{11}

只需要：

11

根地址引脚。

数据宽度：

8 bit

所以总数：

11 + 8 = 19

六、题型4：DRAM 刷新与行列组织

真题：2018 年

题意：

一个 $2 K \times 1$ 位 DRAM，阵列为 $r \times c$ ，既要求地址引脚最少，又要求刷新开销尽量小，应该怎样选择 $r, c$ ？

网站答案：

r = 32, c = 64

因为：

r c = 2048 = 2^{11}

候选：

64 \times 32

和：

32 \times 64

都只需 6 根复用地址线。

这时第二个要求发挥作用：

DRAM 通常按行刷新。

因此：

行数越少，需要刷新的行越少

所以选：

32 \times 64

而不是：

64 \times 32

考研陷阱

千万不要以为 DRAM 阵列一定“尽量方”。

如果题目只有：

地址引脚最少

则尽可能接近平方。

如果又加一句：

刷新开销尽量小

则在地址引脚相同的方案中：

选行数较少的

七、题型5：DRAM 内存条、行缓冲、总线宽度

真题：2022 年

题意：

内存条包含 8 个 $8192 \times 8192 \times 8$ 位 DRAM 芯片，总线宽 64 位，每片有行缓冲。判断容量、地址引脚和行缓冲大小等说法。

网站判断错误项是“芯片地址引脚为26位”。

因为：

8192 = 2^{13}

阵列：

8192 \times 8192

虽然逻辑地址需要：

13 + 13 = 26

位，但 DRAM 行列地址复用，所以物理地址引脚只有：

13

根。

每个芯片每次激活一整行，因此行缓冲：

8192 \times 8 bit

这一题把四个概念揉在一起：

DRAM 组织 + 地址复用 + 并行扩展 + 行缓冲

八、题型6：主存芯片扩展——位扩展、字扩展

这是必会题型。

真题：2009 年

题意：

64KB 主存，其中 4KB 为 ROM，其余 RAM。使用 $2 K \times 8$ ROM 和 $4 K \times 4$ RAM，分别需要多少片？

网站答案：

2, 30

通用方法：先位扩展，再字扩展

目标 RAM：

60 KB

单片：

4 K \times 4

但计算机按字节访问，要得到：

8 bit

所以先做位扩展：

\frac{8}{4} = 2

两片并联：

4 K \times 4 \to 4 K \times 8

一组相当于：

4 KB

需要：

\frac{60}{4} = 15

组。

因此：

15 \times 2 = 30

片。

一条万能公式

目标：

M \times N

芯片：

m \times n

则理论芯片数：

\frac{M}{m} \times \frac{N}{n}

其中：

\frac{N}{n}

是位扩展。

\frac{M}{m}

是字扩展。

九、题型7：芯片对应地址范围

真题：2010 年

题意：

用 $2 K \times 4$ 芯片组成 $8 K \times 8$ 存储器，地址 $0 B 1 F H$ 所在芯片组的最小地址是多少？

答案：

0800 H

一个芯片组的地址容量：

2 K = 2^{11} = 0800 H

所以区间：

0000 H \sim 07 F F H

0800 H \sim 0 F F F H

1000 H \sim 17 F F H

……

而：

0 B 1 F H

落在：

0800 H \sim 0 F F F H

因此最小地址：

0800 H

以后这种题最快做法

设每组大小为：

S

则某地址 $A$ 所在组起始地址：

⌊ \frac{A}{S} ⌋ S

十、题型8：MAR 到底由什么决定？

真题：2011 年

题意：

主存地址空间 64MB，但机器实际只装了 32MB RAM，MAR 至少多少位？

答案：

26

因为：

64 MB = 2^{26} B

这里考的是一个非常经典的坑：

MAR 位数由可寻址地址空间决定

不是：

当前实际插了多少内存

就像一个 CPU 能寻址 4GB，并不意味着机器必须装满 4GB RAM。

十一、题型9：多体低位交叉存储——体号

这个知识点真题和本站模拟题都非常多。

低位交叉编址，若有 $m$ 个存储体：

体号 = 地址 mod m

真题：2015 年

题目给出 4 体交叉存储的访问序列：

8005, 8006, 8007, 8008, 8001, 8002, 8003, 8004, 8000

问可能冲突的地址对。

网站答案：

8000, 8004

因为：

8004 mod 4 = 0

8000 mod 4 = 0

都访问 0 号体，而且时间距离太近。

十二、题型10：多体交叉存储最大带宽

本站模拟题专门强化了这一点。

例如王道模拟题：

八体低位交叉存储器，每体一次传 64 bit，每体存储周期 80ns，求最大带宽。

网站给出的结果是：

800 MB/s

因为：

m = 8

每体一次：

64 bit = 8 B

存储周期：

T = 80 ns

理想轮流启动：

Δ t = \frac{T}{m} = \frac{80}{8} = 10 ns

所以：

B_{m a x} = \frac{8 B}{10 ns}

即：

800 MB/s

最方便直接记：

B_{m a x} = \frac{mW}{T}

其中 $W$ 是每体一次传送的字节数。

十三、题型11：磁盘平均访问时间

磁盘题最大的坑就是：

不要漏平均旋转延迟

平均磁盘访问时间一般写成：

T = T_{s} + T_{r} + T_{t} + T_{c}

其中：

T_{s} = 平均寻道时间

T_{r} = 平均旋转延迟

T_{t} = 数据传输时间

T_{c} = 控制器延迟

真题：2013 年

本站题目：

磁盘转速 10000 转/分，平均寻道 6ms，传输率 20MB/s，控制器延迟 0.2ms，读取 4KB 数据，求平均时间。

先求一圈：

T_{rev} = \frac{60}{10000} = 0.006 s = 6 ms

平均旋转等待半圈：

T_{r} = 3 ms

传输时间约：

T_{t} = \frac{4 KB}{20 MB/s} \approx 0.2 ms

因此：

T \approx 6 + 3 + 0.2 + 0.2

T \approx 9.4 ms

真正占大头的是机械运动时间。

十四、题型12：RAID

真题：2013 年

题意：

磁盘镜像、条带化、奇偶校验、增加 Cache 中，哪些能够提高 RAID 可靠性？

答案：

镜像 + 奇偶校验

记住：

条带化：

性能

镜像：

冗余、可靠性

奇偶校验：

冗余、可靠性

Cache：

性能

所以不要看到 RAID 就条件反射认为“条带化提高可靠性”。

十五、下面进入本章最重要部分：Cache

如果第 3 章只能重点学一半，就学 Cache + 虚拟存储器。

真题里从 2009 年开始就连续出现组号、命中率，2010 年开始出现程序综合题，之后又考 Cache 容量、分离 Cache、TLB、分页以及完整 Cache 访问流程。

十六、题型13：主存地址 → Cache 组号

真题：2009 年

题意：

Cache 共16块，2路组相联，每块32B。主存129号字节应映射到哪一组？

网站答案：

4

先求主存块号：

⌊ \frac{129}{32} ⌋ = 4

Cache：

16 行

2 路：

S = \frac{16}{2} = 8 组

于是：

4 mod 8 = 4

所以：

第 4 组

Cache 映射题万能四步法

以后不管题多复杂，固定：

第一步：求块大小。

B = 2^{b}

第二步：求 Cache 组数。

S = \frac{Cache 容量}{B \times E}

第三步：求主存块号。

j = ⌊ \frac{地址}{B} ⌋

第四步：组号。

j mod S

十七、题型14：Cache 命中率基本计算

真题：2009 年

题意：

总访存1000次，Cache缺失50次，求命中率。

命中：

1000 - 50 = 950

所以：

H = \frac{950}{1000} = 95%

最重要的两个式子：

H = \frac{N _{hit}}{N}

以及：

H = 1 - \frac{N _{miss}}{N}

十八、题型15：程序数组访问与 Cache 命中率

这是 408 最核心题型之一。

真题：2010 年程序 A/B

题目给定：

数据 Cache 8 行；
每行 64B；
直接映射；
int 为 4B；
二维数组 a[256][256] 按行优先；
数组首地址 320；
比较按行访问与另一种跨行访问程序。

题目要求：

Cache 总容量；
a[0][31]、a[1][1] 映射到哪行；
两个程序命中率及谁更快。

网站算出的核心结果：

H_{A} = 93.75%

H_{B} = 0

为什么 A 是 93.75%？

Cache 块：

64 B

每个 int：

4 B

一个块可装：

\frac{64}{4} = 16

个整数。

连续访问：

a [i] [0], a [i] [1], \dots

第一次访问某块：

miss

随后 15 个：

hit

因此：

H = \frac{15}{16} = 93.75%

这是一类极其重要的结论：

连续访问数组时，如果一个 Cache 块能装 $k$ 个元素，且没有冲突，则通常每 $k$ 次访问只有第一次缺失。

于是：

H \approx \frac{k - 1}{k}

十九、为什么按列访问可能直接变成 0%？

二维数组按行优先。

如果：

for(j...)
    for(i...)
        a[i][j]

相邻访问之间跨度是一整行。

2010 真题中跨距：

256 \times 4 = 1024 B

Cache 块：

64 B

相隔：

\frac{1024}{64} = 16

个块。

而 Cache 只有 8 行：

16 mod 8 = 0

所以这些地址总是竞争同一个 Cache 行。

结果：

A \to B \to A \to B

刚调进来就被另一个块赶走。

称为：

冲突缺失 / 抖动

于是甚至可以出现：

H = 0

本站模拟题还专门强调：无论直接映射还是组相联，只要访问序列设计得足够恶劣，都可能出现“刚换出又访问”的情况，缺失率甚至达到 $100%$ 。

所以：

提高关联度通常减少冲突缺失，但绝不是 “ 一定不缺失 ”

二十、题型16：Cache 地址格式

这一题几乎必须做到条件反射。

设：

主存地址 $m$ 位；
块大小 $2^{b}$ B；
Cache 共 $2^{s}$ 组。

地址：

m - s - b Tag s 组号 b 块内偏移

例如：

32 位地址，

块：

64 B = 2^{6} B

所以：

b = 6

Cache 数据区：

32 K B = 2^{15} B

8 路组相联：

S = \frac{2 ^{15}}{2 ^{6} \times 8} = 2^{6}

所以：

s = 6

Tag：

32 - 6 - 6 = 20

位。

二十一、题型17：Cache 总容量，而不是数据容量

这类题特别喜欢骗人。

真题中出现过：

Cache 能存 4K 字数据，问“Cache 总容量至少多少位”。

此时：

Cache 总容量 \neq = Cache 数据容量

每一行除了数据，还可能有：

Tag

有效位 Valid

修改位 Dirty

替换算法状态位

所以一般：

C_{total} = C_{data} + C_{tag} + C_{control}

二十二、什么时候需要 Dirty 位？

这是经常和总容量一起考的。

回写 Write Back

CPU 写 Cache：

只修改 Cache

该行需要标记：

D i r t y = 1

换出时才写回主存。

因此：

需要修改位

直写 Write Through

每次写 Cache：

同时写主存

Cache 和主存始终一致。

因此通常：

不需要 Dirty 位

二十三、题型18：指令 Cache 与数据 Cache 为什么分离？

真题：2014

题目：

采用指令 Cache 与数据 Cache 分离的主要目的是什么？

答案：

减少指令流水线资源冲突

不要选：

提高命中率。

真正原因是：

取指：

I F \to I -Cache

数据访问：

M E M \to D -Cache

可以同时发生。

如果共用一个 Cache 端口：

I F

与：

M E M

可能争用资源。

因此属于：

结构冒险

这会在 CPU 流水线章节再次出现。

二十四、题型19：LRU 位数

2020 年真题非常典型。

题目条件：

32位主存地址；
8路组相联；
32KB数据区；
块64B；
直写；
LRU；
Cache 初始为空。

并问 Tag、LRU 位、是否有修改位以及程序访问等。

8 路意味着每组有 8 行。

若教材按“每行记录相对新旧次序”的常见编码方法：

每行需要：

lo g_{2} 8 = 3

位 LRU 状态。

这一点应根据题目采用的 LRU 实现描述判断；408 一般不会要求设计完整硬件编码。

而由于：

Write Through

所以：

无修改位

二十五、2020 Cache 综合题：顺序数组到底 miss 几次？

题目程序：

for (k = 0; k < 1024; k++)
    s[k] = 2 * s[k];

int=4B，Cache 块 64B。

数组大小：

1024 \times 4 = 4096 B

每块：

64 B

因此涉及：

\frac{4096}{64} = 64

个主存块。

由于顺序访问、没有冲突问题，每个块第一次缺失。

因此核心思想就是：

N_{miss} = 访问到的不同主存块数

这条规则以后非常好用。

二十六、题型20：完整描述一次 Cache 访问过程

2020 真题第三问专门要求说明：

CPU 第一次读取主存地址 00010003H 中的指令，Cache 初始为空，描述完整访问及缺失处理过程。

这是很有代表性的大题表达模板。

答题时按照：

地址分解 \to 定位组 \to Tag 比较 \to 判断 Hit/Miss \to 主存调块 \to 替换

写。

第一步，根据物理地址拆出：

T a g

S e t

O f f se t

第二步，用 Set 直接选中目标组。

第三步，同时读取该组所有路的：

T a g + V a l i d

进行比较。

如果某一路：

V a l i d = 1

且：

T a g_{cache} = T a g_{addr}

则命中。

否则 Miss。

Cache 初始为空：

V a l i d = 0

因此必然 miss。

然后从主存调入：

整个主存块

不是只取 CPU 要的几个字节。

最后：

有空行：直接放；
无空行：按 LRU 替换；
写 Tag；
置 Valid；
更新 LRU；
根据 Offset 取出目标字节。

这套文字模板很值得直接掌握。

二十七、题型21：Cache 平均访问时间

这部分真题经常与性能计算结合。

如果：

Cache 命中时间：

T_{c}

命中率：

H

缺失代价：

T_{m}

常见表达：

A M A T = T_{c} + (1 - H) \times P

其中 $P$ 为 miss penalty。

如果题目明确说：

不命中时先访问 Cache 后再访问主存

也可写：

T = H T_{c} + (1 - H) (T_{c} + T_{m})

整理：

T = T_{c} + (1 - H) T_{m}

关键不是死记哪个形式，而是弄清：

题目给的“主存时间”究竟是不是已经包含前面的 Cache 查询。

二十八、题型22：CPU、Cache、主存、总线综合

本站 2012 年真题非常典型，题目一次问：

CPU 主频 80MHz；
CPI=4；
平均每条指令访存1.5次；
Cache块16B；
命中率99%；
总线宽32位；
求 MIPS、每秒 Cache miss 次数、主存最低带宽；
又加入缺页率；
再加入 DMA；
最后计算四体交叉主存最大带宽。

这类题不要试图“一步算完”，应该画数据流：

C P U \to C a c h e \to M e m or y \to D i s k

第一步：CPU 每秒多少条指令

I P S = \frac{f}{C P I}

即：

\frac{80 M}{4} = 20 M

所以：

20 MIPS

第二步：每秒访存次数

每条指令：

1.5

次访存。

所以：

20 M \times 1.5 = 30 M

次/秒。

第三步：每秒 Cache miss

Miss rate：

1 - 0.99 = 0.01

所以：

30 M \times 0.01 = 300000

次/秒。

如果每次 miss 调：

16 B

则由 Cache miss 产生的数据流量：

300000 \times 16 B

这就是分析主存带宽的核心。

二十九、虚拟存储器：先把三层关系彻底分清

这是大量同学最混乱的地方。

一次 CPU 虚拟地址访问：

V A \to T L B / P a g e T ab l e \to P A \to C a c h e \to M e m or y

TLB解决：

虚拟页号 \to 物理页框号

Cache解决：

物理地址对应的数据是否已在高速缓存

Page解决：

该虚拟页是否已经在主存

这三个“命中”的对象完全不同。

三十、题型23：TLB、Cache、Page 命中组合

真题：2010 年

题目问：

下列哪一种组合不可能？

A. TLB miss、Cache miss、Page miss B. TLB miss、Cache hit、Page hit C. TLB hit、Cache miss、Page hit D. TLB hit、Cache hit、Page miss

答案：

D

为什么？

如果：

T L B hi t

说明 TLB 中已经存在有效的：

V P N \to P F N

映射。

这意味着对应页面当前应在主存中。

因此：

T L B hi t \Rightarrow P a g e hi t

所以：

T L B hi t + P a g e mi ss

是不可能的正常状态。

但 TLB miss + Cache hit 为什么可能？

很多人会错。

TLB miss 只表示：

页表项不在 TLB。

可以去主存查页表，得到物理地址。

然后目标数据完全可能已经：

C a c h e hi t

所以：

T L B mi ss \neq \Rightarrow C a c h e mi ss

三十一、必须掌握的命中逻辑关系

最重要：

T L B hi t \Rightarrow P a g e hi t

但：

C a c h e hi t

和：

T L B hi t

没有这种简单必然关系。

也就是说：

T L B

管“地址翻译缓存”。

C a c h e

管“数据缓存”。

不要混为一谈。

三十二、题型24：TLB 和 Cache 的异同

真题：2020 年

题目问错误说法：

A. 命中率都与程序局部性有关 B. 缺失后都需要进一步访问存储层次 C. 缺失处理都可以由硬件实现 D. 都由 DRAM 构成

答案是：

D

因为 TLB 和 Cache 都追求极高速，一般采用：

SRAM / 专用高速结构

而不是 DRAM。

三十三、题型25：页大小 → 页内偏移

分页题看到页大小：

4 K B

立刻写：

4 K B = 2^{12} B

所以页内偏移：

12 位

若虚拟地址：

32 位

则虚页号：

32 - 12 = 20

位。

如果物理地址：

24 位

则物理页框号：

24 - 12 = 12

位。

这是所有分页地址题的起点。

三十四、题型26：虚拟地址转换

网站 2022 真题给出了：

24位主存地址、4GB虚拟地址空间、4KB页大小，并给出页表，要求把虚拟地址 00082840H 转换为物理地址。

这种题固定做法：

把：

V A

拆为：

V P N ∣ P a g e O f f se t

4KB 页：

P a g e O f f se t = 12 bit

所以十六进制地址低：

3

位十六进制数就是页内偏移。

例如：

00082840 H

低三位：

840 H

因此：

O f f se t = 840 H

剩余高位：

V P N = 82 H

然后查页表得到：

P F N

最后：

P A = (P F N ≪ 12) + 840 H

分页地址转换大部分题本质就是这个模板。

三十五、题型27：缺页异常

这里需要和 OS 联动。

如果页表项显示：

P r ese n t = 0

说明页面不在主存。

触发：

Page Fault

这是：

异常 / 内中断

不是普通 Cache miss。

Cache miss：

通常由硬件自动处理

而缺页：

需要 OS 介入

通常过程：

C P U 访问页面 \to 页表发现不在内存 \to 缺页异常 \to O S 选择页框 \to 从磁盘调页 \to 更新页表 \to 重新执行指令

三十六、题型28：Cache + TLB + 缺页的访存次数

本站的模拟题专门给了一类很好的训练：

分别讨论：

TLB hit、Cache hit；
TLB miss、无缺页、Cache miss；
TLB miss、Page fault、Cache miss；
TLB hit、Cache miss。

然后统计主存访问次数。

核心思想：

TLB hit

不用查主存页表。

TLB miss，但 Page hit

必须：

访问页表

获得 PFN。

Cache miss

还要：

访问主存中的目标块

所以最常见的普通情形：

TLB miss + Page hit + Cache miss：

1 次页表 + 1 次数据

三十七、本章最高价值题型：Cache + 分页 + 二维数组

本站中还有一道非常典型综合题，给定：

int a[24][64];

for (i = 0; i < 24; i++)
    for (j = 0; j < 64; j++)
        a[i][j] = 10;

数组：

按行优先；
首虚拟地址 00422000H；
int=4B；
开始时数组不在内存；
要求计算页数、缺页次数、局部性、Cache 地址位、元素地址、组号、Cache 块数和命中率。

这基本就是第 3 章的“毕业题”。

三十八、先算数组大小

数组：

24 \times 64

个 int。

所以：

24 \times 64 \times 4 = 6144 B

即：

6 K B

如果页大小：

4 K B

又由于起始地址：

00422000 H

恰好页对齐。

所以占：

2 页

第一次进入每一页都会缺页。

因此：

2 次缺页

网站给出的两个故障地址分别是：

00422000 H

和：

00423000 H

三十九、二维数组元素地址公式一定要会

对于：

a [M] [N]

按行优先，每个元素大小为 $w$ 。

则：

A dd r (a [i] [j]) = B a se + (i N + j) w

比如：

a [1] [0]

这里：

N = 64, w = 4

所以：

A dd r = 00422000 H + (1 \times 64 + 0) \times 4

即：

00422000 H + 100 H = 00422100 H

这也是网站给出的结果。

四十、数组总占几个 Cache 块？

如果 Cache 块：

32 B

数组：

6144 B

那么：

\frac{6144}{32} = 192

块。

网站结果也是：

192

每块：

\frac{32}{4} = 8

个 int。

连续访问时：

第一次 miss，后面 7 次 hit。

所以：

H = \frac{7}{8} = 87.5%

网站给出的原循环命中率同样是 $87.5%$ 。

四十一、为什么有时交换循环顺序后命中率居然不变？

这是这道题很好的地方。

通常认为：

按列访问一定很差。

但是不能死记。

这道题交换循环顺序以后，虽然访问顺序变了，但题目给出的 Cache 结构和数组布局使得总体仍产生：

192

次缺失。

于是：

H = \frac{1536 - 192}{1536} = 87.5%

这说明 408 真正想考的不是：

“ 行优先一定好，列优先一定坏 ”

而是要求真的计算：

地址 \to 块号 \to 组号 \to 替换情况

四十二、Cache 程序题真正的万能算法

以后碰到数组循环，建议固定按照下面的方法。

先求一个 Cache 块能放多少数组元素：

k = \frac{B}{s i z eo f ( e l e m e n t )}

然后把程序产生的地址序列写成：

A_{1}, A_{2}, A_{3}, \dots

再变成主存块号：

B_{i} = ⌊ \frac{A _{i}}{B l oc k S i z e} ⌋

再变成组号：

S_{i} = B_{i} mod N_{set}

最后只判断三件事：

是不是第一次访问这个块；
这个块是不是还在 Cache；
有没有被映射到同组的其他块替换掉。

如果没有冲突：

miss 次数 \approx 访问过的不同块数

如果有冲突，则必须模拟替换。

四十三、三种 Cache 映射必须真正理解

1. 直接映射

每个主存块只能进入：

唯一一个 Cache 行

规则：

j mod N

优点：

简单、快

缺点：

冲突严重

2. 全相联

主存块可以进入：

任意 Cache 行

优点：

冲突缺失最少

缺点：

所有 Tag 都要比较：

硬件复杂

3. 组相联

折中。

例如 8 路组相联：

先确定唯一组，再在组内 8 行任选

这也是现在考研综合题最常见的结构。

四十四、Cache 的三类缺失

理解这三个概念，对模拟题特别重要。

强制缺失 Compulsory Miss

第一次访问某块：

必然 miss

容量缺失 Capacity Miss

程序工作集太大：

整个 Cache 装不下

即使全相联也会发生。

冲突缺失 Conflict Miss

多个块竞争同一位置/同一组：

映射冲突

提高关联度主要减少：

冲突缺失

但不能消灭容量缺失和强制缺失。

所以模拟题：

“提高 Cache 关联度一定降低缺失率”

这个“一定”就是错点。

四十五、替换算法怎么考？

直接映射：

根本不用选择替换谁

因为位置唯一。

全相联/组相联才需要：

L R U, F I F O, R an d o m

最常见：

L R U

遇到访问序列：

A, B, C, A, D

要记录最近使用顺序。

不要把：

F I F O

和：

L R U

混起来：

FIFO 看：

谁最早进入

LRU 看：

谁最长时间没有被访问

四十六、写策略四个概念

这部分容易混。

写命中时

Write Through

C a c h e \leftarrow d a t a

同时：

M e m or y \leftarrow d a t a

一致性简单。

Write Back

只：

C a c h e \leftarrow d a t a

并：

D i r t y = 1

换出再写主存。

写不命中时

又分：

Write Allocate

先把块：

M e m or y \to C a c h e

再写 Cache。

No Write Allocate

直接写较低层，不把块调入 Cache。

典型组合经常是：

W r i t e B a c k + W r i t e A l l oc a t e

或：

W r i t e T h r o ug h + N o W r i t e A l l oc a t e

但考试必须服从题目条件，不能当成绝对规则。

四十七、Cache 与虚拟存储器本质上其实是一类思想

它们都是利用：

程序局部性

建立快慢两层存储。

Cache：

C P U \leftrightarrow C a c h e \leftrightarrow M e m or y

虚拟存储：

M e m or y \leftrightarrow D i s k

但是二者有几个关键差异：

Cache	虚拟存储器
块为交换单位	页为交换单位
miss代价较低	缺页代价极高
主要硬件处理	OS必须参与
允许直接映射	页面几乎相当于全相联
替换硬件完成	页面置换主要软件完成

原因非常重要：

磁盘一次缺页可能：

毫秒

而 CPU 周期可能：

纳秒

缺页代价差了几个数量级。

所以虚拟存储器必须尽可能降低冲突。

四十八、这一章最容易出现的 12 个坑

做题时特别检查这些：

MAR 看地址空间，不看已安装 RAM。
DRAM 行列地址复用，不能把行位+列位当物理地址引脚。
DRAM 刷新按行。
低位交叉体号是地址模体数。
平均旋转延迟是一圈时间的一半。
Cache 数据容量不等于 Cache 总容量。
回写需要 Dirty，直写通常不需要。
直接映射没有替换算法选择问题。
组相联的组数不是 Cache 行数。
TLB hit 必然意味着 Page hit。
TLB miss 不意味着 Page miss。
Cache miss 也不等于 Page fault。

四十九、408 综合题的标准解题顺序

当一道大题同时出现：

虚拟地址、页表、TLB、Cache、数组、总线……

不要乱。

固定按：

V A \to V P N + O f f se t

再：

V P N T L B / P a g e T ab l e P F N

得到：

P A

再：

P A \to T a g + S e t + B l oc k O f f se t

最后：

C a c h eH i t / M i ss

也就是：

先翻译地址，再访问 Cache

这是最稳的逻辑链。

五十、建议把第 3 章最终浓缩成这 8 个“母题”

如果下面 8 类能够独立完成，第 3 章基本就掌握了：

母题	必须会
DRAM题	行列地址、刷新、引脚
芯片扩展题	位扩展+字扩展
交叉存储题	体号、冲突、带宽
Cache地址题	Tag/Set/Offset
Cache容量题	数据+Tag+控制位
数组Cache题	元素地址、块号、冲突、命中率
TLB/Page题	虚页→实页、可能命中组合
综合题	数组+分页+TLB+Cache+缺页

其中真正必须反复刷的是：

Cache 地址划分 + 数组访问 + 分页 /TLB

因为这三类最容易组合成 408 大题。

五十一、最后给出一张“看到题立刻写什么”的速查表

看到 $4 K B$ 页：

4 K B = 2^{12} B

立即写：

页内偏移 12 位

看到 $64 B$ Cache 块：

64 B = 2^{6} B

立即写：

块内偏移 6 位

看到 8 路组相联：

组数 = \frac{Cache 容量}{块大小 \times 8}

看到二维数组：

A dd r (a [i] [j]) = B a se + (i N + j) \times s i z eo f (T)

看到低位交叉：

B ank = A dd r ess mod m

看到 Cache hit rate：

H = 1 - \frac{M i ss}{T o t a l}

看到平均访存时间：

A M A T = H i tT im e + M i ss R a t e \times M i ss P e na l t y

看到磁盘：

T = T_{seek} + T_{rotation} + T_{transfer} + T_{controller}

看到 TLB/Page/Cache：

先记住：

T L B hi t \Rightarrow P a g e hi t

但：

T L B mi ss \neq \Rightarrow P a g e mi ss

第 3 章的真正核心

如果只记一句话：

所有题最终都是 “ 地址在哪里，以及这一层现在有没有它 ”

DRAM 问：

地址怎样送进芯片？

主存扩展问：

地址落在哪片芯片？

交叉存储问：

地址落在哪个存储体？

Cache 问：

主存块落在哪一组？

分页问：

虚页落在哪个物理页框？

TLB 问：

页表映射有没有被缓存？

所以这一章表面知识点很多，本质上围绕的始终是 地址、映射、局部性和层次化缓存。把这四件事真正搞清楚以后，2010、2012、2014、2020 这种看起来很长的综合题，其实只是把同一套地址分析连续做几遍而已。

计算机组成原理第 3 章：存储器层次结构

On this page