research-article

LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies

Authors:

C. S. KimAuthors Info & Claims

IEEE Transactions on Computers, Volume 50, Issue 12

Pages 1352 - 1361

https://doi.org/10.1109/TC.2001.970573

Published: 01 December 2001 Publication History

Abstract

Efficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full. In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and {\rm O}(\log_2 n) (the time complexity of LFU), where n is the number of blocks in the buffer. Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered.

References

[1]

M.J. Bach, The Design of the UNIX Operating System. Englewood Cliffs, N.J.: Prentice Hall, 1986.]]

Digital Library

[2]

E.G, Coffman Jr. and P.J. Denning, Operating Systems Theory. Englewood Cliffs, N.J.: Prentice Hall, 1973.]]

Digital Library

[3]

P. Cao E.W. Felten and K. Li, “Application-Controlled File Caching Policies,” Proc. Summer 1994 USENIX Conf., pp. 171-182, 1994.]]

Digital Library

[4]

R. Karedla J.S. Love and B.G. Wherry, “Caching Strategies to Improve Disk System Performance,” Computer, vol. 27, no. 3, pp. 38-46, Mar. 1994.]]

Digital Library

[5]

V. Phalke and B. Gopinath, “An Inter-Reference Gap Model for Temporal Locality in Program Behavior,” Proc. 1995 ACM SIGMETRICS/PERFORMANCE Conf., pp. 291-300, 1995.]]

Digital Library

[6]

G. Glass and P. Cao, “Adaptive Page Replacement Based on Memory Reference Behavior,” Proc. 1997 ACM SIGMETRICS Conf., pp. 115-126, 1997.]]

Digital Library

[7]

Y. Smaragdakis S. Kaplan and P. Wilson, “EELRU: Simple and Effective Adaptive Page Replacement,” Proc. 1999 ACM SIGMETRICS Conf., pp. 122-133, 1999.]]

Digital Library

[8]

H. Chon and D. DeWitt, “An Evaluation of Buffer Management for Relational Database Systems,” Proc. 11th Int'l Conf. Very Large Data Bases, 1985.]]

[9]

C. Faloutsos R. Ng and T. Sellis, “Flexible and Adaptable Buffer Management Techniques for Database Management Systems,” IEEE Trans. Computers, vol. 44, no. 4, pp. 546-560, Apr. 1995.]]

Digital Library

[10]

T. Johnson and D. Shasha, “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm,” Proc. 20th Int'l Conf. Very Large Data Bases, pp. 439-450, 1994.]]

Digital Library

[11]

E.J. O'Neil P.E. O'Neil and G. Weikum, “The LRU-K Page Replacement Algorithm For Database Disk Buffering,” Proc. 1993 ACM SIGMOD Conf., pp. 297-306, 1993.]]

Digital Library

[12]

J.T. Robinson and N.V. Devarakonda, “Data Cache Management Using Frequency-Based Replacement,” Proc. 1990 ACM SIGMETRICS Conf., pp. 134-142, 1990.]]

Digital Library

[13]

L.A. Belady, “A Study of Replacement Algorithms for Virtual-Storage Computers,” IBM Systems J., vol. 5, no. 2, pp. 78-101, 1966.]]

Digital Library

[14]

R.L. Mattson J. Gecsei D.R. Slutz and I.L. Traiger, “Evaluation Techniques for Storage Hierarchies,” IBM Systems J., vol. 9, no. 2, pp. 78-117, 1970.]]

Digital Library

[15]

W. Effelsberg and T. Haerder, “Principles of Database Buffer Management,” ACM Trans. Database Systems, vol. 9, no. 4, pp. 560-595, 1984.]]

Digital Library

[16]

J. Choi S.H. Noh S.L. Min and Y. Cho, “An Implementation Study of a Detection-Based Adaptive Block Replacement Scheme,” Proc. 1999 USENIX Conf., pp. 239-252, 1999.]]

Digital Library

[17]

D. Lee J. Choi J.-H. Kim S.H. Noh S.L. Min Y. Cho and C.S. Kim, “LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies,” technical report, School of Computer Science and Eng., Seoul Nat'l Univ., 2001. http://archi.snu.ac.kr/symin/lrfutr.ps.]]

[18]

M.G. Baker J.H. Hartman M.D. Kupfer K.W. Shirriff and J.K. Ousterhout, “Measurements of a Distributed File System,” Proc. 13th ACM Symp. Operating Systems Principles, pp. 198-212, 1991.]]

Digital Library

[19]

J.R. Spirn, Program Behavior: Models and Measurements. North Holland, New York: Elsevier, 1977.]]

Digital Library

[20]

