一、主存块的替换算法
需要装入新数据块、但候选范围内没有可用空闲行时，就要选择一个块进行替换。常见算法如下：
| 算法 | 中文名称 | 替换依据 |
|---|---|---|
| Random | 随机替换 | 随机选择一个块 |
| FIFO | 先进先出 | 淘汰最早进入 Cache 的块 |
| LRU | 最近最少使用 | 淘汰最久没有被访问的块 |
| LFU | 最不经常使用 | 淘汰访问次数最少的块 |
1. 随机替换（Random）
核心思想：随机选择一个数据块淘汰。
例如，Cache 中已有 A、B、C，现在要装入 D。若随机选中 B，则替换后保存 A、D、C。
- 优点：实现简单，无需记录访问时间或次数，管理开销小。
- 缺点：不考虑使用情况，可能淘汰经常使用的数据，效果受随机结果影响。
2. 先进先出（FIFO）
核心思想：最早进入 Cache 的块最先被淘汰。 可以理解为排队：先来的人先离开。
假设 A、B、C 依次进入 Cache，装入 D 时淘汰 A，进入顺序变为 B、C、D。
重点： FIFO 只看进入顺序。即使 A 最近被访问过很多次，只要它最早进入，仍然优先淘汰。
- 优点：算法简单，可用队列维护进入顺序，管理开销较低。
- 缺点：不考虑最近使用情况和访问频率，可能淘汰正在频繁使用的块。
3. 最近最少使用（LRU）
核心思想：淘汰最长时间没有被访问的块。 利用时间局部性，优先保留最近使用过的数据。
| 数据块 | 距最近一次访问的时间 |
|---|---|
| A | 10 秒 |
| B | 2 秒 |
| C | 30 秒 |
此时要装入 D，应淘汰 C，因为它最久没有被访问。
重点： 每次访问一个块，都要更新它的最近使用记录；命中时也要更新。
- 优点：符合时间局部性，通常比 FIFO 更符合实际访问规律。
- 缺点：需要维护访问顺序，精确实现有额外的数据结构或硬件开销；对循环扫描等访问模式，效果可能不好。
页置换中的补充结论： FIFO 可能出现 Belady 异常，即增加物理页框数量后，缺页次数反而增加；LRU 不存在这种异常。
4. 最不经常使用（LFU）
核心思想：淘汰访问次数最少的块。
| 数据块 | 访问次数 |
|---|---|
| A | 10 次 |
| B | 3 次 |
| C | 20 次 |
此时要装入 D，应淘汰 B。若多个块的访问次数相同，还需规定进一步的选择规则，例如优先淘汰最久未使用的块。
- 优点：能够保留长期频繁访问的热点数据，适合访问频率较稳定的场景。
- 缺点：需要记录次数；过去的热点可能因历史次数较高而长期占据 Cache，因此还需考虑计数衰减或重置。
重点： LRU 看“最近一次什么时候用”，LFU 看“累计用了多少次”。
二、LRU 排序计数器
LRU 的一种实现方式是：为每个候选 Cache 行设置一个排序计数器（LRU 替换位），记录该行在最近访问顺序中的位置。下面以组相联 Cache 的一组为例。
1. 计数值的含义与位数
- 计数值为 0：最近一次被访问的行。
- 计数值越小：越近被访问。
- 计数值越大：越久没有被访问。
- 需要替换时：淘汰计数值最大的有效行。
若每组有 路，最多需要表示 共 个顺序位置。因此，在这种排序计数器实现中，每行至少需要：
其中， 为相联路数， 为每行计数器的位数， 表示向上取整。
| 相联方式 | 每个 Cache 行的计数器位数 |
|---|---|
| 2 路组相联 | 1 位 |
| 4 路组相联 | 2 位 |
| 8 路组相联 | 3 位 |
| 16 路组相联 | 4 位 |
计数器位数取决于相联路数，并非单纯取决于 Cache 总容量。上述公式针对每行保存顺序位置的实现，不能直接视为所有 LRU 实现的统一存储开销。
2. 命中时的更新规则
设命中行原来的计数值为 ：
- 命中行计数器清零。
- 原计数值小于 的其他有效行加 1。
- 原计数值大于 的行保持不变。
例如，4 路组相联 Cache 的某组原来依次保存 A、B、C、D，计数值分别为 0、1、2、3。现在访问 C：
| Cache 行 | 数据块 | 原计数值 | 更新后 |
|---|---|---|---|
| 0 | A | 0 | 1 |
| 1 | B | 1 | 2 |
| 2 | C | 2 | 0 |
| 3 | D | 3 | 3 |
C 从第三新的块变成最新的块，原本排在它前面的 A、B 后移一位；D 原本就比 C 更旧，顺序位置不变。
3. 未命中时的更新规则
目标组仍有空闲行时：新装入行计数器置 0，其他有效行全部加 1。
例如，原来只有 A、B，访问 C 后：
| Cache 行 | 装入前（数据块／计数值） | 装入后（数据块／计数值） |
|---|---|---|
| 0 | A／0 | A／1 |
| 1 | B／1 | B／2 |
| 2 | 空闲／— | C／0 |
| 3 | 空闲／— | 空闲／— |
目标组没有空闲行时：淘汰计数值最大的行，新装入行计数器置 0，其他有效行全部加 1。
例如，原来保存 A、B、C、D，访问 E 后：
| Cache 行 | 替换前（数据块／计数值） | 替换后（数据块／计数值） |
|---|---|---|
| 0 | A／0 | A／1 |
| 1 | B／1 | B／2 |
| 2 | C／2 | C／3 |
| 3 | D／3 | E／0 |
D 的计数值最大，因此被 E 替换。
4. 更新规则汇总
| 访问情况 | 更新规则 |
|---|---|
| 命中 | 命中行清零；比它原计数值小的有效行加 1；其余不变 |
| 未命中，有空闲行 | 新装入行清零；其他有效行加 1 |
| 未命中，无空闲行 | 淘汰计数值最大的行；新装入行清零；其他有效行加 1 |
三、Cache 的写策略
CPU 修改某个主存地址的数据时，先判断对应数据块是否在 Cache 中：
| 情况 | 含义 | 对应策略 |
|---|---|---|
| 写命中（Write Hit） | 目标数据已在 Cache 中 | 全写法、回写法 |
| 写不命中（Write Miss） | 目标数据不在 Cache 中 | 写分配法、非写分配法 |
1. 写命中：全写法与回写法
假设 Cache 和主存中的 A 都为 10，CPU 执行 A = 20。
全写法（Write Through，也叫直写法）
更新 Cache 的同时，向主存发出对应的写请求。 不使用写缓冲、且写入完成后，Cache 和主存中的 A 都为 20。
- 优点：主存随每次写操作得到更新，控制相对简单。
- 缺点：每次写操作都要更新主存，写入流量较大；可用写缓冲减少等待。
回写法（Write Back）
先只修改 Cache，设置脏位，等脏块被替换时再写回主存。
- 将 Cache 中的 A 改为 20。
- 主存中的 A 暂时仍为 10。
- 将该 Cache 块的脏位（Dirty Bit）置 1。
- 替换该块时，若脏位为 1，先将修改后的数据写回主存。
| 阶段 | Cache 中的 A | 主存中的 A |
|---|---|---|
| 修改后、写回前 | 20 | 10 |
写回完成后，主存中的 A 更新为 20。
- 优点：减少主存写操作，提高执行效率。
- 缺点：Cache 与主存可能暂时不一致，需要脏位管理，控制较复杂。
重点： 脏位为 1，表示该块已被修改、尚未写回，替换时需要写回；脏位为 0，表示没有待写回的修改，替换时无需写回。
2. 写不命中：写分配与非写分配
假设 Cache 中没有 A，主存中 A 为 10，CPU 执行 A = 20。
写分配法（Write Allocate）
先将 A 所在的主存块调入 Cache，再执行写操作。 主存是否随本次写操作更新，取决于采用全写法还是回写法。
例如，采用“写分配法 + 回写法”时：Cache 中 A 为 20，主存中 A 暂时仍为 10，该块脏位为 1。
- 优点：调入后方便后续访问或修改该块。
- 缺点：需要调入整个数据块，增加传输开销。
非写分配法（No Write Allocate）
不将 A 所在的数据块调入 Cache，直接向主存写入。 写入完成后，主存中 A 为 20，Cache 中仍没有 A。
- 优点：无需调入数据块，减少不必要的 Cache 空间占用。
- 缺点：后续访问 A 时，仍可能发生 Cache 未命中。
3. 策略汇总与常见组合
| 策略 | 适用情况 | 核心操作 |
|---|---|---|
| 全写法 | 写命中 | 更新 Cache，并向主存写入 |
| 回写法 | 写命中 | 更新 Cache、设置脏位，脏块替换时写回 |
| 写分配法 | 写不命中 | 先调入 Cache，再执行写操作 |
| 非写分配法 | 写不命中 | 不调入 Cache，直接向主存写入 |
重点： “是否随写操作更新主存”和“写不命中时是否调入 Cache”是两个不同的选择，实际使用时组合起来。
| 常见组合 | 写命中 | 写不命中 | 特点 |
|---|---|---|---|
| 全写法 + 非写分配法 | 更新 Cache，并向主存写入 | 不调入 Cache，直接向主存写入 | 主存随写操作更新，写入流量较大 |
| 回写法 + 写分配法 | 更新 Cache，设置脏位 | 调入 Cache 后修改，设置脏位 | 减少主存写入次数；替换脏块时先写回 |
四、全写法中的写缓冲
1. 作用与写入过程
CPU 和 Cache 的速度远快于主存。若每次全写操作都必须等待主存写入完成，CPU 就可能产生较大的等待开销。
写缓冲（Write Buffer） 用于暂存待写入主存的地址和数据，使 CPU 在缓冲区有空位时，不必等待主存完成本次写入。
加入写缓冲后，写命中的处理过程为：
- CPU 更新 Cache 中的数据。
- 将对应地址与新数据送入写缓冲。
- 若写缓冲有空位，CPU 可以继续执行后续指令。
- 写缓冲中的请求随后写入主存。
例如，执行 A = 20 后，Cache 中 A 已为 20，写缓冲中保存 A 的地址和新值 20，而主存中 A 可能暂时仍为 10。待写入完成，主存中的 A 才变为 20。
重点： 使用写缓冲后，主存可以延迟更新，但仍属于全写法，因为每次写操作都会产生主存写请求；回写法则将修改保留在 Cache 中，主要在脏块被替换时写回。
2. 写缓冲满与读写相关性
写缓冲容量有限，不能保证 CPU 始终无需等待。
例如，缓冲区只能保存 4 条请求。若 CPU 连续发出 5 条写请求，而主存尚未处理前 4 条，则第 5 条请求必须等待缓冲区腾出空间。
| 缓冲区状态 | CPU 的等待情况 |
|---|---|
| 未满 | 通常无需等待本次主存写入完成 |
| 已满（Write Buffer Full） | 可能暂停，等待空位 |
若后续读取的地址对应尚未写入主存的请求，还需检查读写相关性，必要时从写缓冲转发最新数据，避免读取旧值。