Optimal Page Replacement
Imagine if an operating system had a time machine. Whenever physical RAM filled up, the OS could simply look into the future, perfectly predict exactly what the program was going to do next, and make the absolute perfect choice of which page to evict.
This is the premise of the Optimal Page Replacement algorithm.
What is the Optimal Algorithm?
Often referred to as Belady's Optimal Algorithm, the core rule is simple: When a page must be evicted, look ahead at the future sequence of memory requests. Evict the page that will not be needed for the longest amount of time in the future.
If a page is never going to be used again, it is the first candidate for eviction.
A Worked Example
Let's trace exactly how the Optimal algorithm makes its decisions.
Example Parameters:
Page reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3
Number of physical frames: 3| Step | Ref | Frames | Fault | Evicted | Reason |
|---|---|---|---|---|---|
| 1 | 1 | 1 | Yes | - | - |
| 2 | 2 | 1, 2 | Yes | - | - |
| 3 | 3 | 1, 2, 3 | Yes | - | - |
| 4 | 4 | 1, 2, 4 | Yes | 3 | Future is [1, 2, 5, 1, 2, 3]. 1 and 2 are needed immediately. 3 is needed last. Evict 3. |
| 5 | 1 | 1, 2, 4 | No | - | - |
| 6 | 2 | 1, 2, 4 | No | - | - |
| 7 | 5 | 1, 2, 5 | Yes | 4 | Future is [1, 2, 3]. 1 and 2 are needed. 4 is NEVER needed again. Evict 4. |
| 8 | 1 | 1, 2, 5 | No | - | - |
| 9 | 2 | 1, 2, 5 | No | - | - |
| 10 | 3 | 1, 2, 3 | Yes | 5 | Future is empty. OS can evict any page (we evict 5 as it is never used again). |
Pros and Cons
| Advantages | Disadvantages |
|---|---|
| Mathematically Perfect: Guaranteed to yield the absolute lowest possible page fault rate for any given system. | Impossible to Implement: An Operating System cannot predict the future. It has no way of knowing what memory addresses a program will request 5 seconds from now. |
| No Belady's Anomaly: Unlike FIFO, adding more physical frames will ALWAYS reduce or maintain the number of page faults. | Not a Real Solution: It cannot be written into the actual code of a live operating system. |
Why do we study it if it's impossible?
If it cannot be programmed, why do operating system engineers care about it? Because it serves as the ultimate benchmark.
When engineers design a new, realistic algorithm (like LRU or Second Chance), they need to know how good it actually is. They run a simulation using a massive string of memory requests. If LRU generates 12,000 page faults, is that good or bad?
To find out, they run the exact same simulation using the Optimal algorithm. If Optimal generates 11,500 faults, the engineers know LRU is doing a fantastic job, operating at 95% of theoretical perfection. If Optimal generates only 4,000 faults, they know their LRU implementation needs serious work.
Summary
The Optimal Page Replacement algorithm is a theoretical gold standard. By evicting the page that will not be needed for the longest amount of time in the future, it guarantees the absolute minimum number of page faults. While completely useless for running a live computer, it is an invaluable analytical tool for evaluating the performance of real-world algorithms.
Predicting the Optimal Eviction
Question 1 of 1Test your ability to trace the Optimal Algorithm's 'look ahead' logic.