LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance

ABSTRACT

Although LRU replacement policy has been commonly used in the buffer cache management, it is well known for its inability to cope with access patterns with weak locality. Previous work, such as LRU-K and 2Q, attempts to enhance LRU capacity by making use of additional history information of previous block references other than only the recency information used in LRU. These algorithms greatly increase complexity and/or can not consistently provide performance improvement. Many recently proposed policies, such as UBM and SEQ, improve replacement performance by exploiting access regularities in references. They only address LRU problems on certain specific and well-defined cases such as access patterns like sequences and loops. Motivated by the limits of previous studies, we propose an efficient buffer cache replacement policy, called Low Inter-reference Recency Set (LIRS). LIRS effectively addresses the limits of LRU by using recency to evaluate Inter-Reference Recency (IRR) for making a replacement decision. This is in contrast to what LRU does: directly using recency to predict next reference timing. At the same time, LIRS almost retains the same simple assumption of LRU to predict future access behavior of blocks. Our objectives are to effectively address the limits of LRU for a general purpose, to retain the low overhead merit of LRU, and to outperform those replacement policies relying on the access regularity detections. Conducting simulations with a variety of traces and 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 LRU.

REFERENCES

• 1: L. A. Belady , R. A. Nelson , G. S. Shedler, An anomaly in space-time characteristics of certain programs running in a paging machine, Communications of the ACM, v.12 n.6, p.349-353, June 1969 [doi>10.1145/363011.363155]
• 2: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 3: P. Cao, E. W. Felten and K. Li, "Application-Controlled File Caching Policies", Proceedings of the USENIX Summer 1994 Technical Conference, 1994, pp. 171-182.
• 4: Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Yookun Cho, Towards application/file-level characterization of block references: a case for fine-grained buffer management, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.286-295, June 18-21, 2000, Santa Clara, California, United States
• 5: J. Choi, S. H. Noh, S. L. Min, Y. Cho, "An Implementation Study of a Detection-Based Adaptive Block Replacement Scheme", Proceedings of the 1999 Annual USENIX Technical Conference, 1999, pp. 239-252.
• 6: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 7: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 8: Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984 [doi>10.1145/1994.2022]
• 9: Gideon Glass , Pei Cao, Adaptive page replacement based on memory reference behavior, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.115-126, June 15-18, 1997, Seattle, Washington, United States
• 10: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 11: J. M. Kim, J. Choi, J. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S. Kim "A Low-Overhead, High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping References", Proceedings of the 4th USENIX Symposium on Operating System Design and Implementation, October 2000, pp. 119-134.
• 12: Donghee Lee , Jongmoo Choi , Jong-Hun Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.134-143, May 01-04, 1999, Atlanta, Georgia, United States
• 13: Todd C. Mowry , Angela K. Demke , Orran Krieger, Automatic compiler-inserted I/O prefetching for out-of-core applications, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.3-17, October 29-November 01, 1996, Seattle, Washington, United States
• 14: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 15: Vidyadhar Phalke , Bhaskarpillai Gopinath, An inter-reference gap model for temporal locality in program behavior, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.291-300, May 15-19, 1995, Ottawa, Ontario, Canada
• 16: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 17: John T. Robinson , Murthy V. Devarakonda, Data cache management using frequency-based replacement, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.134-142, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 18: Yannis Smaragdakis , Scott Kaplan , Paul Wilson, EELRU: simple and effective adaptive page replacement, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.122-133, May 01-04, 1999, Atlanta, Georgia, United States
• 19: J. R. Spirn, "Distance String Models for Program Behavior", IEEE Computer, Vol. 9, 1976, pp.14-20.