Optimal Page Replacement Algorithm

Introduction

Optimal page replacement is a theoretical page replacement algorithm used to make the best possible eviction decision. It is also known as OPT or MIN.

When a page fault occurs and all frames are full, Optimal removes the page that will not be used for the longest time in the future. This gives the lowest possible number of page faults for a fixed reference string and frame count.

Optimal Page Replacement Meaning

The rule of Optimal page replacement is simple: evict the resident page whose next use is farthest in the future. If a page in memory is never used again, it becomes the best victim.

Optimal does not depend on when a page entered memory or when it was last used. It depends only on future use, which is why it is considered an ideal algorithm rather than a practical online policy.

Why Optimal Page Replacement Matters

Optimal cannot be used directly by a normal operating system because the OS does not know the exact future reference string of a running process. Still, it is important because it gives the best possible result for comparison.

For example, if Optimal gives 5 page faults, LRU gives 6, and FIFO gives 7 for the same reference string and frames, Optimal acts as the ideal standard. It tells how close practical algorithms are to the best possible page replacement behavior.

So, Optimal is mainly useful as a benchmark. It shows the minimum page faults that any page replacement algorithm can achieve for a given case.

Flow of Optimal Algorithm

Optimal follows the normal page replacement flow, but its victim selection is based on future references.

• Check the requested page: If the page is already in RAM, record a hit.

• Handle a page fault: If the page is not in RAM, record a page fault.

• Use a free frame if available: If a frame is empty, load the requested page directly.

• Look ahead when frames are full: Check the next use of every page currently present in RAM.

• Choose the victim: Evict the page that will be used farthest in the future.

• Prefer never-used-again pages: If a resident page is never used again, it is the best victim.

• Load the new page: Put the requested page into the victim’s frame and continue.

The key difference from FIFO or LRU is that Optimal looks forward in the reference string, not backward.

Optimal Worked Example

Consider this setup:

• Reference string: 1, 2, 3, 2, 4, 1, 2, 5

• Number of frames: 3

• Initial memory: Empty

• Tie rule: If multiple pages are never used again, evict the leftmost page in the frame table.

At step 5, page 4 causes a fault and all frames are full. Looking ahead, page 1 is used at step 6, page 2 is used at step 7, and page 3 is never used again. So page 3 is evicted.

At step 8, page 5 causes a fault. Pages 1, 2, and 4 are all never used again, so the given tie rule is applied and page 1 is evicted.

For the given reference string, there are 5 page faults and 3 page hits. Therefore, the page fault rate is 5 / 8.

Strengths and Limitations

Summary

Optimal page replacement evicts the page that will not be used for the longest time in the future. If a page in memory is never referenced again, it is the best victim because removing it cannot cause a future fault for that page.

Optimal is not practical as a live operating system algorithm, but it is very useful for comparison. It gives the minimum possible page faults and helps measure how close practical algorithms like FIFO, LRU, and Clock come to the ideal result.