Optimal (Belady's) — Page Replacement

Overview

What this concept solves

Optimal — also called OPT, MIN, or Belady's algorithm — answers a simple question perfectly: of the pages in memory, which one won't be needed for the longest time? Evict that one. If a page is never used again, it's the ideal victim.

This produces the minimum possible number of page faults for a given reference string and frame count. No real algorithm can do better. That makes Optimal incredibly useful — not as something you'd run, but as the yardstick. When you measure LRU or Clock, you compare against Optimal to see how much room is left.

The reason you can't actually use it is right there in the definition: it needs to know the future. A running program hasn't told you what it will reference next. So Optimal is computed offline, on a recorded trace, after the fact. Every practical policy is really an attempt to guess the future from the past.

Mechanics

How it works

The rule, step by step

Page already in a frame? Hit. Nothing to do — Optimal never needs to reorder on a hit.
Not in memory, free frame available? Load it into the free frame.
Not in memory, all frames full? For each resident page, scan the rest of the reference string to find its next use. Evict the page whose next use is furthest in the future. A page that's never used again wins (is evicted) immediately.

Why furthest-future is provably optimal

Intuitively: the page you won't need for the longest time is the one you can most afford to lose, because by the time you'd want it back, every other resident page will have already had its turn. Belady proved this rigorously in 1966. The key consequence for you: Optimal is a hard floor — if your policy's fault count equals Optimal's, you cannot improve it by being cleverer about eviction; you'd need more memory.

Optimal is also a stack algorithm, so it never suffers Belady's anomaly: giving it more frames can only reduce (or hold) the fault count, never increase it. Try the Belady example preset at 3 then 4 frames and watch faults behave sensibly — the opposite of FIFO.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Optimal (Belady's)

About this simulation

Optimal looks into the future. On each fault it computes, for every resident page, the step where that page is next used — shown under each frame and as a dashed outline on the reference string ahead. It evicts the page whose next use is furthest away (or never). Step through and watch the lookahead drive each choice. This is the fewest faults any algorithm could possibly achieve.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Read the lookahead

Load the Classic textbook preset and step to the first fault that requires an eviction. Under each frame you'll see 'next @ step N' or 'not used again'. The decision card lists the lookahead for every resident page and marks which one is evicted. Confirm it always picks the largest 'next use' distance.

try 02

Spot the 'never used again' win

Step through any preset until a resident page has no future use. The prototype marks it 'not used again' and evicts it on the very next fault, ahead of pages that will be needed. A page with no future is the perfect victim.

try 03

Race it against the others

Note Optimal's total faults on the Belady example preset, then open the FIFO and LRU prototypes and run the same string and frame count. Optimal's fault count is the floor; see how close LRU gets and how far FIFO trails. Then raise Optimal to 4 frames — unlike FIFO, faults only drop.

In practice

When to use it — and what you give up

How it's actually used

As the benchmark — run Optimal on a captured trace to learn the best achievable fault rate, then judge real policies against it.
To size memory — if even Optimal faults a lot at N frames, the problem is capacity, not policy; you need more RAM, not a smarter algorithm.
To sanity-check a simulator — no policy should ever beat Optimal. If one does, there's a bug.
Never in a live system — it requires future knowledge that a running program cannot provide. Treat it as theory, not implementation.

The bridge to LRU

Optimal looks forward to the next use. LRU looks backward to the last use and bets the future mirrors the past. That bet — the principle of locality — is why LRU, an implementable policy, often lands surprisingly close to the unbeatable one. Studying Optimal first makes LRU's logic obvious.

Pros

Provably minimal faults — no algorithm can do better for the same memory.
The definitive benchmark — gives every other policy a meaningful target.
No Belady's anomaly — it's a stack algorithm; more frames never hurt.
Conceptually clarifying — frames it as 'guess the future', which is what every real policy attempts.

Cons

Unimplementable online — needs to know future references.
Requires the full trace — only computable offline, after the fact.
Costly to compute naively — scanning ahead for each resident page on every fault (though smarter implementations precompute next-use distances).
Not a product, only a measuring stick — you can't ship it.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

optimal.ts

// Optimal (Belady's) page replacement — needs the full future trace.
function optimal(refs: number[], frames: number) {
  const resident: number[] = [];
  let faults = 0, hits = 0;

  // distance to the next use of `page`, searching from index `from`
  const nextUse = (page: number, from: number): number => {
    for (let k = from; k < refs.length; k++) if (refs[k] === page) return k;
    return Infinity;                         // never used again
  };

  refs.forEach((page, i) => {
    if (resident.includes(page)) { hits++; return; }   // hit
    faults++;
    if (resident.length < frames) { resident.push(page); return; } // free frame

    // evict the resident page whose next use is furthest in the future
    let victim = 0, best = -1;
    for (let f = 0; f < resident.length; f++) {
      const d = nextUse(resident[f], i + 1);
      if (d > best) { best = d; victim = f; }
    }
    resident[victim] = page;
  });

  return { faults, hits };                   // faults is the provable minimum
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Which page does Optimal evict when memory is full?

question 02 / 03

Why can't Optimal be used in a real running system?

question 03 / 03

What is the main practical value of Optimal?

0/3 answered