[Prev][Next][Index]

abstract from a talk at UW (the real UW)



at 2:30 in Siegt 422 is in fact a talk about I/O and
file caching and should be of interest to systems people


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

                         Sang Lyul Min

                    Dept. of Computer Engineering
                     Seoul National University
                    (on sabbatical at University of Illinois)

In this talk, I'll present a spectrum of block replacement policies called 
LRFU (Least Recently/Frequently Used) that 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. I will 
also describe an implementation of the LRFU that again subsumes the LRU and 
LFU implementations. Finally, I will present results from both trace-driven 
simulations and our implementation of the LRFU in the FreeBSD operating
system that show there exist points on the spectrum at which the LRFU performs
better than the previously known policies for the workloads we considered.