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:

  1. 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.