Information Technology Reference
In-Depth Information
n
LRU
n
LRU
−
n
MIN
+
1
F
MIN
(
n
MIN
,
s
)+
n
MIN
Proof
We establish the result for FIFO, leaving it to the reader to show it for LRU. (See
Problem
11.23
.) Consider a contiguous subsequence
t
of
s
that immediately follows a page
fault under FIFO and during which FIFO makes
φ
FIFO
=
f
F
LRU
(
n
LRU
,
s
)
≤
n
FIFO
page faults. In the
next paragraph we show that at least
f
different pages are accessed by FIFO during
t
.Let
MIN make
φ
MIN
faults during
t
. Because MIN has
n
MIN
pages,
φ
MIN
≤
≥
f
−
n
MIN
+
1
≥
0. Thus, the ratio of page faults by FIFO and MIN is
f/φ
MIN
n
MIN
+
1
)
.
Let
p
i
be the page on which the fault occurs just before the start of
t
. To show that at
least
f
different pages are accessed by FIFO during
t
, consider the following cases: a) FIFO
faults on
p
i
in
t
; b) FIFO faults on some other page at least twice in
t
; and c) neither case
applies. In the first case, FIFO accesses at least
n
FIFO
different pages because if it accessed
fewer, then
p
i
would still be in its primary memory the second time it is accessed. In the
second case, the same statement applies to the page accessed multiple times. In the third
case, FIFO can have only
f
faults if it accesses at least
f
different pages during
t
.
Now subdivide the memory access sequence
s
into subsequences
t
0
,
t
1
,
...
,
t
k
such that
t
i
,
i
≤
f/
(
f
−
1, starts immediately after a page fault under FIFO and contains
n
FIFO
faults and
t
0
contains at most
n
FIFO
page faults. This set of subsequences can be found by scanning
s
backwards. Since MIN makes
φ
MIN
j
≥
≥
n
FIFO
−
n
MIN
+
1 faults on the
j
th interval,
j
≥
1,
and
φ
MIN
0
φ
FIFO
0
n
MIN
faults on the zeroth interval (that is,
φ
FIFO
0
φ
MIN
0
≥
−
≤
+
n
MIN
),
the number of faults by FIFO,
F
FIFO
(
n
FIFO
,
s
)=
φ
FIFO
+
φ
FIFO
1
+
φ
FIFO
k
+
···
satisfies
0
the condition of the theorem because
φ
FIFO
j
n
FIFO
φ
MIN
≤
/
(
n
FIFO
−
n
MIN
+
1
)
for
j
j
≥
1.
The upper bounds are almost best possible because, as stated in Problem
11.24
,forany
online algorithm A there is a memory-access sequence such that the number of page faults
F
A
(
s
)
satisfies the following lower bound:
n
A
F
A
(
n
A
,
s
)
≥
n
MIN
+
1
F
MIN
(
n
MIN
,
s
)
n
A
−
The difference between this lower bound and the upper bounds given for FIFO and LRU
is
n
MIN
, which takes into account for the possibility that the initial entries in the primary
memory of MIN and FIFO can be completely different.
It follows that the FIFO and LRU page-replacement strategies are very effective strategies
for two-level memory hierarchies.
.......................................
Problems
MATHEMATICAL PRELIMINARIES
11.1 Let
a
and
b
be integers satisfying 1
≤
a
≤
b
. Show that
b/
2
≤
a
b/a
≤
b
.
(
k
+
1
)
a
for
k
an integer.
11.2 Derive a good lower bound on
k
=
1
(
1
/k
)
of the form
Ω(log
m
)
using an approach
similar to that of Problem
2.2
.
Hint:
Consider values of
b
in the range
ka
≤
b
≤
Search WWH ::
Custom Search