Lesson 3 · Memory management

Optimal Page Replacement: The Benchmark

Evict the page whose next use lies furthest in the future. It provably takes the fewest possible faults, and it needs the one thing no operating system has — the future.

What the Optimal Page Replacement Algorithm Is

The optimal page replacement algorithm — OPT, also called Belady's algorithm or MIN — evicts the resident page whose next use lies furthest in the future. When a page fault arrives and every frame is occupied, OPT looks forward along the reference string, finds where each resident page will next be needed, and removes the one that will be needed last.

A page fault occurs and no free frame is available, so a victim must be chosen.
For each resident page, scan forward through the remaining reference string to find its next use.
A page that is never referenced again is the ideal victim evicting it costs nothing at all.
Otherwise pick the page whose next use is furthest away, measured in references from now.
Evict that page, load the faulting page into its frame, and continue.

Optimal page replacement is a benchmark, not a policy you can ship. Belady proved in 1966 that no replacement algorithm can produce fewer faults on a given reference string, which makes OPT the floor — the number every real algorithm is measured against.

The reason it cannot be implemented is immediate: an operating system choosing a victim right now does not know what the process will reference next. That information exists only after the program has run. OPT is therefore run offline, against a trace recorded from a previous execution.

Decision rule: maximise the distance to next use
A page never used again is always evicted first
Ties can be broken arbitrarily without affecting the fault count
Requires the complete future reference string

Optimal Page Replacement Algorithm Example

This optimal page replacement algorithm example uses the standard exam string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with three frames. Work it left to right; at every fault with full frames, look forward and evict the page you will not need for the longest.

The first three references fault into empty frames — no choice is involved. The algorithm proper begins at reference 4.

Reference 2, frames [7, 0, 1]. Looking forward from here: 0 is needed at the very next reference, 1 is never referenced again, and 7 is never referenced again. Both 7 and 1 are dead, so either can go; evict 7. Frames become [2, 0, 1].

Reference 0 — resident, a hit. Reference 3, frames [2, 0, 1]. Forward: 0 is needed next reference, 2 is needed in three references, 1 is never used again. Evict 1, the page with no future at all. Frames [2, 0, 3].

Reference 0 — hit. Reference 4, frames [2, 0, 3]. Forward: 2 comes in one reference, 3 in two, 0 in four. Evict 0, furthest ahead. Frames [2, 4, 3].

Reference 2 — hit. Reference 3 — hit. Reference 0, frames [2, 4, 3]. Forward: 3 comes next, 2 comes last, 4 is never used again. Evict 4. Frames [2, 0, 3]. The final three references — 3, 2 — are all hits.

Total: 7 faults, 6 hits. On the same string FIFO takes 10 and LRU takes 9. That gap is the value of perfect information.

OPT on 7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames — every decision, with the lookahead that drove it
Ref	Frames after	Event	Why this victim
7	7 – –	fault	empty frame
0	7 0 –	fault	empty frame
1	7 0 1	fault	empty frame
2	2 0 1	evict 7	7 never referenced again
0	2 0 1	hit	—
3	2 0 3	evict 1	1 never referenced again
0	2 0 3	hit	—
4	2 4 3	evict 0	0 next at ref 11; 2 at ref 9, 3 at ref 10
2	2 4 3	hit	—
3	2 4 3	hit	—
0	2 0 3	evict 4	4 never referenced again
3	2 0 3	hit	—
2	2 0 3	hit	—
Total	—	7 faults	the minimum possible on this string

7 faults — the provable floor for this string and frame count
Four of the five evictions were pages never used again
FIFO: 10 faults. LRU: 9. OPT: 7
Hits cost ~100 ns; each avoided fault saves tens of microseconds

Key reference

Terms, operations, and practical uses

The rule

DecisionEvict the resident page whose next use is furthest ahead.
Dead pageOne never referenced again — the ideal victim, costs nothing.
TiesBreak arbitrarily; the fault count is unaffected.
LookaheadDistance measured in references from the current position.

Why it cannot ship

Missing inputThe future reference string does not exist at decision time.
Profiles failA different input takes different branches.
Offline useRun against a recorded trace to get the fault floor.
ExceptionComputable where the whole sequence is known — query plans, batch jobs.

As a benchmark

7 faultsThe minimum on 7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames.
HeadroomTells you whether a policy has 5% or 500% left to gain.
Stack algorithmResident sets nest, so it is immune to Belady's anomaly.
Also calledOPT, MIN, or Belady's algorithm.

Implementation

OPT on the standard reference string

def optimal(refs, frames):
    """Optimal page replacement. Returns (faults, hits).

    Evicts the resident page whose next use lies furthest ahead. Needs the
    whole reference string up front, which is why this is a benchmark rather
    than something an operating system can run.
    """
    resident, faults, hits = [], 0, 0

    for i, page in enumerate(refs):
        if page in resident:
            hits += 1
            continue

        faults += 1
        if len(resident) < frames:
            resident.append(page)
            continue

        # Distance to each resident page's next use; never used again wins.
        def next_use(candidate):
            future = refs[i + 1:]
            return future.index(candidate) if candidate in future else float("inf")

        victim = max(resident, key=next_use)
        resident[resident.index(victim)] = page

    return faults, hits


refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print(optimal(refs, 3))  # (7, 6)

#include <algorithm>
#include <iostream>
#include <vector>
// Optimal page replacement: evict the page used furthest in the future.
// Returns the fault count; `hits` receives the hit count.
int optimal(const std::vector<int>& refs, int frames, int& hits) {
    std::vector<int> resident;
    int faults = 0;
    hits = 0;
    for (size_t i = 0; i < refs.size(); ++i) {
        int page = refs[i];
        if (std::find(resident.begin(), resident.end(), page) != resident.end()) {
            ++hits;
            continue;
        }
        ++faults;
        if (static_cast<int>(resident.size()) < frames) {
            resident.push_back(page);
            continue;
        }
        // Furthest next use, treating "never again" as infinitely far.
        size_t bestDistance = 0;
        size_t victimIndex = 0;
        for (size_t v = 0; v < resident.size(); ++v) {
            size_t distance = refs.size();
            for (size_t j = i + 1; j < refs.size(); ++j) {
                if (refs[j] == resident[v]) {
                    distance = j;
                    break;
                }
            }
            if (distance >= bestDistance) {
                bestDistance = distance;
                victimIndex = v;
            }
        }
        resident[victimIndex] = page;
    }
    return faults;
}
int main() {
    std::vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
    int hits = 0;
    int faults = optimal(refs, 3, hits);
    std::cout << faults << " faults, " << hits << " hits\n"; // 7 faults, 6 hits
    return 0;
}

import java.util.ArrayList;
import java.util.List;
public class OptimalPageReplacement {
    /** Evicts the resident page whose next use is furthest ahead. */
    static int[] optimal(int[] refs, int frames) {
        List<Integer> resident = new ArrayList<>();
        int faults = 0;
        int hits = 0;
        for (int i = 0; i < refs.length; i++) {
            int page = refs[i];
            if (resident.contains(page)) {
                hits++;
                continue;
            }
            faults++;
            if (resident.size() < frames) {
                resident.add(page);
                continue;
            }
            int victimIndex = 0;
            int bestDistance = -1;
            for (int v = 0; v < resident.size(); v++) {
                int distance = Integer.MAX_VALUE;
                for (int j = i + 1; j < refs.length; j++) {
                    if (refs[j] == resident.get(v)) {
                        distance = j;
                        break;
                    }
                }
                if (distance > bestDistance) {
                    bestDistance = distance;
                    victimIndex = v;
                }
            }
            resident.set(victimIndex, page);
        }
        return new int[] {faults, hits};
    }
    public static void main(String[] args) {
        int[] refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
        int[] result = optimal(refs, 3);
        System.out.println(result[0] + " faults, " + result[1] + " hits");
    }
}

Watch it run

Step through it

Running on refs 7,0,1,2,0,3,0,4,2,3,0,3,2 · 3 frames

Output

Why OPT Cannot Be Implemented

The obstacle is not engineering difficulty but information. Choosing the page used furthest ahead requires the future reference string, and at the moment of the fault that string does not yet exist — it depends on branches the program has not taken and input it has not read.

Prediction does not rescue it either. A profile from a previous run tells you what that run did, and a different input takes different branches. Real workloads are input-dependent by nature, which is why practical algorithms use the past as a proxy for the future: LRU bets on temporal locality, and clock approximates LRU using a hardware bit.

There is one narrow exception. When the entire access sequence genuinely is known ahead of time — a compiler scheduling register spills, a database executing a fixed query plan, a batch job over a known file — OPT-style lookahead becomes computable, and those systems do use it.

Needs future references, which do not exist at decision time
Profiles from previous runs do not transfer across inputs
Practical policies substitute recent past for near future
Computable only where the full sequence is known in advance

What OPT Is Actually For

OPT earns its place as a measuring instrument. Record a reference trace, run OPT over it offline, and you have the minimum fault count that string admits. Compare your real algorithm against it and the number tells you something no isolated fault count can: how much room is left.

That distinction decides where engineering effort goes. If LRU takes 9 faults where OPT takes 7, the entire remaining gain from smarter replacement is two faults — and every bit of it hard to reach. If your algorithm takes 40 against OPT's 7, the policy is broken and worth fixing. Without the floor you cannot tell those two situations apart.

OPT is also immune to Belady's anomaly. It belongs to the class of stack algorithms, whose resident set with N frames is always a subset of the set with N+1 frames, so adding memory can never increase faults. FIFO lacks that property, which is exactly why it can behave perversely.

The four policies on 7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames
Algorithm	Faults	Decision rule	Implementable
OPT	7	Page used furthest ahead	No — needs the future
LRU	9	Least recently used	Only approximately
Clock	≈ LRU	First page with a clear reference bit	Yes — nearly free
FIFO	10	Oldest arrival	Yes — trivially

Offline benchmark: the fault floor for a recorded trace
Tells you whether a policy has 5% or 500% left to gain
A stack algorithm — immune to Belady's anomaly
Standard reference point in OS coursework and cache research