Cache 与映射方式

概念

Cache（高速缓冲存储器）是一块容量小、速度接近 CPU 的存储器，里面放的是主存内容的副本——最近被访问过、以及它们附近的数据。

它成立的前提是第 10 篇讲的两条局部性。有了局部性，程序在一小段时间里真正用到的数据，只是整个主存里很小的一块；把这一小块搬到 CPU 旁边，就能挡住绝大多数访问。

Cache 有两个必须一次记住的特性：

1. 内容是副本，不是唯一真身。 主存里永远有那份"原始的"数据，Cache 只存拷贝。这带来"写的时候要不要也改主存"的问题——写策略。
2. 对程序员完全透明。 硬件自动把块搬进来、搬出去，程序看不到 Cache 的存在。

本章的主线：一个主存块，能被放到 Cache 的哪些位置？ 这就是"映射方式"，是全部考点的起点。

原理

一、三个基本术语

术语	含义
块 / 行（block / line）	主存与 Cache 之间数据传送的最小单位。主存叫"块"，Cache 叫"行"，大小相同
命中（hit）	CPU 要的数据就在 Cache 里
缺失（miss）	CPU 要的数据不在 Cache 里，需要从主存调入

主存:  ┌──块0──┬──块1──┬──块2──┬──块3──┬──块4──┬ …  （每块若干字节）
Cache: ┌──行0──┬──行1──┬──行2──┬ …                    （行数远少于块数）

为什么按块传送而不按字：空间局部性。一次把整块搬进来，接下来的邻近访问就全部命中了。块越大，单次传送的摊薄成本越低，但块太大又会把用不上的数据搬进来、并减少 Cache 能容纳的块数——这就是"块大小"要折中的原因。

二、地址划分：三种映射方式的统一框架

CPU 给出的是主存地址，Cache 需要把它切成三段来问："这是哪个主存块？该放到哪一行？我要块里的第几个字节？"

$$\text{主存地址}=\underset{\text{tag}}{\underbrace{\text{标记}}}\mid \underset{\text{index}}{\underbrace{\text{索引}}}\mid \underset{\text{offset}}{\underbrace{\text{块内地址}}}$$

映射方式	索引字段是什么	索引位数	标记位数
直接映射	行号（主存块号 $mod$ Cache 行数）	${\log }_2(\text{Cache 行数})$	地址位数 − 索引 − 块内
全相联	没有索引	$0$	地址位数 − 块内
$n$ 路组相联	组号（主存块号 $mod$ 组数）	${\log }_2(\text{行数}/n)$	地址位数 − 索引 − 块内

$$\text{块内地址位数}={\log }_2(\text{块大小})$$

标记的作用：索引只能定位到"哪一行/哪一组"，但一个行位可以对应很多个主存块（例如 32 位地址下，Cache 只有 64 行时，每个行位对应 $2^{22}$ 个主存块）。所以必须额外存一段标记，与地址里的标记字段比对，才能确认"这一行里装的到底是哪个块"。

缺失的判断：索引定位到候选行 → 比标记 → 标记相等且有效位为 1 才算命中。

三、三种映射方式详解

1. 直接映射（direct mapping）

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

每个主存块只有唯一一个可以放的位置。地址切分：

┌──────────────┬──────────┬────────────┐
│    标记 tag   │ 行号 line │ 块内 offset │
└──────────────┴──────────┴────────────┘

• 优点：硬件最简单，只需 1 个比较器即可判定命中；查找快，不需要替换算法。
• 缺点：冲突缺失严重。若两个块号之差恰是 Cache 行数的整数倍，它们就抢同一个行位，互相淘汰——即使 Cache 里其他地方空着也没用。

2. 全相联（fully associative）

主存的任意一块可以放到任意一行。地址里没有索引字段：

┌───────────────────────┬────────────┐
│        标记 tag        │ 块内 offset │
└───────────────────────┴────────────┘

• 优点：冲突最小、命中率最高，只在 Cache 满时才需要替换。
• 缺点：需要与所有行的标记同时比较（相联存储器 CAM），比较器数量等于行数，硬件昂贵、速度受限。全相联只用在极小容量的场合，如 TLB。

