CREATE OWN LIBRARY

Optimal Page Replacement algorithm

Replace the page that will not be used for the longest period of time. 

The use of this page-replacement algorithm guarantees the lowest possible page fault rate for a fixed number of frames.

But practically the optimal page replacement algorithm is difficult to implement because it requires future knowledge of the reference string (Same as Shortest Job First (SJF) Scheduling).

As a result, the optimal algorithm is used mainly for comparison studies.

Otherwise, the optimal page replacement algorithm will be given always less or an equal number of page faults compare to all other page replacement algorithms. 

There is no page replacement algorithm that exists which can give less number of page faults compare to optimal with certain page reference strings. 

So, in real life optimal page replacement algorithm used as a benchmark, to check the efficiency of other page replacement algorithms.

Example: 

Consider the page reference string (UGC NET– 2016)

1   2  3   4   2  1   5   6   2    1    2   3    7    6   3

Find the number of page faults with optimal, where 5 page frames are present.

Solution:

Explanation: 

Initially, frames are empty, now because our 5 frames are empty, we can load the first different 5 page references into frames.

Step 1: Now, we load the first 5 page references 1, 2, 3, 4, 2, but we are not considering 2 after 4 because page 2 is already loaded. Now we go to the next page reference 1, but again it is already loaded. We consider the next page 5, now it is new not in frames, so, we load 5 into the last frame.

Step 2: Now, after loaded page reference 5, the next requirement of page reference is 6. But no frames are available; one loaded page should be replaced as per the optimal solution. 

Now, if you see page references 1, 2, 3, 4, 5 which are right now at the frame. Now, if we see future upcoming possibilities among those pages, page reference 4 will never occur. 

So, we replace page reference 4 by page reference 6.

Step 3: After loaded page reference 6, the next requirement of page reference is 2, not considered because already in the frame. 

Next page reference is 1, not consider because it previously loaded into the frame. 

Next page reference is again 2, not consider because it is already into the frame. 

Next requirement of page reference is 3, but it is already loaded into the frame.

Next requirement of page reference is 7, new page. But all frames are full, so we have replaced one page from the frame.

Now, again we will apply the optimal solution to replace a page from the frame. Consider those pages 1, 2, 3, 6, 5 which are right now at frames. 

Now, if we see future upcoming possibilities among those pages, page references 1, 2, 5 will never occur. 

So, we can replace anyone but 5 is older than 1 and 2, so, it is better to replace 5 and insert 7 into the frame.  [Note: If we replace 1 or 2, the number of page fault will be the same]

Step 4: After insert page reference 7 into the frame, the next requirement of page reference is 6, not considered because already in the frame. 

Next request for page reference is 3 which also present in the frame. 

Now page reference request is ended. 

So, the number of distinct page references 1, 2, 3, 4, 5, 6, 7 working with the frame, after each page fault occurred, so, the number of page faults = 7.

And page fault rate = number of page faults / number page references

So, page fault rate = 7 / 15 = 0.46