Second Change

传统的FIFO和LRU算法都没有使用访问次数这个信息，使得对于空间局限性较弱的场景效率很低，Second Change算法对FIFO算法做了略微的修改，在一定程度上可以改善这种场景下的效率。该算法依然使用队列的方式访问，同时为队列的每一项设置一个参考位：

second change

Hit：将reference bit设置为1

Miss：从Front端查找可以替换的entry

如果Reference bit 为1：清除该位，将数据放入Rear，继续往后查找，到达Rear后依然没有合适的替换位置，回到Front端继续查找。

如果为0，将该entry替换，并将数据放入Rear，清除Reference bit

Clock

Clock算法是针对LRU遍历链表等开销较大的一种改进，将Second Change使用的列表改成环形链表，属于FIFO的复杂度。Clock 不需要从Front移除数据到Rear端，使用Head指针替代了Front和Rear指针。

替换方式和Second Change相似：

Hit：将reference bit设置为1

Miss：从Head开始查找Reference bit为0 的entry

如果Reference bit为1，清除该位，指针前移，直到找到为0的entry为止。

如果Reference bit 为0， 将数据放入该entry，并将Reference bit置1。

clock

LIRS

LIRS算法中使用了IRR（Inter-Reference Recency）和Recency两个参数

IRR：一个页面最近两次的访问间隔

Recency：页面上次访问至今访问了多少其他页。

IRR和Recency参数不包含重复的页数，因为页面的重复计算对当前页面的优先权没有太多影响。如下图所示：

Recency

上图中，页面1的最近一次访问间隔中，有3个不重复的页面：2，3，4，因此IRR为3，最近一次访问到当前时间有两个不重复的页面5和6，因此Recency 为2

在下表中有一个更复杂的访问序列：

访问顺序为{A，D，B，C，B，A，D，A，E}，表格的最右边列出了第10拍时IRR和Recency的值。

以页面D为例，最后一次访问的时间为第七拍，Recency为2；第2~7拍中有3个不同的页面被访问过，因此IRR为3。页面C和E的IRR为infinite，表示在指定的时间间隔内，没有对该页面重复访问。

LIRS算法首先替换IRR最大的页面，其中infinite的值最大，当IRR相同时，替换Recency最大的页面。IRR在一定程度上反应了页面的访问频度，LIRS倾向于认为：一个页面的IRR越大，将来的IRR会变得更大。Recency参数相当于LRU，替换时IRR优先于Recency，这就降低了最后一次访问数据的优先级，因为有些数据虽然最近访问却不一定常用，可能访问过一次之后很久都不再使用，如果Recency优于IRR，这些只使用了一次数据有可能会停留相当长时间。

对于一个随机访问的队列，要在短时间内精确计算出IRR和Recency的值并不容易，实际上很多情况下并不需要获取这两个参数的精确值，有时候知道一个参数就可以了，比如在获取IRR时，只要有一个Infinite，就不需要比较其他结果，如果有多个Infinite，比如C和D，需要进一步比较Recency。

LIRS的实现过程没有精算计算IRR和Recency两个参数，而是给出基于LIRS stack的近似值，根据IRR的不同，将页面分为LIR（Low IRR）和HIR（High IRR）两类，并尽量使得LIR页面更多地再Cache中命中，当发生冲突时，优先替换HIR中的页面。

LIRS Stack中包含一个LRU Stack，Stack的大小固定，由Cache决定，存放cache中有效的页面。淘汰页面时使用LRU算法。算法使用了两个队列：

LIRS Stack S:保存参数Recency不超过其最大值(Rmax)的LIR和HIR，其中HIR可能不在cache中，但依然使用LRU算法，其长度可变，用于判断IRR的大小

LIRS Stack Q:维护cache中的HIR页面，以加快其索引速度，在需要释放页面时，首先淘汰这类。淘汰操作会引起一系列连锁反应，如下图所示：

LIRS

最开始的时候，Stack S中存放着页面{7, 5, 3, 4, 8}，Q中存放这{7， 5}，Stack S中的页面都在Cache中，其中{7, 5}为HIR， {3, 4, 8}为LIR页面。Cache的大小为5，其中两个存放HIR， 3个存放LIR。

Case 1 访问页面9：cache miss（不在Stack S中）的过程：

页面9不在队列中，Cache miss，需要淘汰一个页面：将队列Q前端（front侧）的页面5 淘汰

页面5是之前LIR且在Cache中，被淘汰后继续留在Stack S，状态依旧是LIR

页面9压入Stack S，状态设置为LIR，栈长度+1

Case 2 访问页面5：cache miss（在stack S中）的过程：

新的页面要进入内存，先释放队列Q中的一个页面：将队列Q中的页面7 淘汰

队列S中页面7的状态修改为不在cache中

队列S中的页面8落入到Q中，状态从LIR转换成HIR，Stack S长度-1

页面8仍然在cache中，重新压栈

页面5没有在Cache中，但在队列S中命中，需要将其移出，重新入栈

页面5的状态修改为在Cache中命中

详细的算法细节参考1.

Clock-Pro

Clock-Pro是LIRS思想在Clock算法上的体现，Clock-Pro算法实现开销更小，适用于操作系统的虚拟内存管理，Linux和BSD都是用了该算法；

LIRS适用于I/O存储领域，比如MySQL和Apache Derby，LIRS较完美的解决了弱空间局部性的问题。

参考1. Song Jiang and Xiaodong Zhang [Jun 2002]. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. In Proc. ACM SIGMETRICS Conf., 2002