∿ExploreSims
ExploreSims / Computer Science & Technology / Operating Systems / Page Replacement Algorithms (LRU, FIFO, Clock)
Premium experiment • virtual-memory policy

COMPUTER SCIENCE & TECHNOLOGY • OPERATING SYSTEMS

Page Replacement Algorithms (LRU, FIFO, Clock)

Run the same memory-reference string through three replacement policies and compare frame contents, hits, faults and eviction choices.

● VIRTUAL MEMORYFrames and reference timeline
Hits
Faults
Hit rate
Progress

Reasoning inspector

live internal state
Policy—
Frames—
Current page—
Replacement frame—
Final hits—
Final faults—
Final hit rate—
FIFO / LRU / Clock—

Eviction policy matters

FIFO, LRU and Clock can retain different pages after the same fault, changing whether future references become hits or misses.

LEARN WITH THE SIMULATION

Understand Page Replacement Algorithms (LRU, FIFO, Clock) by experimenting.

START HERE

Virtual memory gives programs the illusion of a large address space while only some pages are resident in physical frames. When a referenced page is absent and every frame is occupied, the operating system needs a replacement policy. This laboratory steps through one reference string with FIFO, LRU and Clock, exposing frame contents, page hits, page faults and the exact moment each policy makes a different eviction choice.

BUILD THE IDEA

What you should understand first

  • Distinguish a page hit from a page fault and identify when replacement is required.
  • Compare FIFO insertion order, LRU recency and Clock second-chance behavior on the same workload.
  • Explain why two policies with identical frame counts can produce different future hit rates.
  • Use the full-trace comparison to reason about policy quality instead of judging one isolated eviction.

TRY IT YOURSELF

Can the locally reasonable eviction choice lead to a worse result later in the trace?

  1. Run the default sequence with three frames using FIFO and note the final fault total.
  2. Reset and repeat with LRU, watching the frame chosen on each fault.
  3. Run Clock and compare where its reference-bit approximation agrees with or diverges from LRU.
  4. Change frame count while keeping the reference string fixed and observe whether policy rankings stay the same.
Read the visual:

Eviction decisions change the resident set, and the resident set changes whether future references hit. A policy cannot be judged from one replacement in isolation; the full access sequence determines whether keeping or evicting a page was beneficial.

WHY IT WORKS 01

Replacement policy changes the future state of memory

A page fault is not just a one-time penalty. The selected victim determines which pages remain resident after the fault, so it changes the probability of later hits. That is why two policies processing an identical reference string can diverge more and more after the first different eviction choice.

WHY IT WORKS 02

LRU uses recency; Clock approximates recency cheaply

Exact LRU needs enough information to identify the least recently referenced resident page. Clock instead stores one reference bit per frame and scans circularly, clearing recently used pages and giving them a second chance. This usually captures useful recency information with less bookkeeping, but its result can differ from exact LRU.

WHY IT WORKS 03

More frames are not a universal monotonic guarantee for FIFO

Many learners expect that adding memory must always reduce faults. That intuition is true for stack algorithms such as LRU but not for FIFO. Certain reference strings produce Belady's anomaly, where FIFO experiences more faults with more frames. The simulator makes it possible to search for such traces rather than treating the phenomenon as a memorized exception.

DO NOT MIX THESE UP

Common misconception

LRU is not the mathematically optimal policy for every future reference string, and Clock is not exact LRU. More frames also do not make every replacement algorithm strictly better on every possible trace; FIFO famously permits Belady's anomaly. Real systems additionally account for dirty pages, hardware reference bits, multiple processes, working sets and storage cost.

PRACTICE CHALLENGE

Can you meet a page-fault target while keeping the reference string fixed?

  • Set a target number of faults in the premium controls.
  • Run the full trace with FIFO, LRU and Clock using the same frame count.
  • Change only frame count or policy until one configuration meets the target.
  • Use the policy comparison in the inspector to explain why the chosen configuration won on this workload.
Reveal the reasoning

A replacement policy is evaluated against a particular reference pattern and frame budget. Meeting the target requires preserving pages that are reused soon enough to turn future accesses into hits. The best policy in this lab is therefore workload-dependent, not a universal property of its name.

MODEL BOUNDARIES

What this simulation assumes

Every simulation simplifies reality or a mathematical system. These are the assumptions and limits to keep in mind while interpreting the results.

Model assumptions

  • The reference string is processed sequentially against a fixed number of initially empty frames.
  • FIFO evicts in insertion order, LRU evicts the least recently referenced resident page, and Clock uses one reference bit per frame.
  • Every missing reference causes exactly one page fault and replacement is instantaneous.

Model limitations

  • Dirty-page writeback costs, process-local versus global allocation, prefetching, TLB behavior and disk latency are omitted.
  • Clock behavior is a teaching implementation of the second-chance policy rather than a kernel-specific variant.

CONNECT IT

Where this matters

  • Virtual-memory management
  • Operating-system performance analysis
  • Replacement-policy education
  • Reasoning about locality and working sets

WORDS THAT MATTER

Key vocabulary

Page fault
Reference to a virtual-memory page that is not currently resident in physical memory.
Frame
Physical-memory slot capable of holding one virtual-memory page.
FIFO
Replacement policy that evicts the resident page that entered memory earliest.
LRU
Replacement policy that evicts the resident page whose most recent reference is farthest in the past.
Clock
Second-chance replacement policy that scans frames using reference bits to approximate recency.
Working set
Collection of pages a process is actively reusing over a recent interval.