Operating System - Optimal Page Replacement Algorithm
Definition:
The Optimal Page Replacement Algorithm (OPT) replaces the page that will not be used for the longest period of time in the future. This is a theoretical algorithm used mainly for comparison because it requires future knowledge of the reference string.
Key Idea:
“Replace the page that will be used farthest in the future.”
How It Works:
-
When a page fault occurs and memory is full:
-
Look ahead in the reference string.
-
Identify which page in memory will not be used for the longest time.
-
Replace that page.
-
Example:
Let’s consider:
-
Reference String:
7, 0, 1, 2, 0, 3, 0, 4 -
Number of Frames: 3
| Step | Page | Memory Frames | Page Fault | Replaced Page |
|---|---|---|---|---|
| 1 | 7 | 7 _ _ | Yes | — |
| 2 | 0 | 7 0 _ | Yes | — |
| 3 | 1 | 7 0 1 | Yes | — |
| 4 | 2 | 0 1 2 | Yes | 7 (used never) |
| 5 | 0 | 0 1 2 | No | — |
| 6 | 3 | 0 2 3 | Yes | 1 (used never) |
| 7 | 0 | 0 2 3 | No | — |
| 8 | 4 | 0 3 4 | Yes | 2 (used never) |
✅ Total Page Faults: 6
Advantages:
-
Produces the minimum possible number of page faults.
-
Used as a benchmark for evaluating other algorithms.
Disadvantages:
-
Not practically implementable (requires future knowledge).
-
Used only for theoretical analysis.
