3.4 Cache 的替换算法、写策略与容量计算
随机、FIFO、LRU、LFU 替换算法，全写法与写回法、写分配与非写分配，多级 Cache，以及 Cache 行结构与总容量的计算。
替换算法
在采用全相联映射或组相联映射方式时，从主存向 Cache 传送一个新块，当 Cache 或 Cache 组中的空间已被占满时，就需要使用替换算法置换 Cache 行。而采用直接映射时，一个给定的主存块只能放到唯一的固定 Cache 行中，所以在对应 Cache 行已有一个主存块的情况下，新的主存块毫无选择地把原先已有的那个主存块替换掉，因而无须考虑替换算法。
| 算法 | 规则 | 特点 |
|---|---|---|
| 随机（RAND） | 随机地确定替换的 Cache 块 | 实现简单，但未依据程序访问的局部性原理，命中率可能较低 |
| 先进先出（FIFO） | 选择最早调入的行进行替换 | 比较容易实现，但也没有依据局部性原理，最早调入的信息可能仍要使用 |
| 近期最少使用（LRU） | 选择近期内长久未访问过的 Cache 行作为替换的行 | 依据局部性原理，平均命中率较高，是堆栈类算法；需要为每行设置计数器 |
| 最不经常使用（LFU） | 将一段时间内被访问次数最少的行换出 | 曾被经常访问的块不一定近期会用到，实际效果并不比 LRU 好 |
动画演示Cache 的映射方式与替换算法
当前访问的组命中缺失 / 被替换
1/28全相联映射：Cache 共 4 行，分为 1 组（每组 4 行）。访问序列给出的是主存块号。替换算法：LRU
在上面的模拟器中，把替换算法在 LRU 与 FIFO 之间切换，并改变相联度，比较命中率的变化。
写策略
因为 Cache 中的内容是主存块副本，当对 Cache 中的内容进行更新时，就需选用写操作策略使 Cache 内容和主存内容保持一致。
写命中时：
- 全写法（写直通法，write-through）：当 CPU 对 Cache 写命中时，必须把数据同时写入 Cache 和主存。这种方法实现简单，能随时保持主存数据的正确性；缺点是增加了访存次数，降低了 Cache 的效率。为减少全写法直接写入主存的时间损耗，在 Cache 和主存之间加一个写缓冲（Write Buffer）；
- 写回法（write-back）：当 CPU 对 Cache 写命中时，只修改 Cache 的内容，而不立即写入主存，只有当此块被换出时才写回主存。这种方法减少了访存次数，但存在不一致的隐患。为此，每个 Cache 行必须设置一个标志位（脏位 / 修改位），以反映此块是否被 CPU 修改过。
写不命中时：
- 写分配法（write-allocate）：把主存中的块调入 Cache，在 Cache 中修改。通常搭配写回法使用；
- 非写分配法（not-write-allocate）：只写入主存，不进行调块。通常与全写法合用。
Cache 的容量计算
Cache 的每一行由控制位 + 标记 + 数据组成：
- 有效位（1 位）：必须有；
- 修改位 / 脏位（1 位）：仅写回法需要；
- 替换控制位：LRU 等算法需要（ 路组相联时 位）；直接映射无须替换控制位；
- 标记位：主存地址位数 − 组号（行号）位数 − 块内地址位数；
- 数据：块大小 × 8 位。
计算器Cache 地址划分与容量计算
Cache 行数 = 16 KB / 64 B = 256 行
组数 = 256 / 4 = 64 组（每组 4 行）
块内地址 = log₂64 = 6 位
组号 = log₂64 = 6 位
Tag = 32 − 6 − 6 = 20 位
控制位 = 有效位 1 + 修改位 1 + LRU 2 = 4 位
每行总位数 = 4 + 20 + 64×8 = 536 位
Cache 总容量 = 536 × 256 = 137,216 位（≈ 16.75 KB）
→ 主存块号 1165，映射到第 13 组
相联度越高，组号位越少、Tag 位越多：全相联映射没有组号字段，地址只划分为 Tag 和块内地址。
例题（408 真题 2011 改编）
某计算机的主存地址空间为 256 MB，按字节编址，数据 Cache 有 8 行（不含其他 Cache），采用直接映射，每行 64 B，采用写回法。问：Cache 的总容量是多少位？
查看解答
主存地址 28 位（ = 256 MB）。块内地址 位，行号 位，标记 位。每行：有效位 1 + 修改位 1 + 标记 19 + 数据 ，共 533 位。总容量 位。
即时练习
即时练习4 题
点击选项即可作答
- 1某计算机主存地址为 32 位，按字节编址，Cache 数据区大小为 32 KB，主存块大小为 32 B，采用直接映射方式，则每个 Cache 行中标记的位数是（ ）。
- 2下列关于 Cache 写策略的论述中，错误的是（ ）。
- 3采用指令 Cache 与数据 Cache 分离的主要目的是（ ）。
- 4某 4 路组相联 Cache 采用 LRU 替换算法，每行至少需要的替换控制位数为（ ）。
学完了吗？
标记完成后，侧栏会显示进度。进度仅保存在本浏览器中。