Cache基本概念与工作原理

考情分析

Cache 是 408 存储系统的核心。命中率公式、平均访问时间计算、映射方式是三大核心出题点。

大纲定位

考纲第三章（六）「高速缓冲存储器（Cache）」第 1 条：Cache 的基本原理。

要求到什么程度：说清 Cache 为什么有用（局部性）、一次访问的完整流程、命中率与平均访问时间怎么算。后三条（映射方式、替换算法、写策略）各有专篇。

CPU 与主存的速度鸿沟

CPU 速度（GHz 级）与主存速度（百 ns 级）之间存在巨大差距。如果 CPU 每次都直接访问主存，绝大多数时间都在等待。Cache 利用程序的局部性，将频繁访问的数据放在 SRAM 中，大幅降低平均访问时间。

局部性原理

时间局部性

刚被访问的数据，近期很可能再次被访问。

例：循环体内的变量、计数器、累加器。

空间局部性

刚被访问的数据，其周围地址的数据近期也很可能被访问。

例：顺序执行的指令、数组的连续元素。

这两种局部性决定了 Cache 的有效性：将刚访问的数据（时间局部性）及其周围的数据块（空间局部性）一并放入 Cache，后续访问大概率命中。

Cache 工作流程

CPU 发出地址
    ↓
查找 Cache（按 tag 比较）
    ↓
命中？
 是 → 从 Cache 读取数据（快）
 否 → 从主存读取数据块，装入 Cache，再向 CPU 提供数据（慢）

流程里的 tag（标记） 是什么：主存比 Cache 大得多，一个 Cache 行在不同时刻可能装过不同的主存块，所以每行必须额外存一份"我现在装的是谁"的身份证——这就是 tag。它取自主存地址的高位段，和数据一起存在 Cache 行里（见下文「数据块（Cache 行）」）。判命中就是拿地址的 tag 段与行里存的 tag 比对。具体怎么切这个字段，见《Cache地址映射》。

Cache 对程序员透明，由硬件自动管理。程序不需要显式操作 Cache。

命中率

H = \frac{N_{c}}{N_{c} + N_{m}}

其中 $N_{c}$ 是 Cache 命中的次数， $N_{m}$ 是未命中（需要访问主存）的次数， $N_{c} + N_{m}$ 为总访问次数。 $H$ 通常在 0.9 以上。缺失率 $M = 1 - H$ 。

真题不直接给次数——要从访问模式推

上面那个公式的前提是题目告诉你 $N_{c}$ 和 $N_{m}$ 。大题里从来不这么给，给的是一段 C 代码或一个数组遍历，要你自己数。推法只有两步：

第一步：一块装几个元素。

n = \frac{块大小}{单个元素大小}

第二步：顺序遍历时，每块只有首次访问缺失，块内其余 $n - 1$ 次都命中。

H = \frac{n - 1}{n} = 1 - \frac{1}{n}

例：块大小 64 B，数组元素是 int（4 B），行优先顺序遍历。

n = 64 \div 4 = 16 \Rightarrow H = \frac{15}{16} = 93.75 %

反面：局部性被破坏时会怎样

只讲"有局部性就快"是不够的，真题同一问里往往紧接着考反面。判据是工作集有没有超出 Cache 的数据容量：

Cache 数据容量 = 行数 \times 块大小

例：Cache 8 行、块 64 B，数据容量 $8 \times 64 = 512$ B。二维数组每行 1024 B，若按列优先访问，每次访问跨过 1024 B——

1024 B > 512 B（Cache 数据容量）

意味着走完一列回来时，先前调入的块早已被后续块反复替换掉，每一次访问都缺失：

H = 0 %

编者注（卷面）：这一问的得分点不是那个 0%，而是根因要说全。只写"跨步大 / 空间局部性差"不到位，要点明「工作集超过 Cache 数据容量 → 反复冲突替换 → 前面调入的块回来时已被换出」。

算命中率的动作清单

