Optimal Page Replacement
The unbeatable policy you can never implement — the yardstick for every other one.
Skip to the animationOptimal replacement evicts the page that will not be needed for the longest time. It produces the lowest possible fault count for any reference string — and it cannot be implemented, because it requires knowing the future.
The rule
On a fault with memory full, look forward through the rest of the reference string. For each resident page, find its next use. Evict the one whose next use is farthest away — and if a page is never referenced again, evict that one immediately.
It is also called OPT, MIN, or Belady's optimal algorithm. The proof of optimality is a swap argument: any other choice evicts a page needed sooner, which can only bring a fault forward in time, never push one back.
Why bother with an unimplementable algorithm
Because it converts a vague question into a precise one. “Is 12 faults good?” is unanswerable on its own. “Optimal gets 9 on this string, LRU gets 12, FIFO gets 15” tells you exactly how much room is left and whether chasing it is worth the complexity.
| Policy | Faults (20 references, 3 frames) | Fault rate |
|---|---|---|
| FIFO | 15 | 75% |
| LRU | 12 | 60% |
| Optimal | 9 | 45% |
That is the same role a lower bound plays anywhere in computer science: it is the number you are allowed to measure yourself against, and no real policy will beat it.
Why it cannot be built
The OS would need the process's entire future memory access pattern before running it. That depends on the input data, on user actions, on network responses — on things that have not happened yet. It is not a matter of it being too slow; the information does not exist at the moment the decision is required.
It can, however, be computed offline: record a real reference string, replay it afterwards, and you get the true minimum. That is exactly how page replacement policies are evaluated in practice.
Compilers and databases sometimes get close to Optimal for their own data, because they *do* know the access pattern ahead of time. A database that knows it is doing a sequential scan can tell the buffer manager not to keep those pages — future knowledge the general-purpose OS never has.
How the others approximate it
- LRU replaces “farthest next use” with “farthest last use” — the future mirrored into the past. It is usually close, because of locality.
- FIFO replaces it with “oldest resident”, which is not an approximation of anything, and it shows in the numbers.
- Clock / second-chance approximates LRU cheaply using the hardware reference bit, and is what real kernels ship.
Optimal is a stack algorithm, so like LRU it never suffers Belady's anomaly — with more frames it can only do better.
Advantages and disadvantages
Advantages
- Provably the minimum possible number of page faults for any reference string.
- Never suffers Belady's anomaly.
- Gives every other policy a precise yardstick, which is the reason it is taught at all.
Disadvantages
- Impossible to implement — it needs future knowledge that does not exist yet at decision time.
- Usable only offline, on a recorded trace, for evaluation.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.