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

the turning point: ART ∞ (A,B) suffers a miss that
is not a miss for B only in cases 1.f and 2.f, above.
But each of these cases increases the metric C A -
C B . Since C A - C B is zero initially and also zero
at the turning point (by definition), the number
of times cases 1.f and 2.f could have occurred
is at most as many as the number of times the
difference C A - C B has decreased. But this only
occurs in cases 1.a, 1.b, 2.a, and 2.b, and in all of
those algorithm B suffers a miss. In other words,
the number of misses for ART ∞ (A,B) that are
not misses for algorithm B are at most as many
as the misses of B. That is, ART ∞ (A,B) can only
suffer up to twice the misses of B up until the
turning point.
At the turning point (and, actually, any other
point as well) the value of quantity d B is at most
equal to the memory size, m—since d B reflects
how many pages in the set are different between
the memories of ART ∞ (A,B) and B. After the
turning point, ART ∞ (A,B) imitates algorithm B.
Thus, the only case where ART ∞ (A,B) suffers a
miss that is not a miss for B is case 1.f. But in this
case, d B gets decremented and it can never drop
below zero. Thus, ART ∞ suffers at most d B misses
over those of B after the turning point, which is
at most equal to m.
Hence, overall, ART ∞ (A,B) never incurs more
than 2x + m faults, where x is the number of faults
of the better of the two algorithms A and B and
m is the memory size. □
The above results demonstrate the general-
ity and value of ARTs. Without any knowledge
concerning algorithms A and B, and with no as-
sumptions on the behavior of the workload, we
can prove worst-case bounds on the performance
of an adaptive algorithm relative to the perfor-
mance of the better of A and B. The generality of
the results for these ARTs means that they can be
applied to various caching domains, even beyond
operating systems (e.g., processor level-2 cach-
ing (Subramanian, Smaragdakis, & Loh, 2006)).
Following similar reasoning as above, other
robustness results for adaptive algorithms can

be proven (Smaragdakis, 2004). Most notably,
an adaptive algorithm can base its decisions on
a window of k recent misses, as opposed to just
the last miss (as in ART 0 ) or all the misses that
occurred in the past (as in ART ∞ ). This would
produce a template ART k , which has interesting
practical instantiations, as seen next.

implementing adaptiVe
replacement algorithmS—
the eelru algorithm

An adaptive replacement template can be used to
produce effective policies, but it does not directly
result in efficient algorithms. For instance, it is not
clear how to combine a large number of existing
algorithms without needing to keep a record of
the memory contents of each one. For a single
algorithm, keeping a record of the pages it would
hold in memory is typically a small storage cost
in a modern OS. For instance, keeping a record
of which 8KB pages are resident in memory can
typically be done with a data structure storing
a few tens of bytes per page—an overhead of
less than 0.5%. Nevertheless, when an adaptive
algorithm wants to adapt over N distinct other
algorithms, the overhead would be multiplied
by N and would soon end up being prohibitive.
Furthermore, it is not clear what is a tight bound
for the robustness of an adaptive algorithm when
it adapts over more than two basic algorithms.
A simplistic application of our earlier theorems
suggests that when N policies are being com-
posed pair-wise, the resulting adaptive algorithm
is only 2 N-1 -robust with respect to two of them
(the first in the composition). This bound can be
likely tightened with further theoretical work, but
the worst-case behavior of the general case (for
arbitrary algorithms being adapted over) is not
likely to be the worst-case behavior for specific
algorithms that are useful in practice.
The space constraints and worst-case bounds
of adaptive algorithms can be significantly allevi-