4. Cache 替换算法：LRU、LFU、随机替换、伪LRU 算法原理与对比

当 Cache 发生缺失（Cache Miss）且当前 Cache 行已被占满时，必须从主存调入新数据块，并选择一个旧块替换出去。这个“选择牺牲块”的策略就是 Cache 替换算法。替换算法的优劣直接影响 Cache 的命中率、硬件开销和功耗。本节深入剖析四种经典替换算法的原理、实现方式与适用场景。

4.1 替换算法全景对比

下表从核心思想、硬件开销、性能特征和典型应用四个维度，对四种算法进行宏观对比：

4.2 LRU（最近最少使用）算法

LRU（Least Recently Used） 基于时间局部性原理：最近被访问过的数据，在不久的将来很可能再次被访问。因此，它选择替换 最长时间未被访问 的 Cache 行。

4.2.1 实现方式

• 全相联 LRU（硬件栈法）： 使用一个硬件栈维护访问顺序。每次命中时，将命中块移到栈顶；缺失时，替换栈底块。
• 组相联 LRU（计数器法）： 每组内为每行维护一个计数器。访问某行时，该行计数器置 0，其余行计数器 +1；替换时选择计数器值最大的行。

// 假设组内有 4 行，计数器 age[0..3]
// 初始所有 age = 0

// 情况1：命中行 i
age[i] = 0;                     // 重置为最新
for (j = 0; j < 4; j++) {
    if (j != i) age[j]++;       // 其他行老化
}

// 情况2：缺失且组已满
victim = argmax(age[0..3]);     // 选择 age 最大的行
替换 victim 行，并设置 age[victim] = 0;

4.2.2 LRU 的优缺点

• 优点： 对时间局部性强的程序命中率极高；行为可预测。
• 缺点： 硬件实现复杂（N 路需要 O(N) 比较器或移位寄存器）；对“扫描”型访问模式（一次性遍历大量数据）表现极差，会污染 Cache。

4.3 LFU（最不经常使用）算法

LFU（Least Frequently Used） 基于频率局部性：访问次数越多的数据，未来被访问的可能性越大。它选择替换 访问计数最小 的 Cache 行。

4.3.1 实现机制

• 每行维护一个计数器，每次命中时计数器 +1。
• 替换时选择计数器值最小的行；若多个行计数相同，通常使用 LRU 或 FIFO 作为辅助策略（称为 LFU-Aging）。
• 关键问题： 计数器可能无限增长，需要定期老化或衰减，否则旧数据会永久占据 Cache。

4.3.2 LFU vs LRU 对比

4.4 随机替换算法

随机替换（Random Replacement） 是最简单的策略：当需要替换时，从组内所有有效行中 随机 选择一个作为牺牲块。

4.4.1 实现与特点

• 实现： 只需一个伪随机数生成器（LFSR 或 Tausworthe），硬件开销极低。
• 优点： 无状态、无计数器、无比较器；抗扫描干扰能力强（不会像 LRU 那样被全遍历污染）。
• 缺点： 命中率通常低于 LRU，尤其在时间局部性强的程序中；行为不可预测，导致实时系统难以分析最坏情况。

4.5 伪LRU（Tree-PLRU）算法

伪LRU（Pseudo-LRU，通常实现为 Tree-PLRU） 是 LRU 的高效近似。它使用一棵二叉树来记录访问顺序，仅需 N-1 位（N 为路数）即可实现接近 LRU 的命中率。

4.5.1 二叉树原理

• 对于 N 路组相联 Cache，构建一棵深度为 log₂(N) 的完全二叉树。
• 每个内部节点有一个方向位（0 或 1），表示“最近访问的块在左子树还是右子树”。
• 每次访问一个块时，从根节点到该块叶子节点的路径上，所有方向位都指向该块所在子树。
• 替换时，从根节点开始，沿着方向位指示的“非最近访问”路径下行，直到叶子节点，该叶子节点即为牺牲块。

4.5.2 伪LRU 的优缺点

• 优点： 硬件开销极低（仅 N-1 位寄存器 + 简单组合逻辑）；命中率非常接近理想 LRU（通常差距 < 2%）。
• 缺点： 并非严格 LRU，在某些特定访问模式下可能做出次优选择；对路数较多的 Cache（如 16 路以上）性能略有下降。

4.6 算法综合对比与选型指南

下表从硬件实现角度给出更详细的对比：

4.6.1 选型建议

• CPU L1 Cache（4~8路）： 优先使用 Tree-PLRU，兼顾性能与面积。
• CPU L2/L3 Cache（8~16路）： 使用 Tree-PLRU 或 改进型 LRU（如 RRIP，Re-Reference Interval Prediction）。
• TLB（全相联或组相联）： 常用 随机替换 或 伪LRU，因为 TLB 缺失代价高但路数少。
• 数据库/Web Cache（大容量、频率分布倾斜）： 使用 LFU-Aging 或 ARC（Adaptive Replacement Cache）。
• 实时/安全系统： 避免使用随机替换，优先选择 LRU 或 伪LRU 以保证行为可预测。