先算 $n = $ 块大小 $\div$ 元素大小
判访问步长在不在一块之内——在，走 $H = 1 - 1 / n$
步长跨块时，比较工作集与 Cache 数据容量（ $=$ 行数 $\times$ 块大小）
工作集超容量 → 反复替换 → $H \approx 0$
若语句是"读改写"（如 a[i] = a[i]/x），一个元素访存 2 次（读一次写一次），分母要翻倍

平均访问时间

先访问 Cache，未命中再访问主存

t_{a} = H \cdot t_{c} + (1 - H) \cdot (t_{c} + t_{m})

化简：

t_{a} = t_{c} + (1 - H) \cdot t_{m}

其中 $t_{c}$ 是 Cache 访问时间， $t_{m}$ 是主存访问时间。

同时访问 Cache 和主存（命中则取消主存访问）

t_{a} = H \cdot t_{c} + (1 - H) \cdot t_{m}

两种模型的区别：第一种未命中时，访问 Cache 的时间已经浪费；第二种未命中时，主存访问同时启动，未命中惩罚不包含 Cache 时间。

考场上怎么判该用哪个

题目不一定会明说用哪种模型，得从题面措辞识别：

题面出现	用哪个
「同时访问 / 并行启动 Cache 和主存」「命中则中止主存访问」	模型二 $t_{a} = H t_{c} + (1 - H) t_{m}$
「先访 Cache，未命中再访主存」「未命中后从主存调入」	模型一 $t_{a} = t_{c} + (1 - H) t_{m}$
只给「命中时间」和「缺失损失」两个量	模型一的等价形式： $t_{a} = 命中时间 + 缺失率 \times 缺失损失$

第三行最要紧——真题里 Cache 平均访问时间就是按这个形式给分的，且题干并不声明模型。此时「缺失损失」是相对命中而言的额外开销，一次未命中的总代价是命中时间 $+$ 缺失损失。

编者注（易错）：默认套「同时访问」是常见的失分方式。给了「命中时间 + 缺失损失」就老老实实用 $t_{c} + (1 - H) \times$ 缺失损失，两种模型算出来的数不一样，对不上标答。

效率

e = \frac{t_{c}}{t_{a}}

命中率越高，平均访问时间越接近 Cache 时间，效率越高。

数据块（Cache 行）

Cache 与主存之间以块为单位传输，不是以字节为单位。一个 Cache 行（Cache Line）的数据部分通常 64 字节。

好处：利用空间局部性，一次传输一整块，后续对该块内其他地址的访问直接命中。

一行里不止有数据

这是算容量题的命根子。Cache 行 = 数据 + 标记 + 若干控制位：

[\underset{有 效 位}{\underset{⏟}{V}} \underset{标 记}{\underset{⏟}{Tag}} \underset{数 据 块}{\underset{⏟}{Data}} \underset{脏 位}{\underset{⏟}{(D)}} \underset{替 换 算 法 位}{\underset{⏟}{(\cdot)}}]

字段	作用	什么时候有
有效位 V	标记这一行装没装过有效数据。V=0 时即使 Tag 碰巧匹配也不算命中——防的是上电后的随机残留	总是有
Tag（标记）	存放该行当前装的是哪一个主存块的高位地址，命中判定就是拿它和地址的 tag 段比	总是有
数据块	从主存搬来的那一整块	总是有
脏位 D	该行被写过、与主存不一致	仅回写策略
替换算法位	如 LRU 位， $k$ 路组相联需 $\log_{2} k$ 位	题目提到替换算法时

所以命中判定的完整条件是：有效位 $= 1$ 且 Tag 匹配，两个缺一不可。

而「Cache 总容量」这个说法要看题目口径——问总容量时通常指 $行数 \times (V + Tag + 数据 + \dots)$ ，只答数据区容量是最常见的丢分点。具体算法见《Cache地址映射》。

图 7.26 带 cache 的 CPU 的访存操作过程

图中虚线框内是 cache 缺失处理：从主存取出该块 → 在 cache 中找一个对应的空闲行 → 一边把数据送 CPU、一边把整块复制进 cache。注意"送 CPU"和"装入 cache"是并行的两条支路。

