Optimal page replacement, explained

Optimal page replacement looks into the future. When a page must be removed, it picks the page that will not be needed for the longest time, or never again. No other algorithm can cause fewer page faults on the same list.

Real systems cannot see which pages a program will ask for next, so this algorithm cannot be used in practice. Its value is as a yardstick: it tells you how close FIFO or LRU come to the best possible answer.

How it works

• Read the next page request.
• If the page is already in a frame, it is a hit.
• If not, it is a page fault. Load the page into an empty frame if there is one.
• If every frame is full, look ahead at the remaining requests and remove the page whose next use is furthest away (or that is never used again).

A small example

Request list, with 3 frames:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Result with Optimal:

9 page faults

Compare this with FIFO (15) and LRU (12) on the same list. Nothing can do better than 9 here.

What to know about its cost

• It needs the whole future request list, which real systems do not have.
• It never shows Belady's anomaly.
• It is the lower limit for page faults, so it is used to measure other algorithms.

Where it works well

• The fewest possible page faults.
• A fair benchmark for every other algorithm.

Where it struggles

• It cannot be implemented in a real operating system.
• It is only useful offline, when the full list is known.

Try it yourself

Open the Page Replacement experiment, enter the request list from this post with 3 frames, choose Optimal and step through it. Then switch to the other algorithms and compare the page faults.

Open the Page Replacement experiment