概述
在这里记录了部分看到的简单的缓存替换策略。
并未实践，可能有不严谨或者错误之处。
遍历情况指连续访问大量互不相同的元素。
缓存阻塞指多个元素争抢同一个缓存位置导致大量 miss 的情况。
Belady 算法
理论内最有效的缓存替换策略，但是无法用于实践。
未命中时从缓存中逐出未来最晚使用的元素。
随机算法
未命中时从缓存中随机逐出元素。
基于时间的算法
最后访问时间指元素在该生命周期中最后一次被访问的时间刻。
最早使用（LRU）
未命中时从缓存中逐出最后访问时间最早的元素。
无法有效处理遍历情况。
最晚使用（MRU）
未命中时从缓存中逐出最后访问时间最晚的元素。
为处理遍历情况最优的算法，但无法处理新增工作集的情况，一般不独立使用。
预驱逐 LRU（EELRU）
当工作集小于缓存大小时使用 LRU，当检测到工作集大于缓存大小时提前逐出部分空间以避免缓存阻塞。
双态插入（BIP）
以一定概率随机插入 LRU 或 MRU，以缓解 MRU 无法处理新工作集的情况。
分段 LRU（SLRU）
核心思路是保护那些出现至少两次的元素。
将缓存划分为两部分，保护段和试用段。两个段内均独立使用 LRU 算法。
未命中元素首先加入试用段，若再次 hit 则加入保护段。保护段逐出元素时将元素加入使用段并更新该元素访问时间。
重用间隔预测（RRIP）
对于每个元素记录一个 RRPV 值（Re-Reference Prediction Value，重用预测值）。在元素被新插入时 RRPV 值较高，当一个元素 hit 时 RRPV 被设为 $0$。驱逐时逐出 RRPV 为 $maxRRPV$（RRPV 最大值）的元素，若不存在则增加所有元素的 RRPV 值并重复上述操作直至逐出一个元素。
静态 RRIP（SRRIP）
SRRIP 算法在插入新元素时将他的 RRPV 值设置为 $maxRRPV$。
这对于遍历情况是相当有效的。
双态 RRIP（BRRIP）
SRRIP 算法有可能产生缓存阻塞情况，BRRIP 通过在插入新新元素时以一定概率将 RRPV 值设为 $maxRRPV - 1$ 在一定程度上解决此类问题，但略微降低了在一般情况下的性能。
基于频率的算法
访问频率指元素在生命周期内一共的访问频率。
最少频率（LFU）
未命中时从缓存中逐出访问频率最低的元素。
仅在缓存内保留了高频元素，不适用于一般情况。
基于频率算法（FBR）
根据访问时间将元素划分为 new/middle/old 三个区域，new 区域不对频率进行计数，其他两个区域对频率进行计数。逐出时从 old 区域内逐出 LFU。
混合算法
动态插入算法（DIP）
在 LRU 算法和 BIP 算法中动态切换。
在缓存中划分出两个小区域，一个区域使用 LRU 另一个使用 BIP，通过观察两个区域的命中率决定剩余区域使用哪个算法。
动态 RRIP（DRRIP）
当工作集小于缓存大小时 SRRIP 性能最佳，工作集大于缓存大小时 BRRIP 性能最佳。
在 SRRIP 和 BRRIP 间动态切换，用与 DIP 相同的方法决定使用哪种算法。
预测算法
Hawkeye
对缓存操作进行采样，使用采样点过去的操作和 PC 计数器的情况训练预测器，使其对新插入的元素进行预测，若元素为缓存友好则赋予较低的 RRPV 值，若缓存不友好则赋予较高的 RRPV 值，然后使用 RRIP 算法处理缓存内的元素。
Comments | NOTHING