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.
- L. A. Belady, R. A. Nelson, and G. S. Shedler, "An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine", Communication of the ACM, Vol. 12, June 1969, pp. 349-353.]] Google ScholarDigital Library
- E. G. Coffman and P. J. Denning, "Operating Systems Theory", Prentice-Hall, 1973]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- J. Choi, S. H. Noh, S. L. Min, and Y. Cho, "Towards Application/File-Level Characterization of Block References: A Case for Fine-Grained Buffer Management", Proceedings of 2000 ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems, June 2000, pp. 286-295.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- P. J. Denning, "The Working Set Model for Program Behavior", Communications of the ACM, Vol. 11, No. 5, May, 1968, pp. 323-333.]] Google ScholarDigital Library
- P. J. Denning, "Virtual Memory", Computer Survey Vol. 2, No. 3, 1970, pp. 153-189.]] Google ScholarDigital Library
- W. Effelsberg and T. Haerder, "Principles of Database Buffer Management", ACM Transaction on Database Systems, Dec, 1984, pp. 560-595.]] Google ScholarDigital Library
- G. Glass and P. Cao, "Adaptive Page Replacement Based on Memory Reference Behavior", Proceedings of 1997 ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems, May 1997, pp. 115-126.]] Google ScholarDigital Library
- T. Johnson and D. Shasha, "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm", Proceedings of the 20th International Conference on VLDB, 1994, pp. 439-450.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- D. Lee, J. Choi, J.-H. Kim, S. H. Noh, S. L. Min, Y. Cho and C. S. Kim, "On the Existence of a Spectrum of Policies that Subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) Policies", Proceeding of 1999 ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems, May 1999, pp. 134-143.]] Google ScholarDigital Library
- T. C. Mowry, A. K. Demke and O. Krieger, "Automatic Compiler-Inserted I/O Prefetching for Out-of-Core Application", Proceedings of the Second USENIX Symposium on Operating Systems Design and Implementation, 1993, pp. 297-306.]] Google ScholarDigital Library
- E. J. O'Neil, P. E. O'Neil, and G. Weikum, "The LRU-K Page Replacement Algorithm for Database Disk Buffering", Proceedings of the 1993 ACM SIGMOD Conference, 1993, pp. 297-306.]] Google ScholarDigital Library
- V. Phalke and B. Gopinath, "An Inter-Reference Gap Model for Temporal Locality in Program Behavior", Proceeding of 1995 ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems, 1995, pp. 291-300.]] Google ScholarDigital Library
- R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky and J. Zelenka, "Informed Prefetching and Caching", Proceedings of the 15th Symposium on Operating System Principles, 1995, pp. 79-95.]] Google ScholarDigital Library
- J. T. Robinson and M. V. Devarakonda, "Data Cache Management Using Frequency-Based Replacement", Proceeding of 1990 ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems, May 1990, pp. 134-142.]] Google ScholarDigital Library
- Y. Smaragdakis, S. Kaplan, and P. Wilson, "EELRU: Simple and Effective Adaptive Page Replacement", Proceedings of 1999 ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems, May 1999, pp. 122-133.]] Google ScholarDigital Library
- J. R. Spirn, "Distance String Models for Program Behavior", IEEE Computer, Vol. 9, 1976, pp.14-20.]]Google ScholarDigital Library
- LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance
Recommendations
LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance
Measurement and modeling of computer systemsAlthough 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 ...
LIRS-WSR: integration of LIRS and writes sequence reordering for flash memory
ICCSA'07: Proceedings of the 2007 international conference on Computational science and its applications - Volume Part IMost of the mobile devices are equipped with NAND flash memories even if it has characteristics of not-in-place update and asymmetric I/O latencies among read, write, and erase operations: a write/erase operation is much slower than a read operation in ...
An LIRS-Based Replica Replacement Strategy for Data-Intensive Applications
TRUSTCOM '11: Proceedings of the 2011IEEE 10th International Conference on Trust, Security and Privacy in Computing and CommunicationsData Replication, creating identical copies of data on different sites geographically, is one of the effective optimization techniques for reducing data access costs and improving load balance among sites in data-intensive computing. However, due to the ...
Comments