Cache 中主存块的替换算法

2026 大纲 三（六）3 Cache 中主存块的替换算法。

先问一句：这个 Cache 到底需不需要替换算法

替换算法回答的是"该淘汰谁"，而这个问题只有在有得选的时候才成立。

🔴 直接映射根本不需要替换算法。 一个主存块只能去唯一确定的那一行，那行装着什么就覆盖什么，没有任何决策余地。所以直接映射的 Cache 行里没有 LRU 位——这一点直接影响算总容量的结果，是最常被漏掉的一处。

全相联要在所有行里选，组相联要在组内的 $k$ 行里选。第二句还有个容易忽略的限定：

🔴 组相联的替换范围只在组内。 $k$ 路组相联做决策时考察的是该组内的 $k$ 行，与其他组毫无关系；每组维护各自独立的替换状态，某一组的访问不会影响另一组的淘汰顺序。手工走查时必须按组分栏推，混在一起推必错。

想清楚这两句，本节剩下的内容就是三件事：四种算法各按什么依据淘汰、为什么 LRU 的栈性质能排除 Belady 异常、以及 LRU 具体怎么用计数器实现。

交互可视化

加载可视化中...

一、什么时候才需要替换

当一个新的主存块要调入 Cache，而它能去的位置已经被占满时，就必须淘汰一个旧块。关键在于"它能去的位置"有几个：

映射方式	一个主存块能去的位置	需要替换算法吗
直接映射	唯一确定的一行	不需要——没有选择余地，那一行被占就直接覆盖
全相联	任意一行	需要（在所有行中选）
组相联	确定组内的任意一行	需要（在组内 $k$ 行中选）

二、四种替换算法

算法	淘汰谁	依据是否站得住	命中率	硬件开销	是否栈算法
LRU	最长时间未被访问的块	局部性原理的直接推论：当前最久没用的将来也最不可能被用到，在真实程序上相当准确	最高	中（LRU 位）	是
FIFO	最早装入的块，与访问情况无关	站不住：来得早不等于用得少，被频繁使用的块可能仅因进来得早就被淘汰	低	小（指针）	否
LFU	访问次数最少的块	计数值反映历史总量而非近期活跃度：新块从 0 开始容易被误杀，早期热、近期冷的块反而长期赖着不走	较高	较大（计数器）	否
随机	随机挑一行	—	最低	最小（无状态）	否

LRU 与 LFU 的分歧点在新块：LRU 看最近一次使用是什么时候，LFU 看累计被使用了多少次。一个刚调入的块在 LFU 眼里计数为 0、最该淘汰，在 LRU 眼里刚被访问过、最不该淘汰。

LRU 与 FIFO 的根本差别在命中时做不做事：LRU 命中时也要更新使用记录，FIFO 只在装入那一刻记录一次、命中不改变任何状态。走查题里判错的多半就是漏了这一步——命中之后顺序没更新，接下来淘汰的那一个就选错了。

三、栈算法与 Belady 异常

图 7.33　LRU 替换算法示例（袁春风《计算机组成与系统结构（第 3 版）》p245）

教材这张图对同一个访问序列 $\{1,2,3,4,1,2,5,1,2,3,4,5\}$ 分别给出 3 路、4 路、5 路组相联下 LRU 的替换过程。横向对比可以看出栈性质：小容量情形下的驻留块集合，必然是大容量情形下驻留块集合的子集，于是容量增加时命中次数只增不减。

栈算法的定义就是这条子集性质：任一时刻小容量的驻留块集合恒为大容量驻留块集合的子集，于是小容量下能命中的大容量下一定也命中，容量增加时命中次数只增不减。LRU 是栈算法。

不具备栈性质的算法则可能出现容量增大、命中率反而下降的 Belady 异常。同一个序列走 FIFO：3 个位置缺失 9 次，4 个位置缺失 10 次——位置变多，缺失反而增加了 1 次。根因是 FIFO 淘汰"来得最早的"，而来得早与用得少之间没有必然联系。LRU 因为具有栈性质，从原理上排除了这种可能。

