An optimal
page-replacement algorithm has the lowest page-fault rate of all algorithms.
Unfortunately the optimal
page-replacement algorithm is difficult to implement, because it require future
knowledge of the reference string.
An optimal
page-replacement algorithm also 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 that the lowest possible page fault rate
for a fixed number of frames.
For example
We can create a FIFO queue
to hold all pages in memory we replace the page at the head of the queue.
1.
The first reference cause fault fill the
three empty frames.
2.
The reference to page 2 replace page 7,
because 7 will not be used until reference 18. Whereas page 0 will be used at
5, and page 1 at 14.
3.
The reference to page 3 replace page 1 as
page 1 will be the last three page in memory to be referenced again.
With only nine page fault
optimal replacement is much better than a FIFO algorithm which had 15 faults.
If we ignore the first
which all algorithms must suffer then optimal replacement is twice as good as
FIFO replacement.
In fact no replacement
algorithm can process this algorithm can process this reference string in three
frame with less than nine faults.