3. $n$ 路组相联（$n$-way set associative）

把行分成若干组，每组 $n$ 行：组间用直接映射，组内用全相联。

$$\text{组号}=\text{主存块号}mod\text{组数},\text{组数}=\frac{\text{总行数}}{n}$$

┌──────────────┬──────────┬────────────┐
│    标记 tag   │ 组号 set │ 块内 offset │
└──────────────┴──────────┴────────────┘

• 一个主存块可以放进指定组内的任意一路，于是冲突被限制在组内。
• 需要 $n$ 个比较器（并行比较 $n$ 路的标记）。
• $n=1$ 时退化为直接映射，$n = $ 总行数时退化为全相联。组相联是两者的连续谱。

三种方式对比：

对比项	直接映射	全相联	$n$ 路组相联
放置位置	唯一	任意	指定组内任意路
索引字段	行号	无	组号
标记比较次数	1	全部行	$n$
命中率	最低	最高	居中（$n$ 越大越高）
硬件成本	最低	最高	居中
需要替换算法	不需要	需要	需要
典型应用	早期 Cache	TLB、小 Cache	现代 Cache 主流

四、替换算法

替换算法只在全相联和组相联中才需要——直接映射的位置唯一，没有可选的余地，这是常考的送分点。

算法	规则	评价
随机（RAND, random）	随机挑一路淘汰	实现最简单，命中率不稳定
先进先出（FIFO, first-in-first-out）	淘汰最早调入的	简单；可能淘汰掉正在反复用的块
最近最少使用（LRU, least recently used）	淘汰最久未被访问的	命中率最高，也最常用；需为每行维护"最近使用"信息
最不经常使用（LFU, least frequently used）	淘汰访问次数最少的	需计数器；对"阶段性热点"不友好

LRU 的硬件实现：$n$ 路组相联需要 ${\log }_{2}n!$ 位状态（$2$ 路只需 1 位，标记"哪路是最近使用的"；4 路需要 $\lceil {\log }_{2}24\rceil =5$ 位）。这正是"路数越多、替换越贵"的原因之一。

五、写策略

Cache 里是副本，写操作就产生两难：改 Cache 还是改主存？

按"写命中"时的行为分：

策略	做法	优点	缺点
写直达（write through）	同时写入 Cache 和主存	二者始终一致，实现简单	每次写都要访存，慢（可用写缓冲缓解）
写回（write back）	只写 Cache，并置脏位（dirty bit）；只有该行被替换时才写回主存	大幅减少访存次数	主存可能过时，需要脏位与替换时回写逻辑

按"写缺失"时的行为分：

策略	做法
写分配（write allocate）	先把该块调入 Cache，再在 Cache 里写（"先搬来再改"）
非写分配（no-write allocate）	不调入，直接写到主存（"改主存就行"）

常用搭配（记这两组）：

• 写回 + 写分配：写缺失时调入，之后在该块上的多次写都只改 Cache，直到替换才回写。适合本块会被反复写的场合。
• 写直达 + 非写分配：写缺失时直接写主存，反正每次都写主存，调入 Cache 没意义。

六、命中率与平均访问时间

$$H=\frac{\text{命中次数}}{\text{总访问次数}},M=1-H$$

两种口径（与第 10 篇同源）：

$$\text{口径 A（同时访问）：}{T}_a=H{T}_c+(1-H)T_m$$$$\text{口径 B（逐级访问）：}{T}_a=T_c+(1-H)T_m$$

七、Cache 的"总位数"要算哪些位

题目问"Cache 总容量是多少位"时，不能只算数据位。每一行除了数据块，还要存：

$$\text{每行位数}=\underset{\text{数据位}}{\underbrace{\text{块大小}\times 8}}+\underset{\text{tag}}{\underbrace{\text{标记位数}}}+\underset{\text{有效位}}{\underbrace{1}}+\underset{\text{脏位（仅写回）}}{\underbrace{1}}+\underset{\text{LRU 等}}{\underbrace{\text{替换状态位}}}$$$$\text{Cache 总位数}=\text{行数}\times \text{每行位数}$$

