The Optimal page-replacement algorithm has the most reduced page-fault rate overall page-replacement algorithms and it will never suffer from the effect of Belady’s anomaly. Optimal page replacement is such an algorithm that does exist and has been called OPT or MIN page replacement algorithm. It is just this: “Replace the page that won’t be utilized for the longest time frame.”
The optimal page replacement algorithm
Utilizing an optimal page-replacement algorithm ensures the most minimal conceivable page fault rate for a fixed number of frames. For instance, on our example reference string, the optimal page-replacement algorithm would yield nine-page faults, as represented in Figure 1. Initially, the first three references cause (pre-defined number of page frames) faults that fill the three frames that are empty. The reference to page 2 replaces page 7 because page 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 just nine-page faults, optimal page replacement is obviously superior to a FIFO algorithm, which results in fifteen faults. (In the event that we ignore the first three, which all algorithms must endure, at that point optimal replacement is twice as good as FIFO replacement.) In fact, no replacement algorithm can process this reference string in three frames with fewer than nine faults.
Tragically, the optimal page-replacement algorithm is hard to execute, in light of the fact that it requires future knowledge of the reference string. Therefore, the optimal page replacement algorithm is utilized mainly for comparison studies. For example, it may be valuable to realize that, although a new algorithm is not optimal, it is around 12.3 (%) percent of optimal at worst and within 4.7 (%) percent on average.
Also check: segmentation in os
Calculation of Page Hit ratio:
∵We have;
Total number of reference strings = 20
Total number of page misses or page faults = 9
∵We know that;
Total number of page hits = Total number of reference strings – Total number of page misses or page faults
∴ Total number of page hits (from figure 1) = 20 – 9 = 11
Thus, Page Hit ratio = Total no. of page hits/Total no. of references = 11/20 = 0.05 = 5%
Also See: Demand Paging In Operating System
Important points about Optimal page replacement algorithm:
- The consequence of the revelation of Belady’s Anamoly.
- Most reduced page fault rate of all algorithms and will never suffer from Belady’s Anamoly.
- Just it replaces the pages that won’t be utilized for the longest time frame.
- Optimal page replacement is accurate as possible required, but not possible in practice as the operating system cannot know future requests.
- The utilization of optimal Page replacement is to set up a benchmark so that other replacement algorithms can be analyzed against it.
Advantages of Optimal Page Replacement Algorithm:
In this algorithm, only those pages are replaced that are not be utilized for the longest time frame. It includes future knowledge, because of this capability optimal page replacement algorithm consists following advantages;
- Most reduced page fault rate
- Never suffers from Belady’s anomaly
- Twice tantamount to FIFO Page Replacement Algorithm
Also check: Memory Fragmentation in operating system
Disadvantages of Optimal Page Replacement Algorithm:
The optimal page replacement algorithm consists some of disadvantages are as follows;
- It is hard to execute
- It needs to estimate for example future knowledge
Also check: classification of embedded systems
