Information Technology Reference
In-Depth Information
variables that are not in the first
m
memory locations. At least one I/O operation is needed
per variable to operate on them. It thus follows that
log
n
K
ν
(
f
(
n
)
log(
2
d
))
BS
)=
Ω(log
n
−
d
=
0
log
n
=
Ω(log
n
−
d
)
d
=
0
=Ω(log
2
n
)
The last inequality is a consequence of the fact that
log
n
−
d
is greater than
(log
n
)
/
2for
d
≤
(log
n
)
/
2.
Lower bounds on the I/O complexity for these problems can be derived for a large variety
of cost functions. The reader is asked in Problem
11.20
to derive such bounds for the cost
function
ν
(
a
)=
a
α
.
11.9.2 Upper Bounds for the HMM
A natural question in this context is whether these lower bounds can be achieved. We al-
ready know from Theorems
11.5.3
and
11.5.5
that for each allocation of memory to each
memory-hierarchy level, it is possible to match upper and lower bounds on the number of I/O
operations and computation time. As a consequence, for each of these problems near-optimal
solutions exist for any cost function on memory accesses for these problems.
11.10 Competitive Memory Management
The results stated above for the hierarchical memory model assume that the user has explicit
control over the location of data, an assumption that does not apply if storage is allocated by an
operating system. In this section we examine
memory management
by an operating system
for the HMM model, that is, algorithms that respond to memory requests from programs to
move stored items (instructions and data) up and down the memory hierarchy. We examine
offline and online memory management algorithms. An
offline algorithm
is one that has
complete knowledge of the future.
Online algorithms
cannot predict the future and must act
only on the data received up to the present time.
We us e
competitive analysis
, a type of analysis not appearing elsewhere in this topic, to
show that the two widely used online page-replacement algorithms, least recently used (LRU)
and first-in, first-out (FIFO), use about twice as many I/O operations as does MIN, the opti-
mal offline page-replacement algorithm, when these two algorithms are allowed to use about
twice as much memory as MIN. Competitive analysis bounds the performance of an online
algorithm in terms of that of the optimum offline algorithm for the problem without knowing
the performance of the optimum algorithm.
Virtual memory-management systems
allow the programmer to program for one large
virtual random-access memory, such as that assumed by the HMM, although in reality the
memory contains multiple physical memory units one of which is a fast random-access unit
accessed by the CPU. In such systems the hardware and operating system cooperate to move
Search WWH ::
Custom Search