有效位（valid bit）必须有：刚上电时 Cache 里是随机值，没有这个位就无法区分"这行装的是数据"还是"这行是垃圾"。

示例

例 1：直接映射的地址划分

主存地址 32 位，Cache 有 64 行，块大小 16 B，采用直接映射。求地址各字段的位数。

完整计算过程：

第一步，块内地址位数（由块大小决定）：

$${\log }_{2}16=4\text{位}$$

整块 16 B 需要 4 位二进制来编号。

第二步，行号位数（由 Cache 行数决定）：

$${\log }_{2}64=6\text{位}$$

第三步，标记位数（剩下的全归标记）：

$$32-4-6=22\text{位}$$

地址切分结果：

字段	位数	位置
标记	22	$A_{31}\sim A_{10}$
行号	6	$A_9\sim A_4$
块内地址	4	$A_3\sim A_0$

验证一下这个划分的含义：行号 6 位能区分 64 行 ✓；22 位标记意味着每个行位对应 $2^{22}$ 个不同的主存块，它们互相冲突——这就是直接映射冲突缺失的来源。

顺带得出主存容量：$2^{32}$ B = 4 GB（按字节编址）。

例 2：组相联的地址划分

Cache 数据容量 64 KB，块大小 32 B，采用 2 路组相联，主存地址 32 位。求行数、组数、各字段位数与比较器个数。

完整计算过程：

第一步，求总行数：

$$\text{行数}=\frac{\text{Cache 数据容量}}{\text{块大小}}=\frac{64\times 1024}{32}=2048\text{行}$$

第二步，求组数：

$$\text{组数}=\frac{\text{行数}}{n}=\frac{2048}{2}=1024\text{组}$$

第三步，求组号位数：

$${\log }_{2}1024=10\text{位}$$

第四步，求块内地址位数：

$${\log }_{2}32=5\text{位}$$

第五步，求标记位数：

$$32-10-5=17\text{位}$$

第六步，求比较器个数：组内 $n$ 路并行比较标记，所以

$$n=2\text{个比较器}$$

结论汇总：

项	值
行数	2048
组数	1024
标记	17 位
组号	10 位
块内地址	5 位
比较器	2 个

对照体会：同样的 64 KB，如果改成直接映射，标记位会变成 $32-11-5=16$ 位（因为行数 2048 → 行号 11 位），标记更短、硬件更省，但冲突更多。从直接映射到组相联，本质上是用"更长的标记 + 更多比较器"换"更少的冲突"。

例 3：Cache 的总位数（含标记与状态位）

用例 2 的配置（64 KB 数据、32 B 块、2 路组相联、32 位地址），写回法 + LRU 替换。求 Cache 的总位数。

完整计算过程：

第一步，算数据位：

$$64\text{KB}=65536\text{B}=65536\times 8=524288\text{位}$$

第二步，算每行的额外位：

项	位数	说明
标记	17	例 2 已算
有效位	1	判断该行是否已装入有效数据
脏位	1	写回法必需
LRU 状态位	1	2 路只需 1 位
合计	20

第三步，算额外位总量（行数 2048）：

$$2048\times 20=40960\text{位}$$

第四步，求总位数：

$$524288+40960=565248\text{位}=70656\text{B}=69\text{KB}$$

结论：Cache 实际占用 $565248$ 位（约 $69$ KB），其中数据位占 $524288$ 位，为总数的 $92.75\mathrm{\%}$；额外开销 $40960$ 位，占 $7.25\mathrm{\%}$。

考点提醒：题目若只问"数据容量"就答 64 KB，若问"总容量"就必须把标记和状态位算进去。看清"数据容量"还是"总容量"这四个字。

例 4：命中率与平均访问时间

Cache 存取时间 1 个时钟周期，主存存取时间 100 个周期。分别求 $H=90\mathrm{\%}$、$95\mathrm{\%}$、$98\mathrm{\%}$ 下两种口径的平均访问时间。

