Information Technology Reference
In-Depth Information
data from secondary storage units to the primary storage unit in pages (a collection of items).
Each reference to a virtual memory location is checked to determine whether or not the refer-
enced item is in primary memory. If so, the virtual address is converted to a physical one and
the item fetched by the CPU. If not (if a page fault occurs), the page containing the virtual
address is moved into primary memory and the tables used to translate virtual addresses are
updated. The item at the virtual address is then fetched. To make room for the newly fetched
page, one page in the fast memory is moved up the memory hierarchy.
A page-replacement algorithm is an algorithm that decides which page to remove from a
full primary memory to make space for a new page. We describe and analyze page-replacement
algorithms for two-level memory hierarchies both because they are important in their own right
and because they are used as building blocks for multi-level page-replacement algorithms. A
two-level hierarchy has primary and secondary memories. Let the primary memory contain n
pages and let the secondary memory be of unlimited size.
The FIFO (first-in, first-out) page-replacement algorithm is widely used because it is sim-
ple to implement. Under this replacement policy, the page replaced is the first page to have
arrived in primary memory. The LRU (least recently used) replacement algorithm requires
keeping for each page the time it was last accessed and then choosing for replacement the page
with the earliest time, an operation that is more expensive to implement than the FIFO shift
register.
Under the optimal two-level page-replacement algorithm , called MIN , primary memory
is initialized with the first n pages to be accessed. MIN replaces the page p i in primary memory
whose time t i of next access is largest. If some other page, p j , were replaced instead of p i , p j
would have to return to the primary memory before p i is next accessed, and one more page
replacement would occur than is required by MIN.
Implementing MIN requires knowledge of the future, a completely unreasonable assump-
tion on the part of the operating system designer. Nonetheless, MIN is very useful as a standard
against which to compare the performance of other page-replacement algorithms such as FIFO
and LRU.
11.10.1 Two-Level Memory-Management Algorithms
To compare the performance of FIFO, LRU, and MIN, we characterize memory use by a
memory-address sequence s =
{
s 1 , s 2 , ...
}
of HMM addresses accessed by a computation.
We assume that no memory entries are created or destroyed. We let F FIFO ( n , s ) , F LRU ( n , s ) ,
and F MIN ( n , s ) be the number of page faults with each page-replacement algorithm on the
memory address sequence s when the primary memory holds n pages.
We now bound the performance of the FIFO and LRU page-replacement algorithms in
terms of that of MIN. We show that if the number of pages available to FIFO and LRU
is double the number available to MIN, the number of page faults with FIFO and LRU is
at most about double the number with MIN. It follows that FIFO and LRU are very good
page-replacement algorithms, a result seen in practice.
THEOREM 11.10.1 Let n FIFO , n LRU ,and n MIN be the number of primary memory pages used
by the FIFO, LRU, and MIN algorithms. Let n FIFO
n MIN and n LRU
n MIN .Then,for
any memory-address sequence s the following inequalities hold:
n FIFO
n FIFO
F FIFO ( n FIFO , s )
n MIN + 1 F MIN ( n MIN , s )+ n MIN
Search WWH ::




Custom Search