Working set model, thrashing — Hinglish notes

4.1.17 · Coding › Computer Architecture (Deep)

YEH concept exist kyon karta hai?

Problem: Physical RAM finite hai, lekin virtual memory paging ki wajah se pretend karti hai ki woh infinite hai. OS decide karta hai ki kaun se pages RAM mein rehte hain. Agar woh galat guess kare, toh har memory access ek disk access ban jaati hai (ek page fault), aur disk RAM se ~ $1 0^{5}$ – $1 0^{6}$ × slower hoti hai.

Woh observation jo hume bachata hai: Programs apni saari memory uniformly nahi touch karte. Woh principle of locality follow karte hain:

Temporal locality — abhi use hua page jald hi dobara use hone ki sambhavna hai (loops, hot variables).
Spatial locality — agar aap address $x$ touch karte ho, toh jaldi hi $x + 1$ touch karoge (arrays, instruction streams).

Toh kisi bhi instant mein ek program ko sirf ek mutthi bhar pages "live" chahiye hote hain. Working set model us mutthi ko quantify karta hai taaki OS frames intelligently allocate kar sake.

Working set KYA hai?

$Δ$ = working-set window size (memory references mein measure hoti hai, seconds mein nahi).
$∣ W (t, Δ) ∣$ = working set size = frames ki number jo process ko abhi chahiye.

$∣ W ∣$ compute kaise karte hain? — ek worked trace

Reference string (har number = ek touched page): $2615777516234 \dots$ $Δ = 5$ lo (last 5 references dekhna including current).

$t$	ref	last-5 window	$W (t, 5)$	$∣ W ∣$
5	7	2 6 1 5 7	{2,6,1,5,7}	5
6	7	6 1 5 7 7	{6,1,5,7}	4
9	1	7 7 5 1 _	{7,5,1}	3
11	2	1 6 2 _ _	{1,6,2}	3

Yeh step kyon? Jab references repeat hote hain (7s ka run), distinct pages ki count girती है — locality high hai, kam frames chahiye. Jab naye pages stream in hote hain (end mein phase change), $∣ W ∣$ phir se badhta hai.

Allocation rule (OS isko KAISE use karta hai)

Maano $D = \sum_{i} ∣ W_{i} ∣$ = total demand = saare runnable processes ke working-set sizes ka sum. Maano $m$ = available physical frames ki number.

Thrashing precisely KYA hai?

Page-Fault-Frequency (PFF): practical control

Exact working sets compute karne ki jagah (expensive), do thresholds se fault rate bound karo:

Worked example 2 — kya yeh set thrash karega?

Teen processes, frames $m = 12$ . $∣ W_{A} ∣ = 5, ∣ W_{B} ∣ = 4, ∣ W_{C} ∣ = 6$ .

Step 1: $D = 5 + 4 + 6 = 15$ . Kyon? Live demands sum karo. Step 2: Compare karo: $15 > 12$ ⇒ thrashing. Kyon? Demand supply se zyada hai. Step 3 (fix): $C$ ko suspend karo. Naya $D = 9 \leq 12$ . $C$ kyon? Ise remove karna sabse zyada free karta hai aur $D$ ko $m$ se comfortably neeche laata hai, dusron ke liye slack chhod ke. System ab A aur B cleanly run karta hai; C tab resume karta hai jab ek working set fit ho.

Common mistake Steel-man: "Idle CPU use karne ke liye bas aur processes add karo."

Kyon sahi lagta hai: Classic multiprogramming logic — idle CPU wasteful hai, toh I/O overlap karne ke liye aur kaam load karo. Non-thrashing loads ke liye yeh sahi hai aur isliye hum multiprogram karte hain. Kyon yahan catastrophically galat hai: CPU idle hai isliye ki sab page faults ka intezaar karte hue block hain, is wajah se nahi ki koi kaam nahi hai. Ek process add karna aur frames chheenta hai, sabka resident set chhhota karta hai, fault rate badhata hai, CPU use aur girta hai → scheduler ek aur process add karta hai. Positive feedback se collapse. Fix: Regime detect karo (PFF high / $D > m$ ) aur load hatao (ek process suspend karo). High paging ke dauran low CPU utilization ko over-load ka symptom maano, under-load ka nahi.

Recall Feynman: 12-saal ke bacche ko explain karo

Socho tum ek tiny desk (RAM) pe homework karte ho lekin apni saari books dusre kamre mein shelf (disk) pe rakhte ho. Tumhe sirf woh kuch books chahiye jo tumhare abhi ke chapter ke liye hain — woh tumhara working set hai. Agar tum aur tumhare siblings desk pe itna crowd karo ki kisi ke chapter-books fit nahi ho, toh sab shelf ke paas baar-baar daudne lagte hain aur koi actually kuch likhta nahi. Woh endless daudna thrashing hai. Smart move hai ki ek baccha desk chhode taaki baaki finally kaam kar sakein.

Active Recall

What is the working set

W (t, Δ)

Virtual time

t

pe khatam hone wale last

Δ

memory references mein ek process ne jo distinct pages reference kiye, unka set.

What does

∣ W (t, Δ) ∣

represent?

Frames ki number jo process ko abhi heavy faulting ke bina run karne ke liye chahiye.

In what units is the working-set window

Δ

measured?

Memory references (virtual time) mein, seconds mein nahi.

State the thrashing condition.

Agar total demand

D = \sum_{i} ∣ W_{i} ∣

available frames

m

se zyada ho, toh system thrash karta hai.

What principle makes the working set a good predictor?

Locality of reference (temporal + spatial): recently/nearby-use kiye gaye pages jald hi use hone ki sambhavna hoti hai.

Define thrashing.

Ek state jahan ek process executing se zyada time paging (faults service karne) mein bitata hai, CPU utilization collapse kar deta hai.

Why does naively adding processes worsen thrashing?

Low CPU use isliye hoti hai ki sab fault kar rahe hain; zyada processes frames chheente hain, fault rate badhate hain, aur CPU use aur girte hain — positive feedback.

What is the OS fix for thrashing?

Ek puri process ko suspend/swap out karo taaki

D \leq m

ho jaye.

What does the Page-Fault-Frequency (PFF) scheme do when

f > U

Process bahut zyada fault kar raha hai — use aur frames do.

What does PFF do when

f < L

Process ke paas surplus frames hain — ek reclaim karo.

Why is

Δ

too large bad?

Yeh stale pages ko resident rakhta hai, working set over-estimate karta hai aur frames waste karta hai, multiprogramming ghataata hai.

Connections

Demand Paging — working set decide karta hai kaun se pages resident rakhne hain.
Page Replacement Algorithms — LRU/Clock working set approximate karte hain.
Locality of Reference — woh empirical law jis par poora model depend karta hai.
Multiprogramming Degree — $\sum ∣ W_{i} ∣ \leq m$ se bounded hai.
TLB and Caches — same locality principle, chhote scale par.
Page Fault Handling — faults woh events hain jo PFF measure karta hai.