Data cache management using frequency-based replacement

John T. Robinson, Murthy V. Devarakonda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

204 Scopus citations


We propose a new frequency-based replacement algorithm for managing caches used for disk blocks by a file system, database management system, or disk control unit, which we refer to here as data caches. Previously, LRU replacement has usually been used for such caches. We describe a replacement algorithm based on the concept of maintaining reference counts in which locality has been 'factored out'. In this algorithm replacement choices are made using a combination of reference frequency and block age. Simulation results based on traces of file system and I/O activity from actual systems show that this algorithm can offer up to 34% performance improvement over LRU replacement, where the improvement is expressed as the fraction of the performance gain achieved between LRU replacement and the theoretically optimal policy in which the reference string must be known in advance. Furthermore, the implementation complexity and efficiency of this algorithm is comparable to one using LRU replacement.

Original languageEnglish (US)
Title of host publication1990 ACM SIGMETRICS Conf Meas Model Comput Syst
Editors Anon
PublisherPubl by ACM
Number of pages9
ISBN (Print)0897913590
StatePublished - 1990
Externally publishedYes
Event1990 ACM SIGMETRICS Conference on Measurement & Modeling of Computer Systems - Boulder, CO, USA
Duration: May 22 1990May 25 1990

Publication series

Name1990 ACM SIGMETRICS Conf Meas Model Comput Syst


Other1990 ACM SIGMETRICS Conference on Measurement & Modeling of Computer Systems
CityBoulder, CO, USA

ASJC Scopus subject areas

  • General Engineering

Cite this