1. Introduction
FIFO replaces the oldest page in memory, but it often removes useful pages and suffers from Belady’s Anomaly.
This naturally leads to an important question:
What is the best possible page replacement strategy?
The answer is Optimal Page Replacement (OPT).
Optimal Page Replacement replaces the page that will not be used for the longest time in the future.
2. What is Optimal Page Replacement?
Optimal Page Replacement (OPT) is a page replacement algorithm that replaces the page whose next reference occurs farthest in the future.
Key Idea
Look Ahead into Future
↓
Replace Page Used Latest
or
Replace Page with Farthest Future Use
3. Why Optimal is Important
OPT is extremely important because it represents the best possible page replacement strategy.
3.1 Minimum Page Faults
No page replacement algorithm can generate fewer page faults than OPT.
3.2 Benchmark Algorithm
Used to compare:
FIFO
LRU
Clock
Other algorithms
3.3 Theoretical Standard
Defines the lower bound on page faults.
Key Insight
OPT = Best Possible Performance
4. Basic Principle
When a page fault occurs:
Look at all pages currently in memory.
Check when each page will be used next.
Replace the page whose next use is farthest away.
5. Working Mechanism
For each page reference:
Case 1: Page Present
Page Hit
No replacement needed.
Case 2: Page Absent
Page Fault
If Free Frame Exists
Load page directly.
If Memory Full
Check Future References
↓
Find Page Used Latest
↓
Replace It
6. Algorithm
For each page request:
If page present:
Hit
Else:
Fault
If free frame exists:
Insert page
Else:
Replace page whose next use
occurs farthest in future
7. Example
Given
Reference String:
1 2 3 4 1 2 5 1 2 3 4 5
Frames = 3
8. Step-by-Step Execution
| Ref | Frames | Fault? | Reason |
|---|---|---|---|
| 1 | 1 - - | Yes | Empty frame |
| 2 | 1 2 - | Yes | Empty frame |
| 3 | 1 2 3 | Yes | Empty frame |
| 4 | 1 2 4 | Yes | 3 used farthest in future |
| 1 | 1 2 4 | No | Hit |
| 2 | 1 2 4 | No | Hit |
| 5 | 1 2 5 | Yes | 4 used farthest |
| 1 | 1 2 5 | No | Hit |
| 2 | 1 2 5 | No | Hit |
| 3 | 3 2 5 | Yes | 1 never used again |
| 4 | 4 2 5 | Yes | 3 never used again |
| 5 | 4 2 5 | No | Hit |
9. Result
Total Page Faults = 7
Total Hits = 5
10. Future Analysis Example
Suppose memory contains:
1 2 3
Current request:
4
Future references:
1 2 5 1 2 3 4 5
Next use of pages:
| Page | Next Use |
|---|---|
| 1 | Soon |
| 2 | Soon |
| 3 | Much Later |
Therefore:
Replace Page 3
11. Why OPT Produces Minimum Faults
OPT always makes the best replacement decision.
At every page fault:
Keep Pages Needed Soon
↓
Remove Page Needed Latest
Because future information is perfect, no better decision is possible.
12. Comparison with FIFO
Using the same reference string:
| Algorithm | Page Faults |
|---|---|
| FIFO | 9 |
| OPT | 7 |
Observation
OPT < FIFO
OPT produces fewer faults.
13. Belady's Anomaly
A major advantage of OPT:
No Belady's Anomaly
Increasing the number of frames can never increase page faults.
Important Property
OPT belongs to a class called:
Stack Algorithms
Stack algorithms never suffer from Belady's Anomaly.
14. Characteristics of OPT
Uses future knowledge
Produces minimum page faults
Theoretical algorithm
Used for performance comparison
Never suffers from Belady's Anomaly
15. Advantages of Optimal Page Replacement
15.1 Minimum Page Faults
Best performance possible.
15.2 Ideal Benchmark
Useful for evaluating practical algorithms.
15.3 No Belady's Anomaly
More frames always help.
15.4 Demonstrates Best Case Performance
Provides lower bound on faults.
16. Disadvantages of Optimal Page Replacement
16.1 Future Knowledge Required
Need to know future page references.
Future References Unknown
in real systems.
16.2 Not Practically Implementable
Operating systems cannot predict future exactly.
16.3 Purely Theoretical
Used mainly for:
Research
Analysis
Comparisons
17. Optimal vs FIFO
| Feature | FIFO | Optimal |
|---|---|---|
| Future Knowledge | No | Yes |
| Complexity | Low | High |
| Practical | Yes | No |
| Page Faults | More | Minimum |
| Belady's Anomaly | Yes | No |
18. Optimal vs LRU
| Feature | OPT | LRU |
|---|---|---|
| Uses Future | Yes | No |
| Practical | No | Yes |
| Performance | Best | Near Optimal |
| Implementation | Impossible | Possible |
Key Insight
LRU tries to approximate OPT
without knowing the future.
19. Real-World Analogy
Imagine you know exactly which books you will need during the next month.
When your shelf becomes full:
Keep Books Needed Soon
↓
Remove Book Needed Last
Since you know the future perfectly, you'll make the best possible choice every time.
Optimal Page Replacement is the theoretical best page replacement algorithm because it always replaces the page that will not be used for the longest time in the future, thereby producing the minimum possible number of page faults.