Information Technology Reference
In-Depth Information
Proof : Let C A and C B be the counts of total
faults so far for algorithms A and B, respectively.
We again 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 (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 (A,B)'s
memory that are not in B's memory at the same
point in the execution. The values of C A , C B , d A ,
and d B change as follows on every fault (we denote
the new values C' A , C' B , d' A and d' B ):
(As discussed above, there is no possibility of
a hit for A and B, but a miss for ART (A,B).)
c.
fault for B, fault for A, fault for
ART (A,B): C' A = C A + 1, C' B = C B +
1, d' A ≤ d A , d' B ≤ d B + 1
d.
fault for B, fault for A, hit for
ART (A,B): C' A = C A + 1, C' B = C B +
1, d' A ≤ d A , d' B ≤ d B
e.
hit for B, fault forA, hit forART (A,B):
C' A = C A + 1, C' B = C B , d' A ≤ d A , d' B =
d B
f.
hit for B, fault for A, fault for
ART (A,B): C' A = C A + 1, C' B = C B ,
d' A ≤ d A , d' B ≤ d B
To see how the inequalities are derived, con-
sider, for instance, case 1.e. In this case, there is
a miss for A but not for B, which is reflected in
the update of miss counts. Since the reference is
a hit for ART (A,B), one extra common page will
exist in both memories (for A and for adaptive)
after this reference is processed. At the same time,
however, A can evict a page that is in the current
system memory, so d A (the number of pages kept
in memory by ART that would not be in A's
memory) may decrease or stay the same (hence
the d' A ≤ d A ). d B stays the same since the reference
was a hit both for ART (A,B) and for B.
Using the information on the potential quan-
tities we can show our result. Assume, without
loss of generality, that the algorithm with the
fewest total faults is B. (The case of A is virtually
identical.) Consider the point in the execution
when C A was last equal to C B —we will call this
the “turning point”. This was the last time ART
emulated algorithmA. (This point, of course, could
be the very beginning of the execution.) The main
theorem will be broken up in two parts: first we
show that ART (A,B) cannot have suffered more
than twice as many misses as B until the turning
point, and then we show that ART (A,B) cannot
have suffered more than m more misses than B
after the turning point. The two bounds have a
total of 2x + m.
We can establish that ART (A,B) never suf-
fered more than twice as many misses as B until
1.
if C A > C B (in which case ART (A,B) imi-
tates algorithm B)
a.
fault for B, hit forA, hit forART (A,B):
C' A = C A , C' B = C B + 1, d' A = d A , d' B
d B
b.
fault for B, hit for A, fault for
ART (A,B): C' A = C A , C' B = C B + 1,
d' A ≤ d A , d' B ≤ d B
c.
fault for B, fault for A, fault for
ART (A,B): C' A = C A + 1, C' B = C B +
1, d' A ≤ d A + 1, d' B ≤ d B
d.
fault for B, fault for A, hit for
ART (A,B): C' A = C A + 1, C' B = C B +
1, d' A ≤ d A , d' B ≤ d B
e.
hit for B, fault forA, hit forART (A,B):
C' A = C A + 1, C' B = C B , d' A ≤ d A , d' B =
d B
f.
hit for B, fault for A, fault for
ART (A,B): C' A = C A + 1, C' B = C B ,
d' A ≤ d A + 1, d' B < d B
2.
if C A ≤ C B (in which case ART (A,B) imi-
tates algorithm A)
a.
fault for B, hit forA, hit forART (A,B):
C' A = C A , C' B = C B + 1, d' A = d A , d' B
d B
b.
fault for B, hit for A, fault for
ART (A,B): C' A = C A , C' B = C B + 1,
d' A < d A , d' B ≤ d B + 1
Search WWH ::




Custom Search