完整计算过程：

第一步，明确参数：$T_c=1$，$T_m=100$（单位：时钟周期）。

第二步，逐一代入两种口径：

口径 A（同时访问）$T_a=H\times 1+(1-H)\times 100$：

$$H=0.90:0.9\times 1+0.1\times 100=0.9+10=10.90$$$$H=0.95:0.95\times 1+0.05\times 100=0.95+5=5.95$$$$H=0.98:0.98\times 1+0.02\times 100=0.98+2=2.98$$

口径 B（逐级访问）$T_a=1+(1-H)\times 100$：

$$H=0.90:1+10=11.00$$$$H=0.95:1+5=6.00$$$$H=0.98:1+2=3.00$$

汇总表：

命中率 $H$	未命中率	口径 A	口径 B
90%	10%	10.90 周期	11.00 周期
95%	5%	5.95 周期	6.00 周期
98%	2%	2.98 周期	3.00 周期

结论与解读：

• 命中率从 90% 提到 98%，平均访问时间从 10.9 降到 2.98 周期，提速 3.66 倍。
• 两种口径的差值是 $(1-H)\times 0$ 到 $(1-H)$ 之间——本质差别只在"未命中时是否还要额外算一次 Cache 访问"。$H$ 很高时两种口径几乎一样；$H$ 低时差别才明显。
• 平均值被未命中的尾巴主导：$H=90\mathrm{\%}$ 时，那 10% 的未命中贡献了 $10$ 个周期，占总时间的 $91.7\mathrm{\%}$。

例 5：LRU 替换过程（组相联）

Cache 为 4 组 × 2 路（共 8 行），块大小 1 个字，采用 LRU 替换。主存块号访问序列为 0, 1, 4, 2, 0, 1, 4, 8 求每次访问的命中情况与总命中率。

完整计算过程：

第一步，确定映射关系。块号 $b$ 映射到组 $bmod4$：

块号	0	1	2	4	8
组号	0	1	2	0	0

第二步，逐次模拟（组内容按"旧 → 新"排列，队尾是最近使用）：

序	访问块	组号	组内内容（旧→新）	结果	说明
1	0	0	[0]	缺失	组 0 空，直接装入
2	1	1	[1]	缺失	组 1 空，直接装入
3	4	0	[0, 4]	缺失	组 0 还有一路空位，装入第 2 路
4	2	2	[2]	缺失	组 2 空，直接装入
5	0	0	[4, 0]	命中	块 0 在组 0，升为最近使用
6	1	1	[1]	命中	块 1 在组 1
7	4	0	[0, 4]	命中	块 4 在组 0，升为最近使用
8	8	0	[4, 8]	缺失	组 0 已满，淘汰最久未用的块 0

第三步，统计：

$$\text{命中次数}=3,\text{缺失次数}=5,\text{总访问}=8$$$$H=\frac{3}{8}=37.5\mathrm{\%}$$

结论：命中率 $37.5\mathrm{\%}$。

关键观察（第 8 次）：

• 块 8 与块 0、块 4 都映射到组 0（$8mod4=0$），组内只有 2 路，必须淘汰一个。
• 此时组 0 的内容是 [0, 4]（旧→新），即块 0 最久未被使用，所以淘汰块 0。这正是 LRU 的定义。
• 如果换成 FIFO：第 3 次装入 4 时是 [0, 4]，第 5、7 次命中不改变 FIFO 顺序（FIFO 只看"谁先来"），所以第 8 次同样淘汰块 0——本例中 FIFO 与 LRU 结果巧合相同。要构造两者不同的例子，需要让"最早来的块"恰好被反复使用。

例 6：写策略对主存访问次数的影响

某程序对同一个主存块内的地址连续执行 100 次写操作。分别用（写直达 + 非写分配）与（写回 + 写分配）统计主存的访问次数。

完整计算过程：

方案一：写直达 + 非写分配

写缺失时直接写主存，不调入 Cache；写命中时同时写 Cache 和主存。无论命中还是缺失，每次写都要访问主存：

