Page replacement — FIFO, LRU, Clock, Optimal
WHY does page replacement even exist?
WHY it matters: a disk access is ~ slower than RAM. Each avoidable page fault costs millions of cycles. The whole game is minimizing page faults for a given number of frames.
The four policies (WHAT each one keeps)
| Policy | Evicts the page that... | Approximates | Hardware cost |
|---|---|---|---|
| FIFO | entered memory earliest | nothing (just age) | cheap (a queue) |
| LRU | was used least recently | the past | expensive (timestamps) |
| Clock | "hasn't been used since last check" | LRU, cheaply | one ref bit/frame |
| Optimal (OPT) | won't be used for the longest into the future | the future (impossible!) | needs a crystal ball |
Counting page faults — the universal method
For a reference string (the sequence of page numbers the program touches) and frames:
Worked Example 1 — FIFO
Reference string: 7 0 1 2 0 3 0 4, 3 frames.
| Step | Ref | Frames (oldest→newest) | Fault? | Why this step? |
|---|---|---|---|---|
| 1 | 7 | [7] | ✗ fault | empty frame |
| 2 | 0 | [7,0] | ✗ fault | empty frame |
| 3 | 1 | [7,0,1] | ✗ fault | empty frame |
| 4 | 2 | [0,1,2] | ✗ fault | full → evict 7 (oldest) |
| 5 | 0 | [0,1,2] | ✓ hit | 0 present |
| 6 | 3 | [1,2,3] | ✗ fault | evict 0 (now oldest) |
| 7 | 0 | [2,3,0] | ✗ fault | evict 1 (oldest) — note 0 was just evicted! |
| 8 | 4 | [3,0,4] | ✗ fault | evict 2 |
Faults = 7. Why this step (row 7)? FIFO ignores usage — it threw out 0 in step 6 just because it was old, then immediately needed it again. This blindness is FIFO's weakness.
Worked Example 2 — LRU (same string, 3 frames)
| Step | Ref | Frames (LRU→MRU) | Fault? | Why this step? |
|---|---|---|---|---|
| 1 | 7 | [7] | ✗ | empty |
| 2 | 0 | [7,0] | ✗ | empty |
| 3 | 1 | [7,0,1] | ✗ | empty |
| 4 | 2 | [0,1,2] | ✗ | evict 7 = least recently used |
| 5 | 0 | [1,2,0] | ✓ hit | move 0 to MRU end |
| 6 | 3 | [2,0,3] | ✗ | evict 1 (LRU) |
| 7 | 0 | [2,3,0] | ✓ hit | 0 still present — LRU kept it! |
| 8 | 4 | [3,0,4] | ✗ | evict 2 (LRU) |
Faults = 6. Why LRU won row 7: it tracked that 0 was used recently, so it never evicted it — saving the fault FIFO suffered.
Worked Example 3 — Optimal (same string, 3 frames)
OPT looks forward and evicts the page used furthest in the future.
| Step | Ref | Frames | Fault? | Why (future lookahead) |
|---|---|---|---|---|
| 1–3 | 7,0,1 | [7,0,1] | ✗✗✗ | fill (3 faults) |
| 4 | 2 | evict 7 (never used again) → [0,1,2] | ✗ | 7 used furthest (never) |
| 5 | 0 | [0,1,2] | ✓ | present |
| 6 | 3 | evict 1 (used furthest) → [0,2,3] | ✗ | future: 0@step7, 1 & 2 never again — pick a never-used; tie broken → 1 |
| 7 | 0 | [0,2,3] | ✓ | present |
| 8 | 4 | evict 2 (or 3, never used again) → [0,3,4] | ✗ | 2 used furthest (never) |
Faults = 6 (refs at steps 1, 2, 3, 4, 6, 8 all miss; steps 5 and 7 are hits). Even the unbeatable policy still faults 6 times here — but no real policy can do better than OPT. OPT is the lower bound / benchmark.
Clock (Second-Chance) — LRU on a budget
Mini-example (3 frames, R bits in parens), ref A B C A D:
- Load A,B,C →
A(1) B(1) C(1), hand on A. - Ref A → hit, A's R=1 already.
- Ref D: fault, sweep. A(1)→set 0, advance. B(1)→set 0, advance. C(1)→set 0, advance. A(0)→evict A, put D(1). Why? Everyone had a second chance; A lost because it was checked first after all bits cleared.
Belady's Anomaly — FIFO's embarrassing secret
Flashcards
What is a page fault?
FIFO evicts which page?
LRU evicts which page?
OPT evicts which page?
Why is OPT used if it can't be implemented?
Does OPT always beat LRU strictly?
What single piece of hardware does Clock need per frame?
In Clock, what happens when the hand finds R=1?
In Clock, what happens when the hand finds R=0?
What is Belady's Anomaly?
Which policies are immune to Belady's Anomaly and why?
Fault rate formula?
Why does Clock approximate LRU well?
Recall Feynman: explain to a 12-year-old
Imagine a tiny desk that fits only 3 books, but you keep needing books from a big shelf far away. Every time you grab a far book you waste time, and if the desk is full you must put one book back. Which one? FIFO = put back whichever book has been on the desk longest (even if you just read it — silly!). LRU = put back the one you haven't opened in the longest time (smart). Clock = put a sticky note on each book when you read it; when you need space, walk around removing one sticky note per book, and the first book with no sticky gets returned. OPT = a fortune-teller tells you which book you won't need for the longest, and you return that — perfect, but fortune-tellers aren't real.
Connections
- Virtual Memory & Paging — page replacement only happens because of demand paging.
- TLB & Address Translation — the reference bit R lives near page-table entries.
- Cache Replacement Policies — same FIFO/LRU/Clock ideas at the cache level.
- Thrashing & Working Set Model — too many faults ⇒ thrashing; the working set bounds frame needs.
- Belady's Anomaly — pathology of non-stack algorithms.
- Locality of Reference — the assumption that makes LRU/Clock work.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, RAM ek chhoti si shelf hai jisme sirf kuch hi pages aate hain (frames). Jab program ko koi page chahiye jo shelf pe nahi hai, to page fault hota hai aur OS use disk se laata hai — aur disk RAM se laakhon guna slow hai. Agar shelf full hai to kisi purane page ko nikalna padega: yeh decision lena hi page replacement policy hai. Goal simple hai — minimum page faults.
Chaar policies hain. FIFO: jo page sabse pehle aaya tha use nikaalo, chahe abhi use hua ho ya nahi — isliye yeh bewakoof hai. LRU: jo page sabse lambe time se use nahi hua use nikaalo — yeh maanta hai ki "recent past future ko predict karta hai", aur practical me bahut achha chalta hai. Clock: LRU ka sasta version — har frame pe ek reference bit (R) hota hai, hand circular ghoomta hai, R=1 wale ko ek "second chance" deke R=0 kar deta hai, R=0 wale ko nikaal deta hai. Optimal (OPT): jo page sabse door future me use hoga use nikaalo — yeh perfect hai par real me impossible (future kaun jaanta hai), isliye sirf benchmark ke liye use karte hain. Dhyaan rakho: OPT hamesha LRU se strictly kam faults nahi deta — kabhi-kabhi tie bhi hota hai (jaise iss string pe dono 6 faults).
Ek important trap: log sochte hain "zyada frames matlab kam faults" — par FIFO me ulta ho sakta hai, isko Belady's Anomaly kehte hain. LRU aur OPT (stack algorithms) me yeh kabhi nahi hota. Aur dusra confusion: FIFO arrival time dekhta hai, LRU last-access time — dono "purana" lagta hai par alag cheez hai.
Practice ka tareeka: ek reference string lo, table banao jisme har step pe frames ka state likho aur "Why this step?" pucho — yahi Active Recall + Feynman hai. Pehle khud predict karo kaun nikalega (Forecast), phir verify karo. Faults ko gino, andaaze se mat likho. Isse policies dimaag me pakki baith jaayengi.