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