Optimal Page Replacement

Optimal Page Replacement (Belady's algorithm) answers a clean question: if you could see the future, which page should you evict from memory to cause the fewest faults? The answer is a textbook greedy rule, and the "if you could see the future" framing makes it the gold standard every real cache policy (LRU, FIFO, clock) is measured against.

The slow way first

You could try every possible eviction decision: at each fault with full frames, branch on which of the resident pages to throw out, recurse, and keep the branch with the fewest total faults. That explores an exponential tree of choices — far too slow, and completely unnecessary.

The question to ask: when I must evict someone, which choice can never hurt me? The page I will need again soonest is the one I most want to keep. So the page I should drop is the one I will need again latest.

The idea: evict the farthest future use

Walk the reference string in order. For each page:

• If it is already in a frame, it is a hit — do nothing.
• Otherwise it is a fault. If a frame is free, just load it. If frames are full, look ahead in the remaining reference string and evict the page whose next use is farthest away (a page never used again counts as infinitely far).

The greedy choice is provably optimal: keeping the soonest-needed pages minimizes how often you reload something you just threw away.

Walk through it

Step through the animation. The top row is the reference string and the page pointer scans it left to right; the bottom row is the three frames. The first three accesses fill empty frames (3 faults). 1 is then a hit. At 4 the frames {1, 2, 3} are full: looking ahead, 2 is used next while 1 and 3 are never used again — so we evict one of the never-again pages (3) and load 4. The final 2 is a hit. Total: 4 faults.

Pseudocode

frames = empty list, faults = 0
for each index i with page in refs:
    if page is already in frames:
        continue                       # hit
    faults += 1                        # fault
    if frames are full:
        for each resident page p:
            find its next use in refs[i+1:]  (infinity if none)
        victim = the resident page with the farthest next use
        remove victim from frames
    add page to frames
return faults

The Python solution

def page_faults(refs, cap):
    frames = []
    faults = 0
    for i, page in enumerate(refs):
        if page in frames:
            continue
        faults += 1
        if len(frames) == cap:
            future = refs[i + 1:]
            dist = lambda p: future.index(p) if p in future else float('inf')
            victim = max(frames, key=dist)
            frames.remove(victim)
        frames.append(page)
    return faults

• frames is the set of resident pages; faults counts the misses.
• if page in frames: continue skips hits with no work.
• On a fault we increment faults, then only evict if the frames are full.
• future = refs[i + 1:] is everything we have not processed yet.
• dist returns how soon a page reappears — its index in future, or infinity if it never does.
• max(frames, key=dist) is the greedy heart: the resident page used latest becomes the victim.

Complexity

We store at most cap frames, so space is O(cap). The look-ahead can be made faster with precomputed next-use indices, but the greedy decision itself never changes.

When this pattern shows up

Practice