Skip to main content

Page Replacement Simulator Workshop

Build the simulator once, use it to make several questions concrete.

Retrieval Prompts​

  1. State OPT, FIFO, LRU, and clock in one sentence each.
  2. State Belady's anomaly from memory.
  3. Explain why exact LRU is not implemented in Linux.
  4. State what the reference bit is and what it enables.
  5. Explain why scan-resistant policies (2Q, ARC) exist.

Compare and Distinguish​

Separate these pairs:

  • OPT versus LRU
  • LRU versus clock
  • global replacement versus local replacement
  • Belady's anomaly (FIFO) versus stack property (LRU)

Common Mistake Check​

Identify the error:

  1. "OPT is the policy with the lowest fault rate, so we should use it in production."
  2. "FIFO never outperforms LRU."
  3. "Adding more frames always reduces fault count."
  4. "The working set and the resident set size are the same."
  5. "A policy with a lower miss rate is always better, regardless of implementation cost."

Mini Application​

Build a simulator​

Implement in Python (or Rust / C++) a function:

def simulate(policy: str, frames: int, refs: list[int]) -> dict:
    """
    policy in {"OPT", "FIFO", "LRU", "CLOCK"}.
    frames: number of page frames.
    refs: a sequence of virtual page numbers.
    Returns: {"faults": int, "trace": [(access, hit_or_fault, evicted)]}
    """

Validate against these reference strings from OSTEP Chapter 22:

  1. 1 2 3 4 1 2 5 1 2 3 4 5 with 3 frames.
  2. 1 2 3 4 1 2 5 1 2 3 4 5 with 4 frames. (Check Belady's anomaly for FIFO.)
  3. The "80/20" workload: 80% of references go to 20% of pages. Generate 10,000 references with 100 hot pages and 900 cold pages.
  4. The "no locality" workload: uniformly random references over 1,000 pages.
  5. The looping-sequential workload: 0 1 2 ... 49 0 1 2 ... 49 repeated for a long time, with 40 frames. Predict behavior for each policy before simulating.

For each, produce a small table: policy vs. fault count vs. fault rate.

Plot​

Plot fault rate vs. frame count, from 1 to 100 frames, for each of OPT / FIFO / LRU / CLOCK on at least two of the workloads above. Check:

  • OPT is always lowest or tied.
  • LRU and CLOCK are close on the 80/20 and looping workloads.
  • FIFO shows anomalies on the looping workload.

Extend​

  1. Add an ARC-like policy: two lists (recent and frequent), migrate pages between them. Compare its fault rate to LRU on the 80/20 and scan-resistant workloads.
  2. Add a random replacement policy. Compare fault rate.
  3. Derive a reference string (synthetic, at most 30 references) that produces different fault counts for OPT, LRU, and FIFO at 3 frames, and explain why.

Mini modeling questions​

  1. On your looping-sequential workload (50 pages, 40 frames), what does LRU do? What does the optimal policy do?
  2. Why does random replacement sometimes beat LRU on scan-like workloads?
  3. Describe a workload where LRU has 0% fault rate and FIFO has close to 100%.

Evidence Check​

This workshop is complete only if your simulator:

  • produces the correct OPT, FIFO, and LRU fault counts on the canonical reference strings from OSTEP Chapter 22
  • demonstrates Belady's anomaly under FIFO
  • shows LRU's stack property (fault rate monotonically non-increasing as frames grow)
  • lets you invent your own reference string and predict the fault count within a couple of events

And if you can explain, in one paragraph, why real kernels approximate LRU rather than implementing it exactly.

Read This Only If Stuck​