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

ART k , the number of instantiations is staggering:
the published EELRU experiments are derived by
using a total of 40 points in the recency histogram
(Smaragdakis, Kaplan, & Wilson, 2003). 15 of
those points are below the memory size m, and
are thus candidates for the early eviction position
e, while another 24 points are above m, and are
candidates for the late eviction position l. Hence,
there are over 300 possible combinations of e
and l points (plus the plain LRU algorithm) that
EELRU examines to pick the optimal, based on
the program's past behavior.A naïve implementa-
tion of EELRU, as consecutive instantiations of
ART k would be catastrophic. The memory needs
alone, in order to record the memory contents for
all 300+ component algorithms, would be clearly
unrealistic.
Nevertheless, the actual implementation
of EELRU has modest space requirements.
The memory contents of all 300+ component
algorithms have very high overlap and can be
computed approximately from a single recency
queue, holding the 2.5∙m most recently accessed
pages. (The 2.5 factor applies to the setup in the
EELRU publication, but any other factor could be
used.) That is, while plain LRU maintains a data
structure of the m most recently accessed pages,
which also happen to be resident in memory,
EELRU does the same for 2.5 times more pages,
many of which are not resident in memory, but
have been evicted to disk. From this data structure,
the memory contents of any component algorithm
(for any combination of e and l points) can be
approximated: the probability that the i-th most
recently accessed page is resident in memory is
known, even without knowing which exact pages
would be in memory. (It is possible to compute
the exact memory contents for any component
algorithm, but only by knowing the initial con-
tents, right before the least-recently-accessed page
was last touched.) This approximation is used in
all adaptivity reasoning and EELRU can imitate
effectively any of the component algorithms it
chooses to adapt into.

The approximate nature of the EELRU adap-
tivity means that it would be hard to apply to it
robustness results, such as those in the previous
section. Yet the robustness property of interest for
EELRU is not with respect to all its 300+ com-
ponent algorithms, but with respect to a specific
one: LRU itself. Since LRU is the best known
replacement algorithm in practice, it is reason-
able to give LRU special status in the EELRU
adaptivity. That is, EELRU can be seen as an
algorithm that first decides whether to stay with
LRU or perform some early evictions, and then
chooses which early evictions to perform. In this
way, the cumulative performance of past early
eviction decisions is taken into account, relative
to that of LRU. Effectively, if we see EELRU as
an algorithm that applies a sequence of ART k in-
stantiations then its structure is ART k (LRU, ART k
(early1,ART k (early2,ART k (…))): LRU is always
at the top of the composition. This guarantees that
EELRU has its tightest robustness result with re-
spect to LRU. Interestingly, LRU is easy to reason
about in the context of EELRU, because there
is no ambiguity with respect to LRU's memory
contents: the EELRU data structure can always
tell us precisely whether a certain page would be
in memory under the LRU algorithm, since LRU
just keeps the m most recently accessed pages in
memory. Overall, EELRU can be proven 3-robust
with respect to LRU using techniques similar to
those presented earlier. (Smaragdakis, Kaplan, &
Wilson, 2003 demonstrate a proof for a much sim-
plified version of EELRU, but a proof for a more
realistic EELRU is effectively the same as that for
algorithm AB(K) by Smaragdakis, 2004.)
In short, EELRU is best understood as a spe-
cialized application of an adaptive replacement
template. Just like the ARTs examined earlier,
EELRU keeps track of recent misses for each of
its component algorithms and chooses to imitate
the algorithm that has the fewest past misses.
For actual implementation, EELRU exploits a
mathematical understanding of how its component
algorithms behave and approximates their memory