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

张恒瑞，王红

（辽宁工程技术大学电子与信息工程学院，葫芦岛 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，最近最少使用算法，从时间局部性着手，如果数据在最近被访问，将来也很有可能访问，基本的思想是建立一个链表，当访问命中时，将节点插入链表头部，当链表达到长度限制时删除链表尾节点。

上述过程在查找访问过程和删除尾节点处复杂度达到了O（n）[1]，链表的好处在于插入删除的复杂度为O（1）,而在访问节点处复杂度高达O（n），访问检索处的复杂度可以通过红黑树或hash表予以优化，而普通的单链表在删除某节点时需要知道上一个节点，当检索到当前节点后，还需从头访问到上一个节点才能删除该节点，同时最后一个节点的删除也需要从头访问，时间复杂度为O（n），故采用双向链表[2]，插入和删除的复杂度都为O（1）。

2.2 具体实现

因为关于Cache替换中内存也占有很大地位，而hash占有较大的空间复杂度，所以运用红黑树作为数据的存储结构，C++的标准库Map实现了红黑树，list实现了双向链表，总的时间复杂度为O（logn），去除Map的定位功能，对链表的插入删除仅需O（1），以下的代码为了精简，使用了map和list的stl库。

2.3 分析

LRU算法实现简单，效率也不错，但面对偶发性的访问数据无力，造成缓存污染严重。假设缓存容量为100，操作序列为1-101循环访问，若采用LRU算法，当访问101时会将1删除，之后每次访问都会将下次访问数据从缓存删除，命中率大大降低。

32 Q算法

3.1 基本原理

2Q算法缓解了LRU对弱空间局限性的无力，在2Q算法里，有两个队列A1和A2[3]，A1为FIFO队列，A2为LRU队列，若数据在A1和A2中都没命中，将数据插入A1队列尾部，若A1满，A1头部出队，当数据在A1命中时，将其删除，并将数据插入A2尾部，A2满时将A2头部出队。

3.2 具体实现

程序中对A1和A2队列采用list双向链表，并采用map进行访问检索，保证插入删除时的复杂度为O（1）,对key先在A2进行map访问检查，若未命中检查A1，若命中执行list删除操作，并将数据插入A2，代表数据入Cache，为hot数据，避免LRU中一次访问就入Cache造成偶发性数据污染缓存，若在A1未命中，将数据以FIFO的形式入A1。

3.3 分析

以上为简化的2Q操作，在简化操作中，A1和A2所占比例是问题的关键，A1比例大时，缓存容量变少，命中率降低，而A1比例小时，找出数据人缓存的时间变长，如何平衡好A1和A2所占比例是问题的关键[4]。如图1所示，比较下LRU和2Q在缓存为3000，200000次随机数测试下的运行效率和命中率可以发现2Q的运行效率明显较好。

仔细看后，发现两种算法的未命中次数都显得很高，原因在于测试选用的是随机数进行的，在随机数模式下，程序的局部性原理便不再起作用，替换算法之间的差距也变小了，如何进行有效果且具有一定的规模的数据测试呢。下面决定采用编写的简易词法分析器对大量程序分析后得到的数据结果作为替换算法的测试数据。运用词法分析器对超过7000行的代码进行分析得到50000余条数据，作为替换算法的输入文件进行运算，在数据范围在1000以内，缓存容量为300得到如图2结果。

图1 LRU和2Q比较结果

图2 三种算法比较结果

结果中可看出最简单的FIFO算法命中次数最差，在实际的情况下多次访问主存会造成时间效率差，相对的LRU和2Q算法命中次数较好，虽然运行时间稍长于FIFO，在较少的访问主存下会使总的时间效率大大提升，在大多实际情况下，LRU算法运行效率尚可，在大量偶发性数据下，可以采用2Q算法予以改进。

[1]海子.LRU Cache.[2014-5-23].http://www.cnblogs.com/dolphin0520/p/3741519.html.

[2]黄贤明.基于LRU改进算法的实时数据库缓存机制[J].工业控制计算机，2015（12）：63-64.

[3]flychao88.缓存淘汰算法-LRU算法.[2013-11-20].http://flychao88.iteye.com/blog/1977653.

[4]Linux Memory.Cache替换算法之：2Q.[2015-5-20].http://www.jianshu.com/p/4f3ca27300c2.

Depth Analysis of LRU and 2Q on Cache Replacement Algorithm

ZHANG Heng-rui，WANG Hong

（School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105）

Cache replacement algorithm is the key to ensure the speed of memory and CPU interaction,the traditional LRU algorithm in dealing with accidental data access caused by cache pollution,but its implementation is simple and the hit rate and efficiency can be used now,in most cases the algorithm,the 2Q algorithm by setting two queue,queue A1 reduces the influence of sporadic data through the temporary storage of data,to achieve the same performance is simple and has good,through the use of lexical analyzer analysis program code to compare the performance of the data algorithm.

Cache Replacement Algorithm;LRU;2Q；Hit Rate;Performance

1007-1423（2017）04-0017-03

10.3969/j.issn.1007-1423.2017.04.014

王红（1979-），女，辽宁庄河人，讲师,硕士研究生，研究方向为计算机系统结构、计算机控制及应用

2016-12-07

2017-01-20

张恒瑞（1996-），男，本科生