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

An ART instantiation may be effective, yet it
may not be a good candidate for straightforward
applied implementation. For instance, the ART
may be specifying that the combined algorithm
needs to maintain the memory contents of its
component algorithms. This is inefficient and
wasteful when the memory contents of the two
algorithms have few differences. The problem is
exacerbated when more than two algorithms are
being adapted over. For instance, when adapting
over 8 algorithms, as has been the case in past
experiments (Smaragdakis, 2004), a straightfor-
ward application of an ART will require over 8
times the memory space kept for the data struc-
tures of a single replacement algorithm. (This is
not to be confused with the memory space used
to store the actual data. The data structures used
by the replacement algorithm are typically much
smaller—asymptotically logarithmic—than the
overall main memory that the algorithm manages.)
Furthermore, the ART performance guarantees
(i.e., the 2x bound in the number of faults) are
significantly weakened when more algorithms are
being adapted over. If, for instance, we combine 3
algorithms with an ART guaranteeing a 2x bound
per combination, then the naïve application of the
theory just yields a 4x bound. If we adapt over 4
algorithms, we get an 8x bound, etc.
These drawbacks are largely artifacts of the
simplistic realization of the combinations, how-
ever. In practice, for specific algorithms being
adapted over we can specialize the ART instantia-
tion so that the overheads are nearly eliminated.
We demonstrate this with a case study. We analyze
EELRU: a well-known adaptive replacement algo-
rithm that pre-dates (and to some extent inspired)
the ART idea. EELRU can be seen as a specific
instantiation of an ART. The configuration of EE-
LRU in past experiments (Smaragdakis, Kaplan,
& Wilson, 2003) is adapting over several hundred
component algorithms! Nevertheless, we show
that, with appropriate specialization, the space
overhead of EELRU is a small (2.5x) increment
over the space required for LRU—EELRU's main

component algorithm. Furthermore, EELRU can
be proven to always perform within a small bound
(3x) of LRU. This reveals the potential of special-
izing ARTs to get practical algorithms instead of
just good policies.

adaptiVe replacement
templateS

Consider an adaptive replacement algorithm that
dynamically (i.e., during execution) switches
between algorithms A and B so that it uses A
(resp. B) whenever recent behavior indicates that
A (resp. B) outperforms B (resp. A). How can we
define a general adaptive replacement template
that is independent of A and B, yet has bounded
worst-case behavior with respect to either A or
B? We first discuss a very simple ART, which is
not expected to work well in practice. Neverthe-
less, the simple template is very useful because
it makes it trivial to prove desirable worst-case
behavior properties.
We first introduce some terminology.
DEFINITION 1. Robustness : A replacement
algorithm R1 is c-robust with respect to replace-
ment algorithm R2 if R1 can never incur more than
c times (plus possibly a constant, independent of
the number of references) as many faults as R2
for any input and memory size.
All the ARTs we define have a common
structure. They produce an adaptive replacement
algorithm, AB, that simulates both component
algorithmsA and B in memory.AB has full knowl-
edge of the memory contents under algorithms A
and B in the given point of the execution. Thus,
AB can tell whether a given reference to a memory
page (the unit of data storage in virtual memory)
would be a hit (i.e., would be in main memory)
or a miss (i.e., a fault) for algorithms A and B, as
well as what each algorithm would do in that point
in the execution. Based on past behavior, memory
contents, and whatA and B would do, the adaptive
algorithm decides on its own action.