交互可视化

加载可视化中...

例题

例1：平均访问时间计算

Cache 访问时间 $t_{c} = 10$ ns，主存访问时间 $t_{m} = 100$ ns，命中率 $H = 0.95$ 。

同时访问模型：

t_{a} = 0.95 \times 10 + 0.05 \times 100 = 9.5 + 5 = 14.5 ns

先访问 Cache 模型：

t_{a} = 10 + 0.05 \times 100 = 10 + 5 = 15 ns

例2：由命中率反推访问次数

设 CPU 共访问存储器 1000 次，其中访问主存 50 次，则：

N_{c} = 950, N_{m} = 50

H = \frac{950}{1000} = 0.95

考点清单

Cache 利用局部性原理工作，时间局部性和空间局部性都很重要
Cache 由硬件自动管理，对程序员透明
命中率公式： $H = N_{c} / (N_{c} + N_{m})$
平均访问时间（同时访问）： $t_{a} = H \cdot t_{c} + (1 - H) \cdot t_{m}$
平均访问时间（先访 Cache）： $t_{a} = t_{c} + (1 - H) \cdot t_{m}$
Cache 与主存以块为单位传输数据（利用空间局部性）
命中率通常要求在 90% 以上，才能有效提升系统性能
Cache 行 = 有效位 + Tag + 数据（+ 脏位 + 替换算法位），命中 = 有效位为 1 且 Tag 匹配
真题不直接给命中次数：先算一块装几个元素 $n$ ，顺序遍历则 $H = 1 - 1 / n$
工作集超过 Cache 数据容量（行数 × 块大小）→ 反复冲突替换 → $H \approx 0$
题目给「命中时间 + 缺失损失」时用 $t_{a} = t_{c} + (1 - H) \times$ 缺失损失，别默认套同时访问模型

教材出处

袁春风《计算机组成与系统结构（第 3 版）》§7.5 高速缓冲存储器：图 7.26（p236）

Cache基本概念与工作原理

考情分析

大纲定位

CPU 与主存的速度鸿沟

局部性原理

时间局部性

空间局部性

Cache 工作流程

命中率

真题不直接给次数——要从访问模式推

反面：局部性被破坏时会怎样

算命中率的动作清单

平均访问时间

先访问 Cache，未命中再访问主存

同时访问 Cache 和主存（命中则取消主存访问）

考场上怎么判该用哪个

效率

数据块（Cache 行）

一行里不止有数据

交互可视化

例题

例1：平均访问时间计算

例2：由命中率反推访问次数

考点清单

教材出处

真题练习

相关真题（25题）

Cache基本概念与工作原理 ​

考情分析 ​

大纲定位 ​

CPU 与主存的速度鸿沟 ​

局部性原理 ​

时间局部性 ​

空间局部性 ​

Cache 工作流程 ​

命中率 ​

真题不直接给次数——要从访问模式推 ​

反面：局部性被破坏时会怎样 ​

算命中率的动作清单 ​

平均访问时间 ​

先访问 Cache，未命中再访问主存 ​

同时访问 Cache 和主存（命中则取消主存访问） ​

考场上怎么判该用哪个 ​

效率 ​

数据块（Cache 行） ​

一行里不止有数据 ​

交互可视化 ​

例题 ​

例1：平均访问时间计算 ​

例2：由命中率反推访问次数 ​

考点清单 ​

教材出处 ​

真题练习 ​

相关真题（25题）

Cache基本概念与工作原理

考情分析

大纲定位

CPU 与主存的速度鸿沟

局部性原理

时间局部性

空间局部性

Cache 工作流程

命中率

真题不直接给次数——要从访问模式推

反面：局部性被破坏时会怎样

算命中率的动作清单

平均访问时间

先访问 Cache，未命中再访问主存

同时访问 Cache 和主存（命中则取消主存访问）

考场上怎么判该用哪个

效率

数据块（Cache 行）

一行里不止有数据

交互可视化

例题

例1：平均访问时间计算

例2：由命中率反推访问次数

考点清单

教材出处

真题练习