⚠️ OPT 与 Belady 异常不是一回事，别因为名字相近而混淆。 OPT（最优替换，也记作 MIN）是淘汰"将来最长时间不会被用到"的理想算法，需要预知未来、无法实现，只用作衡量其他算法的标尺；Belady 异常则是 FIFO 这类非栈算法的反常现象。两者只是同出一位研究者。

那多出来的一次缺失是怎么发生的：同一序列在 3 个位置与 4 个位置下的 FIFO 逐拍走查（想亲手验证 Belady 异常而不是背结论时展开）

序列 $123412512345$。

3 个位置

访问	1	2	3	4	1	2	5	1	2	3	4	5
结果	缺	缺	缺	缺	缺	缺	缺	中	中	缺	缺	中

缺失 9 次。

4 个位置

访问	1	2	3	4	1	2	5	1	2	3	4	5
结果	缺	缺	缺	缺	中	中	缺	缺	缺	缺	缺	缺

缺失 10 次。位置增多改变了淘汰的时序，恰好使得块 1、2 在刚被换出之后又被访问。

四、颠簸

即使替换算法本身没有缺陷，当程序集中访问的存储区范围超过了 Cache 组的大小时也会出现命中率极低的情况。例如某组只有 3 行，而程序反复按 $1,2,3,4,1,2,3,4,\dots$ 的顺序访问映射到同一组的 4 个块——每次要访问的块恰好都在上一轮刚被淘汰，于是 $H=0$。这称为颠簸（pingpong）或抖动（thrashing）。

这也解释了为什么实际 CPU 要用组相联而非直接映射——直接映射相当于每组只有 1 行，最容易颠簸。

🔴 颠簸不是替换算法的错，换任何算法都救不了。 换成 FIFO、LFU 甚至理想的 OPT，结果完全一样——在 3 个位置上循环容纳 4 个块，从信息论上就不可能。有效的手段只有两个：增大相联度（让组里能装下更多块），或者改变访问模式缩小工作集（比如调整循环嵌套顺序、做分块）。

五、LRU 的硬件实现

LRU 并不是像示意图那样真的搬动块，而是给每个 Cache 行配一个计数器，用计数值记录使用情况，这个计数值称为 LRU 位：

$$\text{LRU 位数}=\lceil {\log }_{2}k\rceil (k\text{为路数})$$

取的是路数的对数而不是路数本身：2 路 1 位、4 路 2 位、8 路 3 位。这个位数要计入 Cache 的总容量，见 Cache 的总容量。

以 $k$ 路组相联为例，计数值越大表示越久未用：

情形	操作
命中	命中行计数器清 0；同组中原计数值小于它的行各加 1；其余不变
未命中，组内有空行	装入空行，计数器清 0；同组其余行加 1
未命中，组已满	替换计数值最大的行，新行计数器清 0，其余行加 1

另一种等价表述是栈（队列）法：维护一个按最近访问顺序排列的队列，命中时把该块移到一端，替换时淘汰另一端。手工推演时更直观。

用队列表示时，"最近使用"放在哪一端并无统一约定，不同资料的画法可能相反。自己推演时先声明一种约定并全程保持一致即可。

一个 2 路组相联的完整逐步模拟：字节地址如何折成块号与组号、两组各自独立的 LRU 状态怎么走（想看清"命中也要更新顺序"这一步的后果时展开）

Cache 共 4 行、2 路组相联、块大小 2 B，按字节编址，初始为空，LRU 替换。依次访问字节地址 0, 4, 8, 2, 0, 6, 8, 4。

第一步，算组数。 $S=\text{行数}/k=4/2=2$ 组。

第二步，把字节地址换算成块号与组号。 替换发生在块的层面，字节地址不能直接使用：

字节地址	0	4	8	2	0	6	8	4
块号 $=\lfloor a/2\rfloor$	0	2	4	1	0	3	4	2
组号 $=$ 块号 $mod2$	0	0	0	1	0	1	0	0

第三步，按组分别模拟。 两组各有独立的 LRU 状态，访问落到哪组只动哪一栏。

