LIRS 缓存替换算法

Question

LIRS (Low Inter-reference Recency Set)是一个页替换算法，相比于LRU(Least Recently Used)和很多其他的替换算法，LIRS具有较高的性能。这是通过使用两次访问同一页之间的距离（本距离指中间被访问了多少非重复块）作为一种尺度去动态地将访问页排序，从而去做一个替换的选择。这个算法由宋江和张晓东实现。

量化局部性

所有的页替换算法的工作都依赖于现存局部性原理，各种替换算法的主要不同在于如何量化局部性。LIRS使用同一个页两次被访问的距离，也即是页的连续两次访问之间，有多少非重复的页被访问去量化局部性。

特别地，LIRS使用最后一次和倒数第二次访问该页来实现这一目的。如果一个页首次被访问，则其reuse distance是无穷大，与此同时，LIRS算法还使用一个页的新近访问时间去量化这种局部性。

（新近访问时间：从该页最近一次访问的时刻到此时，访问过的其他非重复页的数量）。为了将最新的访问历史信息考虑进去，LIRS算法的实现使用再访问间隔和页的新近访问时间的较大值去度量这种局部性，使用RD-R表示（Reuse Distance—Recency）。

再访问间隔和新近访问时间的概念如下图所示：

其中：

• T1为该页的倒数第二次访问时刻
• T2为该页的上一次访问时刻
• T3为此时时刻

选择替换页

LIRS管理缓存页和非缓存页的元数据信息，结合下图，可以描述其替换操作：

1、缓存块被分为LIR和HIR两部分。LIR部分用于存储最经常被访问的一些页面（LIR页面），HIR部分用于存储HIR页面

2、LIR部分存储了缓存的大部分页面，所有的LIR页面都是常驻缓存的

3、所有最近被访问的页面被放置于栈S，所有的常驻HIR页面被放 置于栈Q（有可以实现为队列Q）

4、当栈S中的一个页面被访问时，其就会被移至栈S的顶部，同时要确保栈S的尾部是一个LIR块，（这就会进行“栈剪枝”操作）在图（a）的情况下，页面B被访问，就会得到图（b）

5、当栈S中的的一个HIR页面被访问时，该HIR页面就会转变为LIR页面，相应的栈S底部的LIR页面会转变为HIR页面，并移至栈Q的顶部，在图（a）的情况下，页面E被访问，就会得到图（c）

6、当栈S和栈Q中的页面都不命中时，就得考虑常驻页面的替换， 首先被替换出去的是处于栈Q底部的常驻HIR页面。在图（a）的情况下，页面D被访问，就会得到图（d）；在图（a）的情况下，页面C被访问，就会得到图（e）

我们在LIRS栈S上定义一种操作，“栈剪枝”，即移除栈底的所有的HIR块直到遇到一个LIR块。

这个操作有两个目的：

1、确保栈底的一定是个LIR块

2、当栈底的LIR块被移除后，它上面的HIR块一直到下一个LIR块是没有机会变为LIR块的，因为他们的recency要大于LIR块最大的recency。

栈 S 中保存了三种块，栈Q中保存了所有的驻留在cache中的HIR块。但是没有表示不在cache中又不在S中的HIR块。

总结

对于以上保存、没保存的所有块，存在三种访问情况：

1、访问一个LIR块X：这次访问一定命中，简单的将这个块移动栈顶，如果这个LIR块以前是在栈底，那么就需要一次“栈剪枝”操作。

2、访问一个驻留在cache中的HIR块X：这次访问也会命中，然后将它移动到栈顶。然后分两种情况：如果X原本在S中，需要将他的状态改为LIR，还需要将其从Q移除。栈底的LIR块状态改为HIR，加入Q的栈顶，最后执行一次“栈剪枝”；如果X不在栈S中，保持它的HIR状态，在Q中把它移动到栈顶(注意Q中是有这个块的)。

3、访问一个非驻留cache中的HIR块X：这次会发生不命中，我们需要将Q栈底的HIR块从cache中替换掉，改变其状态为非驻留态。然后将X读入cache中刚分配的空闲块，并将X移动到S栈顶。下面分两种情况：如果X在栈S中，改变其状态为LIR，移动栈底LIR块到Q的尾部并更改状态为HIR，最后执行“栈剪枝”；如果X不在S中，保持它的状态为HIR然后把它加入到Q的栈顶。