文章归档

LIRS缓存

目录索引

参考文献:LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance

LIRS算法主要计算两个参数,IRR和Recency,IRR表示一个页面最近两次被访问访问间隔,Recency表示页面最近一次被访问到现在的访问间隔。IRR越小,表明最近可能经常被访问,Recency越大,表明最近很久没被访问。IRR和Recency的计算方法如下:

这就是LIRS的理论模型,在任何一个时刻,缓存中的每个页面都会有一个IRR值和Recency值。LIRS的核心思想是,如果一个页面当前的IRR越大,将来的IRR会更大。

论文中没有对LIRS的实现作过多的描述,只是简单提到了一个基于Stack的实现方法。

一、替换规则

和LRU不同的是,就是当缓存达到阈值时

  1. 如果是LRU,就会将Recency值最大的那个页面剔除出去,因为这个页面是最近最久没有被访问的
  2. 如果是LIRS,优先剔除IRR值最大的页面,因为IRR越大,说明这个页面过去很少被访问,理所当然认为它在将来可能不会再被访问或者相对其他页面来说最不可能再被访问到。如果有两个页面的IRR相同,则剔除Recency值最大的页面。
显然,LIRS只是一个多了IRR参数的LRU

(待)

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>