$$\text{主存写次数}=100\text{次},\text{主存读次数}=0$$

方案二：写回 + 写分配

第一步，第 1 次写：缺失 → 写分配先把该块调入 Cache，产生 1 次主存读，然后在 Cache 里写并置脏位。

第二步，第 2 ~ 100 次写：全部命中，只改 Cache、更新脏位，不访问主存：

$$\text{命中后的主存访问}=0$$

第三步，该行最终被替换时，脏位为 1 → 1 次主存写回。

$$\text{主存读}=1,\text{主存写}=1$$

对照表：

方案	主存读	主存写	主存访问合计
写直达 + 非写分配	0	100	100
写回 + 写分配	1	1	2

结论：本例中写回法把主存访问从 $100$ 次降到 $2$ 次，减少 $98\mathrm{\%}$。

为什么写回能省这么多：因为对同一块的反复写在缓存里"攒"起来了——100 次写只付一次回写成本。这正是写回法在现代 CPU 里占据主流的原因。

代价也要看清：

• 主存与 Cache 可能不一致（主存里是旧值）。多核环境下需要额外的一致性协议来解决。
• 需要脏位，且替换时要判断"是否脏"，控制逻辑更复杂。
• 单次写的场景下写回反而更差：要调入（1 次读）+ 回写（1 次写）= 2 次访问，而写直达只要 1 次写。

例 7：两种访问序列的命中率对比（冲突缺失）

Cache 为直接映射、共 8 行、块大小 1 个字。比较两个序列的命中率。

完整计算过程：

序列 A： 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

行号 $=$ 块号 $mod8$，块 0~4 分别落在行 0~4，互不冲突：

序	块	结果	序	块	结果
1	0	缺失	7	0	命中
2	1	缺失	8	1	命中
3	2	缺失	9	2	命中
4	3	缺失	10	3	命中
5	0	命中	11	4	命中
6	1	命中	—	—	—

$$\text{缺失}=5,\text{命中}=7,H_A=\frac{7}{12}\approx 58.33\mathrm{\%}$$

序列 B： 0, 8, 0, 8, 0, 8

块 0 和块 8 的行号都是 $0$（$0mod8=0$，$8mod8=0$）——它们抢同一个行位。Cache 其余 7 行全空，却帮不上忙：

序	块	行号	结果	说明
1	0	0	缺失	装入行 0
2	8	0	缺失	行 0 被块 0 占着，只好把块 0 换出
3	0	0	缺失	又换回块 0
4	8	0	缺失	又换出
5	0	0	缺失	反复
6	8	0	缺失	反复

$$\text{缺失}=6,\text{命中}=0,H_B=0\mathrm{\%}$$

结论：序列 B 的命中率是 $0\mathrm{\%}$——尽管 Cache 有 8 行、而工作集只有 2 个块。

这是"冲突缺失"（conflict miss）的教科书级例子：Cache 容量完全够用，但映射方式把两个块钉在了同一个行位上。解决办法是把 Cache 改成组相联或全相联：改成 2 路组相联（8 行 → 4 组）后，块 0 与块 8 都落在组 0，但组内有 2 路可以共存，序列变成"缺、缺、中、中、中、中"——命中率立刻从 $0\mathrm{\%}$ 升到

$$\frac{4}{6}\approx 66.67\mathrm{\%}$$

剩下的 2 次是强制缺失（两个块各自的第一次访问），无法消除。

例 8：C 代码——模拟直接映射 Cache 的命中计数

本机不提供代码运行能力，runnable 标记仅为将来接入运行件预留；请自行在本地编译验证。

#include <stdio.h>

#define NLINE 8          /* Cache 行数 */