约定：下表每组内容按最近使用在左排列，替换时淘汰最右端。

步	地址	块号	落在	组 0	组 1	结果
1	0	0	组 0	[0, –]	[–, –]	缺失
2	4	2	组 0	[2, 0]	[–, –]	缺失
3	8	4	组 0	[4, 2]　淘汰块 0	[–, –]	缺失
4	2	1	组 1	[4, 2]	[1, –]	缺失
5	0	0	组 0	[0, 4]　淘汰块 2	[1, –]	缺失
6	6	3	组 1	[0, 4]	[3, 1]	缺失
7	8	4	组 0	[4, 0]	[3, 1]	命中
8	4	2	组 0	[2, 4]　淘汰块 0	[3, 1]	缺失

$$H=\frac{1}{8}=12.5\mathrm{\%}$$

注意第 7 步：块 4 命中后队列顺序也要更新（[0, 4] 变为 [4, 0]），因此第 8 步淘汰的是块 0 而非块 4。

考点速记

1. 只有全相联和组相联需要替换算法；组相联的替换范围是组内的 $k$ 行、各组状态独立；直接映射没有选择余地，也不需要 LRU 位。
2. LRU 命中率最高且是栈算法（小容量驻留集恒为大容量驻留集的子集），故容量增加命中率不降；FIFO 等非栈算法会出现 Belady 异常，它与理想算法 OPT 是两回事。
3. 颠簸由工作集超过组容量引起、任何算法都救不了，只能增大相联度或改访问模式；LRU 位数 $=\lceil {\log }_{2}k\rceil$ 要计入总容量；LRU 命中时也要更新使用记录，FIFO 不用；淘汰只需把有效位清零。

这一节在真题里被考过的形式（下方「真题练习」里属于本篇的那几道）：

• 给一串字节地址，问组相联 + LRU 下命中几次：四步——① 行数 $÷$ 路数得组数；② 每个字节地址 $÷$ 块大小换成块号（不能拿字节地址直接推）；③ 块号对组数取模定组；④ 按组分栏各自维护 LRU 顺序。⚠️ 命中之后那一栏的顺序也要更新，漏掉这一步后面淘汰谁就选错了。
• 大题里给一串虚页号，问 TLB 里哪一个表项被替换：手法与上一条完全相同，只是把"块号对组数取模"换成"虚页号对 TLB 组数取模"。先筛出被访问超过路数次的那一组，只推那一组即可，其余组根本不会发生替换。答题时必须写出命中那一步的 LRU 顺序演化——它正是替换结果的根因。
• 算 Cache 行位数时的替换位那一项：$\lceil {\log }_{2}k\rceil$ 位，直接映射为 0 位。

易错：拿字节地址直接对组数取模。必须先除以块大小换算成块号。

易错：把各组的 LRU 状态混在一起推。每组独立，落到哪组只动哪一栏。

易错：命中时不更新 LRU 顺序。这是 LRU 与 FIFO 的分界，也是走查题最主要的失分点。

易错：给直接映射的 Cache 行算上替换位。它没有选择余地，不需要。

易错：把 LRU 位数写成路数本身。是 $\lceil {\log }_{2}k\rceil$，8 路是 3 位不是 8 位。

教材出处

• 袁春风《计算机组成与系统结构（第 3 版）》§7.5.4 cache 的替换算法：LRU 算法思想与图 7.33、栈算法的定义、颠簸现象、LRU 位的位数与计数器实现（p245）

相关知识

Cache 的基本原理｜Cache 和主存之间的映射方式｜Cache 写策略

真题练习

相关真题（25题）

2026Q182分2026Q192分2025Q4312分2024Q172分2023Q4314分2022Q162分2021Q162分2021Q448分2020Q152分2020Q4410分2019Q467分2018Q4415分2016Q152分2016Q4513分2015Q152分2015Q162分2014Q162分2013Q162分2013Q439分2012Q172分2011Q4412分2010Q172分2010Q4412分2009Q142分2009Q212分

上一篇Cache 和主存之间的映射方式下一篇Cache 写策略