Skip to main content

Page Replacement Problem: FIFO, LRU, and Optimal Fault-Counting

Medium

Interview Question: "Given the 20-page reference string [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] and a memory allocation of 3 physical page frames, trace each step and compute total page faults for FIFO, LRU, and Optimal (Bélády's MIN) algorithms. Why is Optimal impossible to implement in practice?"

Problem Specification​

You have 3 physical frames (slots) in RAM, initially empty, and a program that touches pages in this order:

σ=⟨7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1⟩\sigma = \langle 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 \rangle

Every time a page isn't already sitting in one of those 3 slots, that's a page fault — the OS has to fetch it from disk. If it's already there, that's a hit, free. The question is just: when a frame is full and a new page needs a slot, which page do you kick out?

Part 1: FIFO (First-In, First-Out)​

FIFO maintains a strict queue of memory residency. The page that has been in RAM the longest, regardless of how frequently or recently it was accessed, is selected for eviction.

Step-by-Step Trace Table (FIFO)​

StepPage ReqFrame 1Frame 2Frame 3ResultEvicted Victim
177--❌ Fault-
2070-❌ Fault-
31701❌ Fault-
42201❌ Fault7 (Oldest)
50201✅ Hit-
63231❌ Fault0 (Oldest)
70230❌ Fault1 (Oldest)
84430❌ Fault2 (Oldest)
92420❌ Fault3 (Oldest)
103423❌ Fault0 (Oldest)
110023❌ Fault4 (Oldest)
123023✅ Hit-
132023✅ Hit-
141013❌ Fault2 (Oldest)
152012❌ Fault3 (Oldest)
160012✅ Hit-
171012✅ Hit-
187712❌ Fault0 (Oldest)
190702❌ Fault1 (Oldest)
201701❌ Fault2 (Oldest)
  • Total FIFO Page Faults: 15
  • Total FIFO Page Hits: 5
  • Fault Rate: 15 / 20 = 75.0%

Part 2: LRU (Least Recently Used)​

LRU leverages the principle of temporal locality: pages accessed recently are likely to be accessed again soon. The page that has not been referenced for the longest duration of time in the past is evicted.

Step-by-Step Trace Table (LRU)​

StepPage ReqFrame 1Frame 2Frame 3ResultEvicted Victim (Least Recently Used)
177--❌ Fault-
2070-❌ Fault-
31701❌ Fault-
42201❌ Fault7 (Last used at step 1)
50201✅ Hit-
63203❌ Fault1 (Last used at step 3)
70203✅ Hit-
84403❌ Fault2 (Last used at step 4)
92402❌ Fault3 (Last used at step 6)
103432❌ Fault0 (Last used at step 7)
110032❌ Fault4 (Last used at step 8)
123032✅ Hit-
132032✅ Hit-
141132❌ Fault0 (Last used at step 11)
152132✅ Hit-
160102❌ Fault3 (Last used at step 12)
171102✅ Hit-
187107❌ Fault2 (Last used at step 15)
190107✅ Hit-
201107✅ Hit-
  • Total LRU Page Faults: 12
  • Total LRU Page Hits: 8
  • Fault Rate: 12 / 20 = 60.0%

