Adaptive Replacement Algorithm Templates and EELRU - Advanced Operating Systems and Kernel Applications - page 263

Chapter 13
Adaptive Replacement
Algorithm Templates and EELRU
Yannis Smaragdakis
University of Massachusetts, Amherst, USA
Scott Kaplan
Amherst College, USA
abStract
Replacement algorithms are a major component of operating system design. Every replacement algo-
rithm, however, is pathologically bad for some scenarios, and often these scenarios correspond to com-
mon program patterns. This has prompted the design of adaptive replacement algorithms: algorithms
that emulate two (or more) basic algorithms and pick the decision of the best one based on recent past
behavior. The authors are interested in a special case of adaptive replacement algorithms, which are
instances of adaptive replacement templates (ARTs). An ART is a template that can be applied to any
two algorithms and yield a combination with some guarantees on the properties of the combination,
relative to the properties of the component algorithm. For instance, they show ARTs that for any two
algorithms A and B produce a combined algorithm AB that is guaranteed to emulate within a factor
of 2 the better of A and B on the current input. They call this guarantee a robustness property. This
performance guarantee of ARTs makes them effective but a naïve implementation may not be practi-
cally efficient—e.g., because it requires significant space to emulate both component algorithms at the
same time. In practice, instantiations of an ART can be specialized to be highly efficient. The authors
demonstrate this through a case study. They present the EELRU adaptive replacement algorithm, which
pre-dates ARTs but is truly a highly optimized multiple ART instantiation. EELRU is well-known in the
research literature and outperforms the well-known LRU algorithm when there is benefit to be gained,
while emulating LRU otherwise.