/* 直接映射：行号 = 块号 % NLINE，标记 = 块号 / NLINE */
static int simulate(const int *seq, int n, int verbose) {
    int tag[NLINE], valid[NLINE];
    for (int i = 0; i < NLINE; i++) { tag[i] = -1; valid[i] = 0; }
    int hit = 0;

    for (int k = 0; k < n; k++) {
        int b = seq[k];
        int line = b % NLINE, tg = b / NLINE;
        int h = (valid[line] && tag[line] == tg);
        if (h) {
            hit++;
        } else {
            valid[line] = 1;
            tag[line] = tg;        /* 直接映射无需替换算法：位置唯一 */
        }
        if (verbose)
            printf("  访问块 %2d -> 行 %d : %s\n", b, line, h ? "命中" : "缺失");
    }
    return hit;
}

int main(void) {
    int seqA[] = {0,1,2,3,0,1,4,0,1,2,3,4};
    int seqB[] = {0,8,0,8,0,8};
    int nA = sizeof seqA / sizeof seqA[0];
    int nB = sizeof seqB / sizeof seqB[0];

    printf("序列 A:\n");
    int hA = simulate(seqA, nA, 0);
    printf("  缺失 %d / %d, 命中率 %.2f%%\n", nA - hA, nA, 100.0 * hA / nA);

    printf("序列 B:\n");
    int hB = simulate(seqB, nB, 1);
    printf("  缺失 %d / %d, 命中率 %.2f%%\n", nB - hB, nB, 100.0 * hB / nB);

    printf("\n提示: 序列 B 的块 0 与块 8 都映射到行 0, 容量够但冲突缺失 -> 命中率 0%%\n");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

序列 A:
  缺失 5 / 12, 命中率 58.33%
序列 B:
  访问块  0 -> 行 0 : 缺失
  访问块  8 -> 行 0 : 缺失
  访问块  0 -> 行 0 : 缺失
  访问块  8 -> 行 0 : 缺失
  访问块  0 -> 行 0 : 缺失
  访问块  8 -> 行 0 : 缺失
  缺失 6 / 6, 命中率 0.00%

与例 7 的手算完全一致。

例 9：Python 对照——LRU 与地址划分

# ---- 例 5：4 组 x 2 路，LRU ----
def lru_sim(seq, nsets=4, ways=2):
    sets = [[] for _ in range(nsets)]      # 队尾 = 最近使用（MRU）
    hit = 0
    for b in seq:
        s = b % nsets
        if b in sets[s]:
            hit += 1
            sets[s].remove(b)
            sets[s].append(b)              # 升为 MRU
            res = '命中'
        else:
            if len(sets[s]) == ways:
                victim = sets[s].pop(0)    # 队首 = 最久未用（LRU）
                print('  访问块 %d -> 组 %d 缺失，淘汰块 %d，组内容%s -> %s'
                      % (b, s, victim, sets[s] + [victim], sets[s] + [b]))
            sets[s].append(b)
            res = '缺失'
        if res == '缺失':
            print('  访问块 %d -> 组 %d : 缺失, 组内容(旧->新) = %s' % (b, s, sets[s]))
    return hit, len(seq)

seq = [0, 1, 4, 2, 0, 1, 4, 8]
h, n = lru_sim(seq)
print('LRU: 命中 %d / %d -> 命中率 %.1f%%' % (h, n, h / n * 100))

# ---- 例 2：地址划分 ----
import math
cap, bs, ways, A = 64 * 1024, 32, 2, 32
lines = cap // bs
sets = lines // ways
print('行数 %d, 组数 %d, 组号 %d 位, 块内 %d 位, 标记 %d 位'
      % (lines, sets, int(math.log2(sets)), int(math.log2(bs)),
         A - int(math.log2(sets)) - int(math.log2(bs))))

# ---- 例 3：总位数 ----
extra = 17 + 1 + 1 + 1
print('数据位 %d + 额外 %d x %d = %d 位 = %d KB'
      % (cap * 8, extra, lines, cap * 8 + extra * lines,
         (cap * 8 + extra * lines) // 8 // 1024))

输出对照：LRU 命中 $3/8=37.5\mathrm{\%}$、组数 $1024$、标记 $17$ 位、总位数 $565248$ 位（$69$ KB），与例 2、例 3、例 5 一致。

考点

考点

1. 必背公式

• 块内地址位数 $={\log }_2(\text{块大小})$
• 直接映射：行号位数 $={\log }_2(\text{行数})$；标记 $=$ 地址位 $-$ 行号位 $-$ 块内位
• 组相联：组数 $=$ 行数 $/n$，组号位数 $={\log }_2(\text{组数})$，比较器 $=n$ 个
• 全相联：无索引，标记 $=$ 地址位 $-$ 块内位
• $T_a=H{T}_c+(1-H)T_m$ ／ $T_a=T_c+(1-H)T_m$
• Cache 总位数 $=\text{行数}\times (\text{块大小}\times 8+\text{标记}+\text{有效位}+\text{脏位}+\text{替换位})$

2. 高频陷阱

• 直接映射不需要替换算法。位置唯一，没得选。题目问"哪种映射需要 LRU"时不能选直接映射。
• "数据容量"≠"总容量"。数据容量只算块本身；总容量必须加标记位和状态位。例 3 里差了 $5$ KB。
• 组数 $=$ 行数 ÷ 路数，不是 ÷ 块数。别把"块大小"扯进来。
• 全相联也需要替换算法（Cache 满了才替换），但它没有索引字段——这两条常被混着考。
• $n$ 路组相联的比较器个数是 $n$（并行比较 $n$ 路），不是总行数。
• 有效位不能省。没有它无法区分"空行"与"装着数据但标记恰好匹配的行"。
• 写策略要组合着看：题目要写清是"写直达+非写分配"还是"写回+写分配"。只答"写回"是不完整的。
• 写回法替换时判断脏位：脏位为 0 直接丢弃，为 1 才写回主存。算访存次数时别漏了这一步。
• 命中率低不等于容量不够。例 7 的序列 B 是冲突缺失——容量绰绰有余，是映射方式的问题。
• 两种平均访问时间口径别混，与第 10 篇同源。看清"同时访问"还是"逐级访问"。
• 块大小不是越大越好：块太小 → 每次传送的有效数据少、缺失频繁；块太大 → 把用不上的数据搬进来，且行数减少导致冲突加剧。存在最优值。

3. 解题模板（"给配置求地址划分"）

① 行数 = Cache 数据容量 / 块大小
② 组数 = 行数 / 路数            ← 直接映射时路数 = 1，组数 = 行数
③ 块内位 = log2(块大小)
④ 索引位 = log2(组数)           ← 直接映射即"行号位"
⑤ 标记位 = 总地址位 - 索引位 - 块内位
⑥ 比较器 = 路数

4. 三种缺失的名称要认识

缺失类型	原因	对策
强制缺失（compulsory）	该块第一次被访问	无法避免
容量缺失（capacity）	Cache 太小，装不下工作集	加大容量
冲突缺失（conflict）	多个块争抢同一行位/组	提高相联度（例 7 序列 B）

5. 与后续章节的接口

• 第 13 篇虚拟存储器会把"直接映射/全相联"的思路搬到页表上：全相联页表 + TLB。
• 例 3 的"标记位可长达 22 位"直接影响第 11 篇主存储器里 Cache 芯片的选型。
• 与操作系统交叉命题：Cache 一致性是多核 OS 调度的前提；Cache 与虚拟地址的配合（VIPT/PIPT）是体系结构进阶内容。

小结

• Cache 是主存的副本，靠局部性工作，对程序员透明。
• 三种映射方式的本质区别在索引字段：直接映射是"行号"、全相联"没有索引"、组相联是"组号"。地址位 $=$ 标记 $+$ 索引 $+$ 块内。
• 直接映射简单但冲突多，全相联命中率高但硬件贵，组相联是主流折中；直接映射不需要替换算法。
• 替换算法里 LRU 命中率最高；写策略要成对记：写回 + 写分配、写直达 + 非写分配。
• Cache 总位数必须算上标记位、有效位、脏位、替换位——"数据容量"和"总容量"是两个数。
• 例 7 要记住：Cache 有 8 行、工作集只有 2 个块，命中率照样可以是 0%——这就是冲突缺失。

下一篇：虚拟存储器