Part 3: Optimal (Bélády's MIN Algorithm)​

Optimal page replacement evicts the page that will not be referenced for the longest duration of time in the future. It is mathematically proven to generate the absolute minimum number of page faults for any given reference string.

Step-by-Step Trace Table (Optimal)​

StepPage ReqFrame 1Frame 2Frame 3ResultEvicted Victim (Furthest Future Use)
177--❌ Fault-
2070-❌ Fault-
31701❌ Fault-
42201❌ Fault7 (Next used at step 18; 0 used at step 5, 1 at step 14)
50201✅ Hit-
63203❌ Fault1 (Next used at step 14; 0 used at step 7, 2 at step 9)
70203✅ Hit-
84243❌ Fault0 (Next used at step 11; 2 used at step 9, 3 at step 10)
92243✅ Hit-
103243✅ Hit-
110203❌ Fault4 (Never used again in reference string!)
123203✅ Hit-
132203✅ Hit-
141201❌ Fault3 (Never used again in reference string!)
152201✅ Hit-
160201✅ Hit-
171201✅ Hit-
187701❌ Fault2 (Never used again in reference string!)
190701✅ Hit-
201701✅ Hit-
  • Total Optimal Page Faults: 9
  • Total Optimal Page Hits: 11
  • Fault Rate: 9 / 20 = 45.0%

Comparative Evaluation Scorecard​

AlgorithmTotal FaultsTotal HitsFault RateImplementable in OS?
Optimal (MIN)91145.0%NO (Theoretical Bound). Requires predicting future memory references.
LRU12860.0%Approximated. True LRU requires expensive hardware counters / stack updates per memory cycle.
FIFO15575.0%YES. Simple queue, but suffers from high fault rates and Bélády's Anomaly.

Why real kernels can't just use Optimal or true LRU​

  1. Optimal needs to see the future. It evicts whatever page won't be used for the longest time — but that means knowing what the program will do next, which no kernel can. It's a useful yardstick, not something you can actually run.
  2. True LRU is too expensive to track exactly. Doing it perfectly means updating a timestamp or re-ordering a linked list on every single memory access — billions of times a second. No CPU wants that overhead.
  3. So kernels approximate LRU with the Clock algorithm instead. Every page gets one reference bit, flipped on by hardware whenever the page is touched. A "clock hand" sweeps through the pages in a circle:
R = 1
give it a second chance
clear the bit, move on
hand sweeps to next page
R = 0
evict this page
hasn't been touched since the last sweep

This gets you roughly 95% of true LRU's accuracy for a fraction of the cost — O(1) per access instead of updating a list every time.

Say this in the interview​

"With 3 frames on this reference string: Optimal gets 9 faults, LRU gets 12, FIFO gets 15. Optimal is the theoretical best — it evicts whatever's needed furthest in the future — but it's impossible to run for real since it requires knowing the future. True LRU is accurate but too expensive to track exactly, so production kernels approximate it with the Clock (second-chance) algorithm instead."

Python Verification: Page Replacement Multi-Algorithm Simulator​

The following executable Python script implements FIFO, LRU, and Optimal page replacement algorithms, verifying the exact fault counts and hit rates across reference strings:

"""
Page Replacement Algorithms Simulator (FIFO, LRU, Optimal)
Verifies:
  - Exact fault counts across 3 frames
  - Hit/Fault classifications per reference step
"""

from typing import List, Tuple

def simulate_fifo(ref_str: List[int], num_frames: int = 3) -> Tuple[int, int]:
    frames: List[int] = []
    faults = 0
    hits = 0

    for page in ref_str:
        if page in frames:
            hits += 1
        else:
            faults += 1
            if len(frames) < num_frames:
                frames.append(page)
            else:
                frames.pop(0)  # Evict oldest
                frames.append(page)
    return faults, hits


def simulate_lru(ref_str: List[int], num_frames: int = 3) -> Tuple[int, int]:
    frames: List[int] = []  # Index 0 is LRU, last index is Most Recently Used
    faults = 0
    hits = 0

    for page in ref_str:
        if page in frames:
            hits += 1
            frames.remove(page)
            frames.append(page)  # Move to MRU position
        else:
            faults += 1
            if len(frames) < num_frames:
                frames.append(page)
            else:
                frames.pop(0)    # Evict least recently used
                frames.append(page)
    return faults, hits


def simulate_optimal(ref_str: List[int], num_frames: int = 3) -> Tuple[int, int]:
    frames: List[int] = []
    faults = 0
    hits = 0

    for idx, page in enumerate(ref_str):
        if page in frames:
            hits += 1
        else:
            faults += 1
            if len(frames) < num_frames:
                frames.append(page)
            else:
                # Find page that will not be used for longest time in future
                future_sub = ref_str[idx + 1:]
                victim = None
                furthest_use = -1

                for f in frames:
                    if f not in future_sub:
                        victim = f
                        break
                    else:
                        next_use = future_sub.index(f)
                        if next_use > furthest_use:
                            furthest_use = next_use
                            victim = f

                frames.remove(victim)
                frames.append(page)
    return faults, hits


def main():
    print("=== Page Replacement Numerical Problem Verification ===\n")
    reference_string = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
    num_frames = 3

    print(f"Reference String: {reference_string}")
    print(f"Total References: {len(reference_string)} | Total Physical Frames: {num_frames}\n")

    f_fifo, h_fifo = simulate_fifo(reference_string, num_frames)
    print(f"FIFO:    {f_fifo} Faults | {h_fifo} Hits | Fault Rate: {(f_fifo / len(reference_string))*100:.1f}%")

    f_lru, h_lru = simulate_lru(reference_string, num_frames)
    print(f"LRU:     {f_lru} Faults | {h_lru} Hits | Fault Rate: {(f_lru / len(reference_string))*100:.1f}%")

    f_opt, h_opt = simulate_optimal(reference_string, num_frames)
    print(f"Optimal: {f_opt} Faults | {h_opt} Hits | Fault Rate: {(f_opt / len(reference_string))*100:.1f}% [Theoretical Bound]")

if __name__ == "__main__":
    main()