Operating Systems · Virtual Memory
Page ReplacementAlgorithm Simulator
Interactive comparison of all four OS page replacement algorithms with real-time step visualization, performance charts & Belady's Anomaly demo.
FIFO
LRU
LFU
Optimal
Scroll to explore
Simulation Input
3
⚠
Performance Summary
Page fault counts, hit ratios & miss penalties across all algorithms.
Step-by-Step Page Tables
🟢 H = Hit | 🔴 F = Page Fault | Highlighted = newly loaded
Visual Comparison
Cumulative faults over time and per-algorithm fault totals.
📊 Page Faults Comparison
📈 Cumulative Faults Over Time
Export Results
Download a PNG snapshot or full CSV data
💻 Execution Logs
Real-time algorithm trace output — step-by-step frame operations.
Detailed execution trace for all 4 algorithms
os_simulator@ubuntu:~/page-replacement
Algorithm Theory
OS theory, complexity, and real-world applications.
FIFO — First In, First OutEvicts the oldest page in memory.
Simple▼
Core Idea: Queue-based eviction — oldest page leaves first regardless of usage.
Weakness: Susceptible to Belady's Anomaly. No practical OS uses pure FIFO.
Real-world: Simple cache eviction in network routers/message queues.
Weakness: Susceptible to Belady's Anomaly. No practical OS uses pure FIFO.
Real-world: Simple cache eviction in network routers/message queues.
LRU — Least Recently UsedEvicts the page not used for the longest time.
Practical▼
Core Idea: Tracks last-access timestamp. Evicts least-recently-accessed page.
Stack Property: Immune to Belady's Anomaly. Pages with n frames ⊂ pages with n+1 frames.
Real-world: Linux two-list LRU (active/inactive lists). ARM hardware access bits.
Stack Property: Immune to Belady's Anomaly. Pages with n frames ⊂ pages with n+1 frames.
Real-world: Linux two-list LRU (active/inactive lists). ARM hardware access bits.
LFU — Least Frequently UsedEvicts the page with fewest total accesses.
Frequency▼
Core Idea: Counts references per page. Evicts lowest-frequency page (FIFO tiebreak).
Strength: Excellent for hot/cold page patterns.
Weakness: Cache pollution — early-accessed pages persist too long. ARC combines LRU+LFU.
Strength: Excellent for hot/cold page patterns.
Weakness: Cache pollution — early-accessed pages persist too long. ARC combines LRU+LFU.
OPT — Belady's OptimalEvicts the page used farthest in the future. Theoretical optimal.
Optimal▼
Core Idea: Requires future knowledge. Evicts page with farthest next use.
Why it matters: Provably optimal lower bound. Benchmarks all other algorithms.
Real-world: Impossible in OS (no oracle). Compilers/DB query planners can approximate.
Why it matters: Provably optimal lower bound. Benchmarks all other algorithms.
Real-world: Impossible in OS (no oracle). Compilers/DB query planners can approximate.