- Cache Replacement Policies - Coarse-Grained Frequency
FREQUENCY-BASED POLICIES
- 基于频率的策略不依赖于最近的访问频率，而是使用访问频率来识别受害者，因此访问频率较高的行优先缓存在访问频率较低的行之上。这种方法不太容易受到扫描的干扰，并且在较长一段时间内考虑重用行为，而不仅仅是最后一次使用。
- 最简单的基于频率的策略是最少频繁使用(LFU)策略[Coffman and Denning, 1973]，它将频率计数器与每条缓存行关联起来。当该行插入缓存时，频率计数器初始化为 0，每次访问该行时，频率计数器都增加。在缓存丢失时，频率最低的候选对象将被逐出。表 3.9 总结了这些操作。
- 不幸的是，基于频率的策略不能很好地适应应用程序阶段中的更改，因为即使不再访问前一阶段中具有高频率计数的行，它们仍然会缓存到新的阶段中。为了解决这个问题，有几个解决方案[Lee等人，2001年，O Neil等人，1993年，Robinson和Devarakonda, 1990年，Shasha和Johnson, 1994] 用最近的信息增加频率信息，让旧的行优雅地老化。这里我们讨论两种这样的解决方案。
Frequency-Based Replacement (FBR)
- FBR [Robinson和Devarakonda, 1990] 指出，基于频率的方法容易受到短时局域性突发的高计数器值的误导。因此，FBR 通过选择性地增加频率计数器从频率计数中剔除局部性。特别是，FBR 不增加 LRU 堆栈的顶部部分的频率计数器，这被称为新部分。因此，时间局部性的短突发不会影响频率计数器。图 3.8 说明了这个策略。
- 不幸的是，这种策略有一个缺点，即一旦新部分的行老化，即使是经常使用的行也会很快被淘汰，因为它们没有足够的时间来建立频率计数。因此，FBR 进一步限制替换在一个旧的部分中使用最少的行，其中包括最近没有被访问的行(LRU堆栈的底部)。堆栈的其余部分称为中间部分，它为经常使用的行提供了足够的时间来建立它们的频率值。
- 表 3.10 总结了 FBR 的操作策略。
Least Recently/FrequentlyUsed (LRFU)
- LRFU 策略 [Lee等人，2001] 建立在这样的观察之上：LRU 和 LFU 策略代表了结合了最近和频率信息的一系列政策的极端点(见图3.9)。LRFU 使用一种名为联合近期和频率(Combined Recency and Frequency, CRF)的新指标，通过允许近期和频率之间的灵活权衡来探索这个频谱。
- 与基于频率的策略一样，LRFU 将每个过去对块的引用计算进去，但与基于频率的策略不同的是，LRFU 通过一个权重函数来衡量每个引用的相对贡献。特别地，LRFU 为每个区块计算 CRF 值，CRF 值是权重函数 F(x) 对每个过去的参考的总和，其中 x 是过去的引用距离当前时间的距离。因此，对于纯粹基于频率的策略仿真，权重函数可以对所有过去的引用给予同等的优先级，而对于基于最近的策略仿真，权重函数可以对最后的引用给予较高的优先级。
- LRFU采用式3.1中的权重函数，其中 是经验选择的参数。权重函数为老的缓存行提供指数级的低优先级，这使得 LRFU 保留了 FBR 的好处，同时支持优雅的老化。$$F(x) = (\frac{1}{p})^{{\lambda}x}$$
- 表 3.11 总结了块 b 在不同决策点上的 LFRU 策略操作。
- LRFU 的性能很大程度上依赖于此，因此随后开发的 ALRFU 策略动态调整了 的值 [Lee et al.， 1999]。
