General adaptive replacement policies
- 24 October 2004
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 108-119
- https://doi.org/10.1145/1029873.1029887
Abstract
We propose a general scheme for creating adaptive replacement policies with good performance and strong theoretical guarantees. Specifically, we show how to combine any two existing replacement policies so that the resulting policy provably can never perform worse than either of the original policies by more than a small factor. To show that our scheme performs very well with real application data, we derive a virtual memory replacement policy that adapts between LRU, loop detection, LFU, and MRU-like replacement. The resulting policy often performs better than all of the policies it adapts over, as well as two other hand-tuned adaptive policies from the recent literature.Keywords
This publication has 17 references indexed in Scilit:
- The EELRU adaptive replacement algorithmPerformance Evaluation, 2003
- Design, implementation, and performance evaluation of a detection-based adaptive block replacement schemeIEEE Transactions on Computers, 2002
- LIRSPublished by Association for Computing Machinery (ACM) ,2002
- LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policiesIEEE Transactions on Computers, 2001
- Trace reduction for virtual memory simulationsPublished by Association for Computing Machinery (ACM) ,1999
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Page replacement algorithm for large-array manipulationSoftware: Practice and Experience, 1980
- A decomposable model of program paging behaviourActa Informatica, 1976
- Computation of page fault probability from program transition diagramCommunications of the ACM, 1974
- Principles of Optimal Page ReplacementJournal of the ACM, 1971