不同的工作负载，甚至同一工作负载内的不同阶段，会受益于不同的替换策略

  • 当工作集较小时，会受益于 recency-friendly 策略
  • 而当工作集较大时，会受益于 thrash-resistant 策略

混合策略会评估应用程序当前工作集的需求，并从多个竞争策略中动态选择

两个主要难点是:

  1. 准确识别出最有益的策略
  2. 以较低的硬件成本管理多个策略

Adaptive Replacement Cache (ARC)

ARC 动态平衡基于最近使用和使用频率的 eviction

ARC 会跟踪两个额外的 tag directories，L1 和 L2，它们共同记录的 entry 数量是基准 cache 容量的两倍

  • L1 directory 维护最近使用过但仅被访问过一次的页面
  • L2 directory 维护最近被访问过至少两次的页面

ARC 将基准 cache 目录分为两个列表：T1和T2，分别用于存放最近引用和频繁引用的条目

T1 和 T2 分别扩展了 ghost lists（B1和B2），用于追踪最近从 T1 和 T2 中踢出的 entry

Ghost list

  • ghost list 仅包含 tag 元数据，而不包括实际数据
  • 当相应数据从 cache 中被踢出时，entry 会被添加到 ghost list 中
  • T1 和 B1 共同构成基于 recency 的 L1 directory
  • T2 和 B2 共同构成基于 frequency 的 L2 directory

ARC 的目标是动态选择分配给 L1 和 L2 合适的 cache 容量

  • 在 B1 中的命中会增加 T1 的大小（即分配给最近访问元素的缓存比例）
  • 在 B2 中的命中则会增加 T2 的大小（即分配给至少访问过两次的元素的缓存比例）
  • 从 T1 和 T2 中踢出的 entry 会分别添加到 B1 和 B2 中

缺点：维护额外 tag directory 的开销很大

Set Dueling Policy

机制：以较低硬件成本精确采样不同策略行为

思路：少数随机选择的 set 可以准确代表整个 cache 上不同替换策略的行为

数学上证明，对于具有 1‑4 MB（1024 - 4096 个 sets ）的 cache ，64 个 set 足以捕捉整个 cache 的行为

Dynamic Insertion Policy (DIP, 2007)

通过动态调节新进 cacheline 的插入位置，结合了 recency-friendly 策略和 thrash-resistant 策略的优势

DIP 在 recency-friendly 的 LRU 与 thrash-resistant BIP 之间交替使用

DIP 使用 set dueling 来动态追踪每种策略的 hit rate 以选择合适的替换策略

DIP 将所有 cache sets 分为：

  1. Set Dueling Monitors (SDMs)
    • 少数 sets 专用于 LRU
    • 少数 sets 专用于 BIP
  2. 其余 sets 称为 follower sets

策略选择（PSEL）饱和计数器通过识别 cache hit 更多的 SDM 来确定获胜策略

  • 当专用于 LRU 的 SDM hit 时，PSEL递增
  • 当专用于 BIP 的 SDM hit 时，PSEL递减（一个 k 位 PSEL 计数器初始化为 2^{k−1} ）

获胜策略由 PSEL 的最高有效位（MSB）标识

  • 如果 PSEL 的 MSB 为 0 ，则 follwer sets 使用 LRU 策略
  • 否则，follower sets 使用 BIP

额外硬件开销只有 PSEL

Dynamic Re-Reference Interval Policy (DRRIP)

  • DRRIP 在 DIP 的基础上构建，增加了抗扫描能力
  • DRRIP 使用 set dueling来创建 SRRIP 和 BRRIP 的混合策略