Page replacement — FIFO, LRU, Clock, Optimal

4.1.16 · Coding › Computer Architecture (Deep)

Page replacement exist kyun karta hai?

WHY it matters: disk access RAM se ~ $1 0^{5} \times$ slower hota hai. Har avoidable page fault millions of cycles cost karta hai. Poora khel hai — diye gaye frames ki sankhya ke liye page faults minimize karna.

Chaar policies (WHAT har ek rakhti hai)

Policy	Woh page evict karta hai jo...	Approximate karta hai	Hardware cost
FIFO	memory mein sabse pehle aaya	kuch nahi (sirf age)	sasta (ek queue)
LRU	least recently use hua	past	mehnga (timestamps)
Clock	"last check ke baad use nahi hua"	LRU, saste mein	ek ref bit/frame
Optimal (OPT)	future mein sabse zyada der baad use hoga	future (impossible!)	crystal ball chahiye

Page faults count karna — universal method

Ek reference string (page numbers ki sequence jo program touch karta hai) aur $F$ frames ke liye:

Figure — Page replacement — FIFO, LRU, Clock, Optimal

Worked Example 1 — FIFO

Reference string: 7 0 1 2 0 3 0 4, 3 frames.

Step	Ref	Frames (oldest→newest)	Fault?	Yeh step kyun?
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 (ab oldest)
7	0	[2,3,0]	✗ fault	evict 1 (oldest) — note karo 0 abhi evict hua tha!
8	4	[3,0,4]	✗ fault	evict 2

Faults = 7. Yeh step kyun (row 7)? FIFO usage ignore karta hai — usne 0 ko step 6 mein sirf isliye bahar phenka kyunki woh purana tha, phir turant uski zaroorat padi. Yahi FIFO ki kamzori hai.

Worked Example 2 — LRU (same string, 3 frames)

Step	Ref	Frames (LRU→MRU)	Fault?	Yeh step kyun?
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	0 ko MRU end pe move karo
6	3	[2,0,3]	✗	evict 1 (LRU)
7	0	[2,3,0]	✓ hit	0 abhi bhi present — LRU ne use rakha!
8	4	[3,0,4]	✗	evict 2 (LRU)

Faults = 6. Row 7 mein LRU ne kyun jeeta: usne track kiya tha ki 0 recently use hua tha, isliye usne kabhi use evict nahi kiya — woh fault bach gaya jo FIFO mein hua tha.

Worked Example 3 — Optimal (same string, 3 frames)

OPT aage dekhta hai aur woh page evict karta hai jo future mein sabse zyada der baad use hoga.

Step	Ref	Frames	Fault?	Kyun (future lookahead)
1–3	7,0,1	[7,0,1]	✗✗✗	fill (3 faults)
4	2	evict 7 (kabhi use nahi hoga) → [0,1,2]	✗	7 sabse zyada door use hoga (kabhi nahi)
5	0	[0,1,2]	✓	present
6	3	evict 1 (sabse zyada door use hoga) → [0,2,3]	✗	future: 0@step7, 1 & 2 kabhi nahi — kabhi nahi use hone wala chunna; tie broken → 1
7	0	[0,2,3]	✓	present
8	4	evict 2 (ya 3, kabhi use nahi hoga) → [0,3,4]	✗	2 sabse zyada door use hoga (kabhi nahi)

Faults = 6 (refs steps 1, 2, 3, 4, 6, 8 pe miss hote hain; steps 5 aur 7 hits hain). Yahan tak ki unbeatable policy bhi 6 baar fault karti hai — lekin koi bhi real policy OPT se better nahi kar sakti. OPT lower bound / benchmark hai.

Clock (Second-Chance) — Budget mein LRU

Mini-example (3 frames, R bits parens mein), ref A B C A D:

