On the existence of a spectrum of policies that subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) policies

Donghee Lee, Jongmoo Choi, Jong Hun Kim, Sam H. Noh, Sang Lyul Min, Yookun Cho, Chong Sang Kim

Research output: Contribution to journalConference articlepeer-review

153 Scopus citations

Abstract

We show that there exists a spectrum of block replacement policies that subsumes both the Least Recently Used (LRU) and the Least Frequently Used (LFU) policies. The spectrum is formed according to how much more weight we give to the recent history than to the older history, and is referred to as the LRFU (Least Recently/Frequently Used) policy. Unlike many previous policies that use limited history to make block replacement decisions, the LRFU policy uses the complete reference history of blocks recorded during their cache residency. Nevertheless, the LRFU requires only a few words for each block to maintain such history. This paper also describes an implementation of the LRFU that again subsumes the LRU and LFU implementations. The LRFU policy is applied to buffer caching, and results from trace-driven simulations show that the LRFU performs better than previously known policies for the workloads we considered. This point is reinforced by results from our integration of the LRFU into the FreeBSD operating system.

Original languageEnglish
Pages (from-to)134-143
Number of pages10
JournalPerformance Evaluation Review
Volume27
Issue number1
DOIs
StatePublished - Jun 1999
EventProceedings of the 1999 International Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS '99 - Atlata, GA, USA
Duration: 1 May 19994 May 1999

Fingerprint

Dive into the research topics of 'On the existence of a spectrum of policies that subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) policies'. Together they form a unique fingerprint.

Cite this