🔄

Page Replacement — FIFO, LRU, Optimal & Thrashing

When RAM is full and a new page must come in, which page gets evicted? See FIFO, LRU and Optimal traced frame-by-frame on the same reference string, why adding frames can hurt FIFO (Belady's anomaly), and how too many processes tip a system into thrashing — with fully animated traces and two worked numericals.

FIFO · LRU · OPT Belady's Anomaly Thrashing 2 Numericals

Press Next → or use ← → arrow keys

SECTION 01

The Problem — A Full Counter

🥐 REAL-WORLD ANALOGY · THE BAKERY DISPLAY

Only So Much Counter Space

A bakery has room to display only a handful of trays at the front counter, but bakes dozens of kinds in back. When a customer asks for something not on display, a staffer fetches it — but first has to pull a tray off the counter to make room. Pull the wrong one and the next customer wants exactly what you just removed, so you fetch again. Choosing which tray to remove is the whole game.

🧠

The Replacement Question

When a page fault hits and every frame is occupied, the OS must evict a victim page to free a frame. A good page-replacement algorithm removes the page least likely to be needed soon — because every wrong choice becomes another slow disk fault.

SECTION 02 · DIAGRAM

The Replacement Procedure — Six Steps

🧽

The Dirty-Bit Shortcut

Every frame carries a dirty bit. If the victim was only read since it loaded, its disk copy is still valid — the OS can skip the write-back and just overwrite it, turning a two-I/O eviction into one. Clean victims are cheaper to evict, so good algorithms prefer them when they can.

SECTION 03 · DIAGRAM

FIFO — Evict the Oldest Arrival

📥

Simple, but Blind

FIFO keeps a queue of arrival order and always evicts the oldest page — cheap to implement, no per-access bookkeeping. But "oldest" isn't "least useful": a heavily-used page loaded early gets evicted anyway. On the string 7 0 1 2 0 3 0 4 2 3 with 3 frames, FIFO takes 9 faults.

SECTION 04 · DIAGRAM

Belady's Anomaly — More Frames, More Faults

🤯

Intuition Betrayed

You'd expect more RAM to only ever help. But with FIFO, giving the process a 4th frame raises the fault count from 9 to 10 on this string. FIFO isn't a "stack algorithm", so its frame sets don't nest as frames grow — the anomaly Belady discovered. LRU and OPT never suffer it.

SECTION 05 · DIAGRAM

LRU — Evict the Least Recently Used

🕒

The Past Predicts the Future

LRU evicts the page unused for the longest time, betting that recently-used pages will be used again (locality). It needs per-access bookkeeping — timestamps or a stack — but pays off: on the same string it takes 8 faults, one better than FIFO, and it never hits Belady's anomaly.

SECTION 06 · DIAGRAM

Optimal — Evict What's Needed Farthest Away

🔮

The Unbeatable Benchmark

Optimal evicts the page that will be referenced farthest in the future — provably the fewest faults possible (6 here). It needs to see the future, so it can't be built for real, but it's the yardstick: every practical algorithm is measured by how close it gets to OPT.

SECTION 06 · DIAGRAM

Same String, Three Verdicts

🏁

FIFO 9 · LRU 8 · OPT 6

On identical input, FIFO is 50% worse than Optimal and LRU is 33% worse. LRU lands closest to the unreachable ideal — which is exactly why real kernels approximate LRU rather than settle for FIFO's simplicity.

NUMERICAL 1

Full Trace — 3 Frames

Reference string 7 0 1 2 0 3 0 4 2 3, 3 frames. Frame set after each reference (fault marked ✱).

Ref	7	0	1	2	3	0	4	2	3	Faults
FIFO	7✱	0✱	1✱	2✱	3✱	0✱	4✱	2✱	3✱	9
LRU	7✱	0✱	1✱	2✱	3✱	0	4✱	2✱	3✱	8
OPT	7✱	0✱	1✱	2✱	3✱	0	4✱	2	3	6

🧮

Where They Diverge

All three fault on the first four cold references and hit on the second 0. They part ways after: LRU saves a fault by keeping 0 resident at ref 7; OPT saves more by foreseeing that 2 and 3 return, keeping them for the final two hits — 9, 8, 6.

NUMERICAL 2

LRU Walkthrough — A Second String

🧮

Reference String 4 1 2 4 5 3 4 1 2 5 · LRU · 3 Frames

The two hits land on the repeated 4s (refs 4 and 7), which LRU keeps resident because they were used recently. Every other reference misses, for 8 faults out of 10. Notice at the last step LRU evicts 4 — now the least-recently-used — to bring in 5.

SECTION 09 · DIAGRAM

Thrashing — The Performance Cliff

📉

Past the Peak, Adding Work Subtracts Throughput

More processes normally means better CPU use — until their combined working sets no longer fit in RAM. Then every process constantly faults, stealing frames from every other, and the system spends more time paging than computing. CPU utilisation collapses off a cliff — that's thrashing.

SECTION 10

The Working-Set Model — Denning

🎯 Keep Every Process's Working Set Resident

MeasureFor each process, count its working set WSSᵢ — the unique pages it referenced within a recent window Δ.

SumTotal demand D = Σ WSSᵢ across all running processes.

CompareIf D ≤ available frames, the system is safe; if D > frames, thrashing is imminent.

ReactSuspend a process (swap it out) until D fits — freeing frames so the rest stop faulting.

📊

Or Watch the Fault Rate Directly

An alternative is Page-Fault Frequency control: set an upper and lower fault-rate threshold. If a process faults too often, give it more frames; if it faults rarely, take some away. Either way the goal is the same — hold each process's resident set near its working set so faults stay rare.

SECTION 11

Choosing an Algorithm

Algorithm	Implementation	Overhead	Faults	Belady's Anomaly
FIFO	Queue of arrival order	Very low	Highest (poor)	Yes
LRU (true)	Timestamps / stack per access	High	Close to OPT	No (stack algorithm)
LRU approx.	Reference bits · clock algorithm	Medium	Good	No
Optimal	Requires future knowledge	N/A	Provably minimum	No

⚙️

Why Real Kernels Approximate LRU

True LRU's per-access bookkeeping is too costly in hardware, and FIFO is too weak (and anomaly-prone). The sweet spot is approximate LRU — the clock (second-chance) algorithm using a reference bit — cheap enough for hardware yet nearly as good as true LRU. OPT stays a benchmark only.

SECTION 12

Replacement in the Real World

🐧

Linux Two-List LRU

active / inactive

Linux keeps an active and an inactive list, moving pages between them by access — an efficient LRU approximation, not a costly true LRU.

🕰️

Clock / Second-Chance

reference bit

A circular scan gives each page a "second chance" if its reference bit is set, clearing it and moving on — approximate LRU in one cheap sweep.

🪟

Windows Working Sets

per-process

Windows tracks a working set per process and trims it under memory pressure — Denning's model shipping in production.

🧽

Dirty-Bit Write-Back

clean vs dirty

Clean victims are evicted with no disk write; only modified pages are written back — halving the cost of many evictions.

📱

Mobile Memory Pressure

Android · iOS

Low-memory killers and page reclaim evict cold pages first, keeping the foreground app's working set resident.

🗃️

Database Buffer Pools

LRU-K · ARC

Databases run their own replacement (LRU-K, ARC) over cached disk pages — the same problem, one layer up.

SECTION 13

Eight Rules for Page Replacement

🔄 PAGE REPLACEMENT · CHECKLIST

1

On a fault with RAM full, a victim is evicted — the whole art is choosing the right one.

2

FIFO evicts the oldest arrival: cheapest to build, but poorest fault count and prone to Belady's anomaly.

3

Optimal evicts the page used farthest in the future — provably minimal faults, but a benchmark only.

4

LRU evicts the least-recently-used page; it lands closest to OPT and never suffers Belady's anomaly.

5

Real systems use approximate LRU — reference bits and the clock algorithm — to dodge LRU's cost.

6

The dirty bit lets a clean victim be dropped without a disk write — cheaper evictions.

7

Thrashing strikes when total working sets exceed RAM: paging overwhelms computing, throughput collapses.

8

The working-set model (D = Σ WSSᵢ) and page-fault-frequency control keep the fault rate low.

FINAL

Choosing the Right Victim

FIFO 9Oldest arrival

LRU 8Least recently used

OPT 6Provable minimum

9 → 10Belady's anomaly

D = ΣWSSBeat thrashing

🎯

You Now Understand Page Replacement

From the six-step procedure and the dirty-bit shortcut, through FIFO, LRU and Optimal traced frame-by-frame, Belady's anomaly, thrashing and the working-set model — you can run any replacement algorithm by hand and reason about why a system slows to a crawl.

📚

The Memory Story, Complete

Page replacement is the last piece of the memory-management arc — from contiguous allocation and paging, through virtual memory and demand paging, to keeping the fault rate low here. Next the course turns to storage and file systems, where these pages finally meet the disk.

🔄 End of tutorial · Press ← to review, or click Restart