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

Let us see this pattern in action, by defin-
ing a simple ART, which will produce adaptive
algorithms that are 2-robust with respect to their
component algorithms. The ART will adapt based
on the behavior of A and B during the current
reference, with no memory of how well A and B
did in the past.
DEFINITION 2. ART 0 (A,B). On every
reference to a page that is not in memory (i.e.,
on every miss) algorithm ART 0 (A,B) uses the
following logic:

also a fault for algorithm ART 0 (A,B), then there
are 3 cases in the ART 0 (A,B) eviction logic:

• ART

0 (A,B) evicts a page not in B's
memory.
ART •

0 (A,B) evicts a page not in A's
memory.
ART •

0 (A,B) evicts the same page as A.

In each of the above cases, the page evicted by
ART 0 (A,B) could not have been present in both
A's and B's memory before the eviction or will be
evicted from one of them at the same time. Thus,
if the property held before the current fault, it will
hold after the eviction. □
The lemma means that the set of pages held in
ART 0 (A,B)'s memory is a superset of the intersec-
tion of the sets of pages in A's and B's memories
at all points in time.
We can now prove our robustness result.
THEOREM 1. The adaptive replacement
algorithm ART 0 (A,B) is 2-robust with respect
to both A and B. That is, ART 0 (A,B), as defined
above, never incurs more than twice as many
faults as either A or B.
Proof : We define two “potential” quantities
and examine how their values change on every
fault for either algorithm A or B.
Let d A be the number of pages currently in
ART 0 (A,B)'s memory that are not in A's memory
at the same point in the execution.
Let d B be the number of pages currently in
ART 0 (A,B)'s memory that are not in B's memory at
the same point in the execution. The above values
of d A , and d B change as follows on every fault (we
denote the new values d' A and d' B ):
(Note that according to Lemma 1 a hit for both
A and B implies a hit for ART 0 (A,B) and none of
the potentials changes.)

• if the reference is a miss for A but not for

B, then evict one of the memory pages that
are not in B's memory. (I.e., imitate B.)

(There have to be such pages, since the memo-
ries of ART 0 (A,B) and B have the same size,
otherwise the contents of the real memory and
those of the memory of B would be the same and
the current reference would have been a miss for
B, since it is a miss for ART 0 (A,B).)

• otherwise imitate A:

◦ if the memory contains pages that are

not in A's memory, then evict one of
those pages.
otherwise evict whichever page A ◦

evicts.

To prove the 2-robustness of ART 0 (A,B) with
respect to A and B, we need a simple lemma:
LEMMA 1. Consider the same reference se-
quence processed by replacement policies A, B
and ART 0 (A,B). If at a certain point a page is both
in the memory managed by A and in the memory
managed by B then it is also in the memory man-
aged by ART 0 (A,B).
Proof : The property holds initially and if it
holds up to a point in the reference sequence, then
consider the next fault for either algorithm A or B.
If it is not a fault for ART 0 (A,B), then the property
will hold after the replacement (because the new
page is already in ART 0 (A,B)'s memory). If it is

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

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