``Making LRU friendly to weak locality workloads: a novel replacement algorithm to improve buffer cache performance" 

Song Jiang and Xiaodong Zhang 

IEEE Transactions on Computers, Vol. 54, No. 8, 2005, pp. 939-952. 

Abstract

Although the LRU replacement has been widely used in buffer cache management, it is well-known for 
its inability to cope with access patterns with weak locality. Previously proposed algorithm to 
improve LRU greatly increase complexity and/or cannot provide consistently improved performance. 
Some of the algorithm only address LRU problems on certain specific and predefined cases. Motivated by 
the limitations of existing algorithms, we propose a general and efficient replacement algorithm, called
Low Inter-reference Recency Set (LIRS). LIRS effectively addresses the limitations of LRU by using 
recency to evaluate Inter-Reference Recency (IRR) of accessed blocks for making a replacement decision. 
This is contrast to what LRU does: directly using recency to predict the next reference time. Meanwhile, 
LIRS mostly retains the simple assumption adopted by LRU for predicting future block access behaviors.  
Conducting simulations with a variety of traces of difference access patterns and with a wide range of 
cache sizes, we show that LIRS significantly outperforms LRU and outperforms other existing replacement 
algorithms in most cases. Furthermore, we show that the additional cost for implementing LIRS is trivial
in comparison with that of LRU. We also show that the LIRS algorithm can be extended into a familty of 
replacement algorithms, in which LRU is a special member.