Optimal Page Replacement (OPT)
What you'll learn: You'll understand the theoretical best-case algorithm for page replacement that minimizes page faults by looking into the future.
The Core Idea
When a page fault occurs and all frames are full, the operating system must choose which page to evict. The Optimal Page Replacement (OPT) algorithm, also called Bélády's algorithm, always replaces the page that will not be used for the longest time in the future.
This algorithm provably produces the minimum number of page faults for any given reference string. It's the gold standard against which all practical page replacement algorithms are compared.
Why "Optimal" but Impractical
OPT is optimal because it makes the best possible decision every single time—it keeps in memory the pages that will be needed soonest, maximizing frame utilization. However, there's a critical problem: the OS cannot actually predict the future. It doesn't know which pages a program will reference next unless it can see the entire memory reference sequence in advance.
Think of it like having perfect stock market foresight—you'd always buy low and sell high, but in reality, you can't see tomorrow's prices today.
How It Works (Conceptually)
When replacing a page:
- Examine all pages currently in memory
- For each page, determine when it will be referenced next
- Replace the page that won't be needed for the longest time
- If a page is never referenced again, choose it first
Why Study It?
Even though OPT is impossible to implement in real systems, it serves as a theoretical benchmark. By comparing practical algorithms (like LRU or FIFO) against OPT's performance on the same reference string, we can measure how close to optimal our real implementations are.
Key Takeaway: Optimal Page Replacement minimizes page faults by replacing the page needed farthest in the future, but requires impossible foreknowledge—making it a theoretical ideal rather than a practical solution.