On the Relative Dominance of Paging Algorithms
Journal version
[.pdf]
Abstract
In this paper we give a fi ner separation of several known paging algorithms using a new technique called relative interval analysis. This technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size rather than in the worst case alone. Using this technique we characterize the relative performance of LRU and LRU-2, as well as LRU and FWF, among others. We also show that lookahead is bene ficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verifi ed by theory.
Bibtex Entry
