基于顺序检测的双队列缓存替换算法

摘要：

缓存技术是提高存储性能最有效的技术之一,在存储系统中得到了广泛应用.由于缓存容量有限,替换算法在缓存策略中占据了重要地位.当前,缓存替换算法的研究工作主要集中在如何提高缓存系统命中率,忽略了通过降低缓存失效开销来提高缓存系统性能方面的研究.针对这一问题,本文提出了一种基于顺序检测的双队列缓存替换算法:本算法优先淘汰缓存中的顺序页面,保留随机页面,从而大大减少后续请求对磁盘进行随机访问的次数,能够显著降低缓存系统的失效开销.同时,本算法使用两个队列分别维护新加入页面和待淘汰页面,遵循时间局部性原理,保证了缓存命中率.实验结果表明,本算法在多种缓存大小及工作负载下,可以达到比LRU和ARC算法更优的性能.

关键词：缓存技术、替换策略、命中率、失效开销、顺序检测

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金;新世纪优秀人才支持计划;国家高技术研究发展计划（863计划）

在线出版日期：2012-01-16（万方平台首次上网日期，不代表论文的发表时间）

页码：429-439