Visual walkthrough — Memory allocation — contiguous (first-fit, best-fit, worst-fit)

4.2.23 · D2 · Coding › Operating Systems › Memory allocation — contiguous (first-fit, best-fit, worst-f

Hum ek running scenario use karte hain (parent ka Worked Example 1):

• Holes address order mein: $A=100,B=500,C=200,D=300,E=600$ (sab KB mein).
• Requests arrival order mein: $P_1=212,P_2=417,P_3=112,P_4=426$ (KB).

Step 1 — Shelf draw karo aur har piece ko naam do

KYA. RAM ek lamba horizontal strip hota hai. Dark bars woh memory hain jo doosre programs ne pehle se use ki hui hai; unke beech ke light bars holes hain — free space ke unbroken stretches. Har hole ko ek letter aur KB mein uski size se label karte hain.

KYUN. Jo bhi algorithm hum padhenge woh exactly ek kaam karta hai: yeh holes ki list dekhta hai aur ek choose karta hai. Toh jedani bhi state matter karti hai woh hai "kaun se holes hain, kis order mein, kis size par." Choose karne se pehle, hume shelf padhni aani chahiye.

PICTURE. Neeche strip dekho. Left se right padhte hue (yeh direction address order hai — left par low address, right par high address) free holes $A,B,C,D,E$ hain. Unki sizes unke andar likhi hain. "Address order" shelf par simply physical left-to-right order hai — yaad rakho, kyunki first-fit exactly isi order mein scan karta hai.

Step 2 — Ek placement: chunk kaatna aur leftover chhodna

KYA. Request $s$ lo, size $H$ wala ek hole choose karo jisme $H\ge s$ ho, aur program ko us hole ke left end par rakho. Hole do parts mein split hota hai: program (size $s$) aur ek naya chhota hole (size $H-s$).

KYUN. Yeh atomic move hai jo har rule perform karta hai; rules sirf kaunsa $H$ choose karte hain isme differ karte hain. Ek cut samjho aur teeno algorithms samajh lo — woh sirf teen answers hain "kaunsa $H$?" ke.

PICTURE. Figure mein, size $H$ ka teal hole orange knife se $s$ position par apne left edge se slice hota hai. Knife ke left ki taraf used ho jaati hai; knife ke right ki taraf (plum sliver, width $H-s$) ek naya hole ban jaata hai.

$\underset{\text{naya tiny hole}}{\underbrace{\text{leftover}}}=\underset{\text{hole jo hum kaate}}{\underbrace{H}}-\underset{\text{program size}}{\underbrace{s}}$

• Agar $H-s=0$: knife exactly right edge par padti hai — hole bilkul gayab ho jaata hai.
• Agar $H-s>0$: ek real sliver bachta hai, address (hole ka base $+s$) par baitha.
• Agar $H<s$: illegal — knife hole ki right edge se aage kat jaati. Yeh hole candidate hi nahi hai.

Step 3 — First-fit chalta hai: pehle fit hone wale hole par ruk jao

KYA. Har request ke liye, holes ko address order mein scan karo ($A\to B\to C\to D\to E$) aur sabse pehle aise hole par ruko jiska size $\ge s$ ho. Wahan cut karo.

KYUN. Kyunki hum jaldi ruk jaate hain, first-fit sabse fast rule hai: average par yeh sirf pehle kuch holes hi touch karta hai. First-fit har hole jo visit karta hai use test karta hai (kya $\text{size}(h_i)\ge s$ hai?), lekin woh candidates ko ek doosre se compare nahi karta — jis moment ek pass kare, hum commit kar lete hain. Yahi early stop uski speed ka source hai.

PICTURE. Green check mark wahan hai jahan scan ruka; grey crosses woh holes hain jinhe skip kiya (too small) ya kabhi reach hi nahi kiya. $P_1=212$ dekho: yeh $A=100$ par step karta hai (cross, $100<212$), $B=500$ par land karta hai (check), aur cut karta hai — $B=288$ bachta hai.

Full run:

• $P_1=212$: $A=100$ ✗, $B=500$ ✓ → leftover $B=288$.
• $P_2=417$: $A,B=288,C=200,D=300$ sab too small, $E=600$ ✓ → leftover $E=183$.
• $P_3=112$: $A=100$ ✗, $B=288$ ✓ → leftover $B=176$.
• $P_4=426$: holes ab $A=100,B=176,C=200,D=300,E=183$ hain — koi bhi $\ge 426$ nahi. $P_4$ FAILS.

Step 4 — Best-fit chalta hai: sabse tight hole choose karo

KYA. Har request ke liye, sab holes scan karo, har candidate jo size $\ge s$ ho use collect karo, aur sabse chhota aisa candidate choose karo — sabse tight fit.

KYUN. Tight fit is step mein sabse chhota possible leftover kaata hai, toh intuitively yeh "abhi kam waste karta hai." Price: hume confirm karne ke liye ki hum sabse chhota mile, poori free list scan karni padti hai — first-fit se slow.

PICTURE. $P_1=212$ ke liye candidates ($\ge 212$) hain $B=500,D=300,E=600$; unme sabse chhota, $D=300$, plum mein glow karta hai (chosen), sirf $88$ bachta hai. Compare karo first-fit se, jisne bada $B=500$ pakda aur $288$ waste kiya.

Full run:

• $P_1=212$: candidates $\{B=500,D=300,E=600\}$ → sabse chhota $D=300$ → leftover $88$.
• $P_2=417$: candidates $\{B=500,E=600\}$ → sabse chhota $B=500$ → leftover $83$.
• $P_3=112$: candidates $\{C=200,E=600\}$ (note $D=88<112$, $B=83<112$) → sabse chhota $C=200$ → leftover $88$.
• $P_4=426$: candidate $\{E=600\}$ → $E$ → leftover $174$. Chaaron succeed karte hain.

Step 5 — Worst-fit chalta hai: sabse choda hole choose karo

KYA. Har request ke liye, sab holes scan karo aur sabse bada choose karo (chahe woh $s$ se kitna bhi bada ho).

KYUN. Umeed yeh hai: sabse bade hole mein se $s$ kaatne ke baad sabse bada possible leftover bachega, jo "reusable" rahega. Khatre ki baat, jo picture reveal karti hai, yeh hai ki tum apne bade holes pehle kha jaate ho — toh ek badi future request ke liye kuch nahi bachta.

PICTURE. $P_1=212$ ke liye har hole candidate hai (sab widest compare kiye ja sakte hain); sabse tall bar $E=600$ choose hota hai aur $388$ tak shrink ho jaata hai. Notice karo $E$ ko do baar nibble hote hue — end mein $P_4$ ke liye koi bada hole nahi bachta.

Full run:

• $P_1=212$: largest $E=600$ → leftover $388$.
• $P_2=417$: largest $B=500$ → leftover $83$.
• $P_3=112$: ab largest $E=388$ → leftover $276$.
• $P_4=426$: holes $A=100,B=83,C=200,D=300,E=276$ — largest $D=300<426$ hai. $P_4$ FAILS.

Step 6 — Degenerate cases (reader ko kabhi stranded mat chhodho)

KYA. Woh corners jo running example ne hit nahi kiye. Har ek ek legal input hai jo algorithm ko handle karna padega.

KYUN. Ek rule jo tum sirf "nice" inputs par samajhte ho woh real workloads par surprise karega. Yeh rahi chaar edges.

PICTURE. Chaar mini-shelves, ① ② ③ ④ labelled top se bottom, neeche chaar numbered cases se match karte hue:

1. ① Exact fit ($H=s$): leftover $=0$. Hole bilkul gayab ho jaata hai — koi sliver nahi, is step se koi fragmentation nahi. Sabse achha possible outcome.
2. ② Koi hole fit nahi hota ($\text{size}(h_i)<s$ har $i$ ke liye): request fail hoti hai chahe total free space ${\sum }_i\text{size}(h_i)\ge s$ ho. Do 30 KB holes ek 50 KB program host nahi kar sakte — contiguity splitting forbid karta hai. (Yeh external fragmentation ka kaatna hai.)
3. ③ Zero-size request ($s=0$): kisi bhi hole se trivially satisfiable; kuch nahi badalta — ek well-behaved allocator immediately return karta hai.
4. ④ Ties (do holes equally good): best-fit aur worst-fit ties ko address order se break karte hain (lowest first), first-fit ke scan direction se match karte hue — ek convention hai, lekin ek fixed convention, toh results reproducible hain.

Ek-picture summary

Neeche, teeno rules same request $P_1=212$ ka saamna same starting shelf par karte hain. Corner mein ek legend har arrow ke color ko uske algorithm se map karta hai: orange → first-fit ($B$ pakadta hai, pehla jo fit ho), plum → best-fit ($D$ pakadta hai, tightest), teal → worst-fit ($E$ pakadta hai, widest). Har arrow apne target ke paas words mein bhi labelled hai, toh mapping kabhi sirf color par depend nahi karti — ek image mein poora chapter.

Active Recall

Connections

• Parent topic (Hinglish)
• Fragmentation — in cuts se bache slivers external fragmentation hain.
• Compaction — allocated blocks ko saath slide karta hai taaki bikhre leftovers merge ho sakein.
• Free List Management — OS hole list ko kaise store aur scan karta hai jo tumne yahan dekhi.
• Paging — woh contiguity requirement hata deta hai jisne corner case fail karaya.
• Segmentation — variable-size contiguous chunks, har segment ke liye same placement rules.
• Buddy System — ek alag splitting scheme jo leftover sizes bound karta hai.