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

3 fault for B, fault for A, fault for
ART 0 (A,B): d' A ≤ d A , d' B ≤ d B + 1

and 3, where both B and ART 0 (A,B) incur faults.
Thus, for every fault of ART 0 (A,B) that is not a
fault of B, B and ART 0 (A,B) must have suffered
a common fault earlier. That is, ART 0 (A,B) can
only incur up to twice as many faults as B. □
ART 0 produces algorithms that are not too re-
alistic because they only check the performance of
algorithmsA and B for the very last memory refer-
ence. A more realistic algorithm would remember
what A and B have done over a longer timeframe
and imitate the better algorithm. Indeed, a simple
but powerful ART would be one that remembers
how well A and B have done in the current ex-
ecution, i.e., it uses two counters misses(A) and
misses(B) that reflect the total number of misses
so far. We call this template ART ∞ .
DEFINITION 3. ART ∞ (A,B). On every
reference to a page that is not in memory (i.e.,
on every miss) algorithm ART ∞ (A,B) uses the
following logic:

4 fault for B, fault for A, hit for ART 0 (A,B):
d' A ≤ d A , d' B ≤ d B

5 hit for B, fault for A, hit for ART 0 (A,B):
d' A ≤ d A , d' B = d B

6 hit for B, fault for A, fault for ART 0 (A,B):
d' A ≤ d A + 1, d' B < d B

We do not show all the case-by-case reason-
ing needed to derive the above values since the
derivation is tedious but straightforward. As a
single example, consider case 2. In this case, there
is a fault for B and ART 0 (A,B) but a hit for A.
Thus ART 0 (A,B) is imitating A and furthermore
ART 0 (A,B)'s memory contains pages not in A's
memory (otherwise A would have suffered a fault
as well). Then, the newly referenced page is al-
ready in A's memory and ART 0 (A,B) will replace
a page not in A's memory. Thus, the difference of
the two memories will strictly decrease: d' A < d A .
At the same time, ART 0 (A,B) and B will fault-in
the same page, but they may pick two different
pages to evict and these pages could have been
common to both their memories before. Thus d B
(the number of pages in ART 0 (A,B)'s memory
that are not in B's memory) may increase but at
most by one (hence the d' B ≤ d B + 1).
Now we can show that ART 0 (A,B) is 2-robust
relative to A. To see this, consider that for each
fault of ART 0 (A,B) that is not a fault of A (case 2)
d A is strictly decreasing (by 1). But d A is originally
0, has to stay nonnegative, and increases only in
the case where both A and ART 0 (A,B) incur a
fault (case 6). Thus, for every fault of ART 0 (A,B)
that is not a fault of A, A and ART 0 (A,B) must
have suffered a common fault earlier. That is,
ART 0 (A,B) can only incur up to twice as many
faults as A.
Similarly, we can show that ART 0 (A,B) is
2-robust with respect to B. If ART 0 (A,B) suffers
a fault that is not a fault of B (case 6) then d B is
strictly decreasing. But d B is originally 0, has to
stay non-negative, and increases only in cases 2

• if (misses(A) > misses(B)) then imitate B:

◦ if B missed AND the page B would

evict is in memory, evict that page
otherwise evict one of the memory ◦

pages that are not in B's memory. (By
same reasoning as in Def. 2, there
have to be such pages.)
otherwise imitate A (same as above with B •

replaced by A).

It is easy to show, with similar reasoning as in
Lemma 1, that the set of pages held inART ∞ (A,B)'s
memory is a superset of the intersection of the
sets of pages in A's and B's memories at all points
in time.
We can prove relatively easily a robustness
result for ART ∞ (A,B).
THEOREM 2. The adaptive replacement
algorithm ART ∞ (A,B) is 2-robust with respect
to both A and B. That is, ART ∞ (A,B), as defined
above, never incurs more than 2x + m faults, where
x is the minimum number of faults of algorithms
A and B, and m is the memory size.