Page 190 - DCAP103_Principle of operating system

Unit 5: Memory Management

retrieve the active page. Some other page will need to be replaced to bring the active page back Notes
into memory. Thus, a bad replacement choice increases the page-fault rate and slows process
execution, but does not cause incorrect execution.
To illustrate the problems that are possible with a FIFO page-replacement algorithm, we consider
the reference string page frames.
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Figure 5.30: FIFO Page-replacement Algorithm

Figure 5.31: Page-fault Curve for FIFO Replacement on a Reference String

16

14
12

Number of pages 8 6
10

4

1 2 3 4 5 6 7
Number of frames
5.10.3 Optimal Page Replacement
One result of the discovery of Belady’s anomaly was the search for an optimal.

5.10.4 Page-replacement Algorithm
An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms, and
will never suffer from Belady’s anomaly. Such an algorithm does exist, and has been called OPT
or MIN. It is simply replace the page that will not be used for the longest period of time. Use
of this page-replacement algorithm guarantees the lowest possible page fault rate for a fixed
number of frames. For example, on our sample reference string, the optimal page-replacement
algorithm would yield nine page faults. The first three references cause faults that fill the three
empty frames. The reference to page reference string 2 replaces page 7, because 7 will not be
used until reference 18, whereas page 0 will be used at 5, and page 1 at 14. The reference to
page 3 replaces page 1, as page 1 will be the last of the three pages in memory to be referenced
again. With only nine page faults, optimal replacement is much better than a FIFO algorithm,
which had 15 faults. (If we ignore the first three, which all algorithms must suffer, then optimal
replacement is twice as good as FIFO replacement) In fact, no replacement algorithm can process
this reference string in three frames with less than nine faults. Unfortunately, the optimal page-
replacement algorithm is difficult to implement, because it requires future knowledge of the

LOVELY PROFESSIONAL UNIVERSITY 183