Load A,B,C → A(1) B(1) C(1), hand A par.
Ref A → hit, A ka R=1 already.
Ref D: fault, sweep. A(1)→0 set karo, aage badho. B(1)→0 set karo, aage badho. C(1)→0 set karo, aage badho. A(0)→evict A, D(1) daalo. Kyun? Sabko second chance mila; A haara kyunki saare bits clear hone ke baad use pehle check kiya gaya.

Belady's Anomaly — FIFO ka sharmnaak raaz

Flashcards

Page fault kya hai?

Ek aisi page ka reference jo currently physical frame mein nahi hai, jis se disk se load karna padta hai (aur possibly ek eviction bhi).

FIFO kaunsa page evict karta hai?

Woh jo memory mein sabse zyada der se hai (earliest arrival), usage chahe kuch bhi ho.

LRU kaunsa page evict karta hai?

Woh jo least recently used hai (last access ke baad sabse zyada time beet gaya).

OPT kaunsa page evict karta hai?

Woh page jiska next use future mein sabse zyada door hai — optimal lekin unrealizable (future chahiye).

OPT ko use kyun karte hain agar implement nahi ho sakta?

Ek theoretical lower bound / benchmark ke roop mein real policies judge karne ke liye.

Kya OPT hamesha LRU se strictly beat karta hai?

Nahi — OPT ≤ har policy hai, lekin tie bhi kar sakta hai (jaise dono '7 0 1 2 0 3 0 4', 3 frames par 6 score karte hain).

Clock ko per frame hardware ka kaunsa ek piece chahiye?

Ek reference bit (R).

Clock mein, jab hand ko R=1 mile toh kya hota hai?

R=0 set karo (second chance) aur evict kiye bina hand aage badhaao.

Clock mein, jab hand ko R=0 mile toh kya hota hai?

Us page ko evict karo, nayi page install karo, hand aage badhaao.

Belady's Anomaly kya hai?

FIFO ke liye, zyada frames add karne se page faults ki sankhya badh sakti hai.

Kaunsi policies Belady's Anomaly se immune hain aur kyun?

LRU aur OPT — ye stack algorithms hain (k-frame contents ⊆ (k+1)-frame contents).

Fault rate formula?

(number of page faults) / (number of references).

Clock LRU ko achhi tarah approximate kyun karta hai?

Frequently-referenced pages R=1 rakhte hain aur sweeps mein survive karte hain, "recently used" ko mimic karte hue, sirf 1 bit use karke per-access timestamps ki jagah.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek chhoti si desk jisme sirf 3 kitaabein fit hoti hain, lekin aapko baar baar door rakhi shelf se kitaabein chahiye. Jab bhi aap door ki kitaab lete hain, time waste hota hai, aur agar desk full hai toh ek kitaab wapas rakhni padti hai. Kaunsi? FIFO = woh kitaab wapas rakho jo desk par sabse zyada der se thi (chahe aapne abhi padhaa ho — bewakoofi!). LRU = woh kitaab wapas rakho jise aapne sabse zyada time se nahi khola (smart). Clock = har kitaab par ek sticky note lagao jab aap padhte ho; jab space chahiye, har kitaab se ek sticky note hataate hue ghoom, aur pehli kitaab jis par koi sticky nahi hai woh wapas chali jaati hai. OPT = ek jyotishi aapko batata hai kaunsi kitaab aapko sabse zyada der tak nahi chahiye, aur aap wahi wapas rakhte ho — perfect, lekin jyotishi real nahi hote.

Connections

Virtual Memory & Paging — page replacement sirf isliye hota hai kyunki demand paging hai.
TLB & Address Translation — reference bit R page-table entries ke paas rehta hai.
Cache Replacement Policies — cache level par bhi wohi FIFO/LRU/Clock ideas.
Thrashing & Working Set Model — bahut zyada faults ⇒ thrashing; working set frame needs bound karta hai.
Belady's Anomaly — non-stack algorithms ki pathology.
Locality of Reference — woh assumption jo LRU/Clock ko kaam karvaati hai.