G.S. Gao, “Performance Analysis of Cache Memories,” J. ACM, vol. 25, no. 3, pp. 378-395, 1978.]]

Digital Library

Cited By

Fahmin ACheema MEunus Ali MNadjaran Toosi ALu HLi HTaniar DA. Rakha HShen B(2024)Eco-Friendly Route Planning Algorithms: Taxonomies, Literature Review and Future DirectionsACM Computing Surveys10.1145/3691624Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3691624
Chen DXu WWang HQi YLi RZhou PGuo S(2024)Caching User-Generated Content in Distributed Autonomous Networks via Contextual BanditIEEE Transactions on Mobile Computing10.1109/TMC.2024.334984923:8(8355-8369)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TMC.2024.3349849
Zhu JLi RChen XMao SWu JZhao Z(2024)Semantics-Enhanced Temporal Graph Networks for Content Popularity PredictionIEEE Transactions on Mobile Computing10.1109/TMC.2023.334931523:8(8478-8492)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TMC.2023.3349315
Show More Cited By

Index Terms

LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory

Recommendations

Window-LRFU: a cache replacement policy subsumes the LRU and window-LFU policies

Replacement algorithms have been widely used as key technologies for cache management in areas such as file systems or database management. A replacement algorithm determines which page to be evicted when the cache is full and a new page is referenced. ...
CRFP: A Novel Adaptive Replacement Policy Combined the LRU and LFU Policies
CITWORKSHOPS '08: Proceedings of the 2008 IEEE 8th International Conference on Computer and Information Technology Workshops

A variety of cache replacement algorithms have been proposed and applied in different situations, in which the LRU (Least Recently Used) and LFU (Least Frequently Used) replacement policies are two of the most popular policies. However, most real ...
An Empirical Analysis on Memcached's Replacement Policies
MEMSYS '23: Proceedings of the International Symposium on Memory Systems

The performance of large-scale web services heavily relies on the hit ratio of the key-value caches. One core component of a high-performance key-value cache is the replacement policy. A right replacement policy can help the caching system achieve a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 50, Issue 12

December 2001

103 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © Copyright © 2001 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 2001

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

167
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fahmin ACheema MEunus Ali MNadjaran Toosi ALu HLi HTaniar DA. Rakha HShen B(2024)Eco-Friendly Route Planning Algorithms: Taxonomies, Literature Review and Future DirectionsACM Computing Surveys10.1145/3691624Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3691624
Chen DXu WWang HQi YLi RZhou PGuo S(2024)Caching User-Generated Content in Distributed Autonomous Networks via Contextual BanditIEEE Transactions on Mobile Computing10.1109/TMC.2024.334984923:8(8355-8369)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TMC.2024.3349849
Zhu JLi RChen XMao SWu JZhao Z(2024)Semantics-Enhanced Temporal Graph Networks for Content Popularity PredictionIEEE Transactions on Mobile Computing10.1109/TMC.2023.334931523:8(8478-8492)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TMC.2023.3349315
Zhou YWang FShi ZFeng D(2024)An Efficient Deep Reinforcement Learning-Based Automatic Cache Replacement Policy in Cloud Block Storage SystemsIEEE Transactions on Computers10.1109/TC.2023.332562573:1(164-177)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TC.2023.3325625
Zhang TGupta ARodríguez MSpjuth OHellander AToor S(2024)Data management of scientific applications in a reinforcement learning-based hierarchical storage system▪Expert Systems with Applications: An International Journal10.1016/j.eswa.2023.121443237:PBOnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121443
Zhu BSheng YZheng LBarrett CJordan MJiao JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)On optimal caching and model multiplexing for large model inferenceProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668699(59062-59094)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668699
Mo SChen YWang HCong GBao Z(2023)Lemo: A Cache-Enhanced Learned Optimizer for Concurrent QueriesProceedings of the ACM on Management of Data10.1145/36267341:4(1-26)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626734
Yang JZhang YQiu ZYue YVinayak RDruschel PKaufmann AMace JFlinn JSeltzer M(2023)FIFO queues are all you need for cache evictionProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613147(130-149)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613147
Yang JQiu ZZhang YYue YRashmi KBaumann ACrooks NSchwarzkopf M(2023)FIFO can be Better than LRU: the Power of Lazy Promotion and Quick DemotionProceedings of the 19th Workshop on Hot Topics in Operating Systems10.1145/3593856.3595887(70-79)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1145/3593856.3595887
Soria-Pardos VArmejach AMück TSuárez-Gracia DJoao JRico AMoretó MSolihin YHeinrich M(2023)DynAMO: Improving Parallelism Through Dynamic Placement of Atomic Memory OperationsProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589065(1-13)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589065
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents