LRFU (Least Recently/Frequently Used) Replacement Policy: A Spectrum of Block Replacement Policies

A spectrum of block replacement policies called LRFU (Least Recently/Frequently Used) is proposed for buffer caches. The proposed spectrum is formed according to how much more weight we give to the recent history than to the older history and subsumes the well-known LRU (Least Recently Used) and the LFU (Least Frequently Used) policies. 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. Results from tracedriven simulations show that there exist points on the spectrum at which the LRFU performs better than the previously known policies for the workloads we considered. This point is reinforced by results from our integration of the LRFU into the FreeBSD..