张恒瑞，王红

（辽宁工程技术大学电子与信息工程学院，葫芦岛 125105）

Cache替换算法LRU和2Q的深度分析

张恒瑞，王红

（辽宁工程技术大学电子与信息工程学院，葫芦岛 125105）

Cache替换算法是内存和CPU交互时速度保证的关键，传统的LRU算法在处理偶然性数据访问时造成缓存污染严重，但其实现简单，命中率和效率尚可，故成为现今大多情况下使用的算法；2Q算法通过设置两个队列，A1队列通过暂存数据减弱偶发性数据的影响，实现同样简单且有不错的性能。通过编制的词法分析器分析程序代码得来的数据进行算法性能的比较。

Cache替换算法；LRU；2Q；命中率；性能

0 引言

Cache作为一种媒介大大提升了CPU和内存的访问速度，为了增加Cache的访问命中率，替换策略的选取大为重要，如今的替换策略大都以程序的局部性原理作为理论基础，分别从时间局部性和空间局部性作为着眼点，阐释不一样的替换算法。LRU作为经典的替换策略，实现简单，但对于特定的数据有很大的缺陷，2Q算法从某种程度上缓解了缓存污染，但是将一个队列变成两个队列势必会影响性能，如何平衡这两者的关系成为重点。

1 问题抽象

将对Cache的操作简化为get和set操作，get（key）表示通过其缓存地址key得到内容value，未命中count++，增加键值对（key，value）表示入缓存，缓存满时按策略删除，set（key，value），若key存在则修改对应缓存中value值，若不存在则增加键值对（key，value）表示入缓存，count，缓存满时按策略删除，可以通过其count值判断其命中情况，运行时间来比较其效率。

2 LRU

2.1 LRU原理

LRU，最近最少使用算法，从时间局部性着手，如果数据在最近被访问，将来也很有可能访问，基本的思想是建立一个链表，当访问命中时，将节点插入链表头部，当链表达到长度限制时删除链表尾节点。……