Fragmentation — internal vs external, compaction: Visual walkthrough

4.2.24 · D2 · Coding › Operating Systems › Fragmentation — internal vs external, compaction

Shuru karne se pehle, ek word jis par hum baar baar rely karenge:

Step 1 — Ruler neeche rakhna: "allocation" ka matlab kya hai

KYA. Hum memory ki ek bare strip draw karte hain aur uspe equal blocks mark karte hain, har ek $B$ bytes lambi. Abhi kuch bhi use nahi hua.

KYO. Tum wasted space ki baat tab tak nahi kar sakte jab tak dono cheezein ek saath na dekh sako: ek process ko kitni space chahiye versus use kitni space di gayi. Ruler dono ko ek hi scale par dikhata hai.

PICTURE. Figure dekho. Poori strip memory hai. Vertical chalk ticks use equal width $B$ ke blocks mein divide karti hain. Har tick woh jagah hai jahan OS ek naya allocation start kar sakta hai — aur sirf wahi jagah.

Figure — Fragmentation — internal vs external, compaction

Step 2 — Ek block bharna: internal waste kahaan chupta hai?

KYA. Hum ek process ko $S$ bytes ki zaroorat ke saath left mein rakhte hain, jahan $S$ ek block se chhota hai ( $S < B$ ). Woh pehle block ka kuch hissa bharta hai aur ruk jaata hai.

KYO. OS ek block ka hissa nahi de sakta — smallest unit poora block $B$ hai. Toh process ne sirf $S$ maanga tha, lekin use poora block $B$ diya jaata hai. "Diya gaya" aur "chahiye tha" ke beech ka woh gap hi woh waste hai jo hum dhundh rahe hain.

PICTURE. Blue region woh $S$ bytes hai jinhein process use karta hai. Pink region usi block ke andar bacha hua hissa hai — bytes jo process ke paas hain lekin woh kabhi use nahi karega. Woh pink strip hi internal fragmentation hai: waste jo ek allocated block ke andar chupta hai.

given (whole block) B - needed S = wasted tail (pink) B - S

$B$ — poora block jo haath mein diya gaya, kyunki ek block indivisible hai.
$S$ — actually use kiye gaye bytes (blue).
$B - S$ — pink tail; owned but idle. Yeh internal waste hai jab $S < B$ ho is case mein.

Step 3 — Ek bada process: kai blocks aur ceiling

KYA. Ab process bada hai: $S > B$ . Usse kai blocks chahiye. Hum count karte hain kitne.

KYO. Hume upar round karna hai, kabhi neeche nahi — agar ek bhi byte last full block se bahar jaata hai, to hume ek aur poora block lena padta hai. Woh math tool jo "agli poori sankhya tak round up karo" kehta hai woh ceiling function hai, jise $⌈ ⌉$ likhte hain. Hum ceiling (na ordinary rounding, na floor) isliye use karte hain kyunki ek block ka fraction impossible hai.

PICTURE. Process (blue) ko $S$ bytes chahiye. Woh do poore blocks bharta hai aur phir thoda teesre mein ghus jaata hai. Woh spillover poore teesre block ko reserve karne par majboor karta hai. Teesre block mein pink tail phir se internal waste hai.

N = ⌈ \frac{S}{B} ⌉

$\frac{S}{B}$ — kitne blocks ki zaroorat hai, ek possibly-fractional number ke roop mein (yahan $S / B \approx 2.4$ ).
$⌈ ⌉$ — ceiling; yeh $2.4$ ko $3$ tak uthata hai, kyunki woh bacha hua $0.4$ of a block phir bhi ek poora block cost karta hai.
$N$ — result mein aane wala poora number of blocks reserved.

Step 4 — Internal fragmentation formula, poori tarah assemble hui

KYA. Hum Steps 2 aur 3 ko ek formula mein combine karte hain jo kisi bhi size $S$ aur kisi bhi block $B$ ke liye kaam karta hai.

KYO. Hume ek single expression chahiye: total space di gayi minus total space chahiye thi. "Di gayi" hai $N$ blocks har ek $B$ length ki, yaani $N \cdot B$ . "Chahiye thi" hai $S$ . Subtract karo.

PICTURE. Reserved region ke upar bracket $N \cdot B$ hai (teeno blocks). Neeche blue bracket $S$ hai. Pink sliver jo $S$ ke aage jaata hai lekin $N \cdot B$ ke andar rehta hai woh answer hai.

Internal = N \cdot B - S = ⌈ \frac{S}{B} ⌉ B - S

$N \cdot B$ — total bytes reserved (blocks $\times$ block-length).
$S$ — actually use kiye gaye bytes.
Difference — last block mein pink tail; pehle ke poore blocks mein koi waste nahi.

Step 5 — Pieces wapas lena: external waste kahan paida hota hai

KYA. World switch karo. Ab allocation variable-size hai (jaise Segmentation aur Dynamic Memory Allocation mein): har process ko exactly utna hi milta hai jitna woh maangti hai. Hum teen processes A, B, C tightly allocate karte hain, phir B ko free karte hain — ek gap chhodke.

KYO. Variable sizing internal waste khatam kar deti hai (tum exactly $S$ paate ho). Lekin jab processes jaati hain, toh woh beech mein awkward sizes ke holes chodh jaati hain. Allocations ke beech holes ek naya waste hai: external fragmentation.

PICTURE. Top strip: A, B, C tightly packed — koi waste nahi. Bottom strip: B ja chuka hai, A aur C ke beech ek yellow hole chhod ke. Hole free hai, lekin do used blocks ke beech phansa hua hai.

Step 6 — Kaafi free space hai, phir bhi request fail ho jaati hai

KYA. Bahut saare allocate/free cycles ke baad strip Swiss cheese ban jaati hai: 40K, 30K, 50K ke holes. 100K ka naya request aata hai — aur fail hota hai.

KYO. Ek contiguous scheme mein OS ko ek request ek hole mein rakhna hota hai. $40 + 30 + 50 = 120$ K total free hai, lekin sabse bada single hole sirf 50K ka hai. 100K kisi ek hole mein fit nahi hota, toh allocation refuse ho jaata hai bawajood kaafi total free space ke. Yeh external fragmentation ka shudh, pareshaani karne wala chehra hai.

PICTURE. Teen yellow holes apne sizes ke saath. Ek pink 100K request-bar upar float kar raha hai, har hole se chauda — woh kahin land nahi kar sakta.

External fragmentation ratio = 1 - \frac{largest free block}{total free memory}

$largest free block$ — sabse bada single hole ( $50$ K), woh best jo tum ek baar mein actually use kar sako.
$total free memory$ — sab holes ka sum ( $120$ K).
$1 - \frac{50}{120} = 1 - 0.4167 = 0.583$ — आधे से zyada free memory 50K se badi kisi cheez ke liye unusable hai.

Step 7 — Compaction: holes ko ek saath sweep karna

KYA. Hum har used block ko ek end ki taraf slide karte hain. Jaise woh close ranks karte hain, sab chhote holes ek bade free block mein pool ho jaate hain doosre end par.

KYO. Bytes hamesha kaafi the (120K); akela problem yeh tha ki woh scattered the. Compaction geometry fix karta hai, amount nahi: yeh used blocks ko re-arrange karta hai taki free space contiguous ho jaaye (ek unbroken run). Ab 100K request ko jagah mil jaati hai.

PICTURE. Pehle: A, B, C ke beech holes ke saath. Arrows har used block ko left mein push karte hain. Baad mein: A, B, C left mein flush hain, aur right mein $40 + 30 + 50 = 120$ K ka ek merged yellow free block — pink 100K request ke liye kaafi chauda, jo ab land kar jaata hai.

Step 8 — Do escape hatches, side by side

KYA. Hum do raaste contrast karte hain: compaction (holes merge karne ke liye re-arrange karo) versus paging (blocks fixed-size banao taki holes form hi na hon).

KYO. Compaction ek cure hai — expensive, kyunki yeh bytes copy karta hai aur pause karta hai ("stops the world"); cost moved bytes ke saath badhti hai. Paging ek prevention hai: sab frames identical hone se, koi bhi free frame kisi bhi request ko satisfy karta hai, toh external holes exist hi nahi kar sakte. Paging ki jagah thodi si internal waste hoti hai (aakhri partial page) — wahi trade-off jo Step 4 se hai.

PICTURE. Left panel: variable blocks + compaction arrow (ek running cost). Right panel: uniform paged frames — ek process non-adjacent frames mein spread hai, phir bhi zero external waste kyunki frames interchangeable hain, plus ek chhota sa pink tail of internal waste.

Ek-picture summary

Yeh final figure sab aath steps compress karta hai: fixed-block world (internal waste, pink) left mein, variable-block world (external holes, yellow) right mein, aur do cures — compaction holes merge karta hua, paging unhe prevent karta hua — bottom se arrows ke roop mein.

Recall Feynman retelling — poora walkthrough simple words mein

Memory ko ek ruler ki tarah socho. Pehle hum sirf fixed tick marks (blocks) par cuts allow karte hain. Ek chhota toy ek bade bag mein baitha hai: bag mein bacha khaali room waste hai — yeh internal waste hai, aur exactly hai "poora bag minus toy," itna rounded ki koi bhi spilled bit ek aur poora bag force karta hai ( $⌈ S / B ⌉ B - S$ ). Average mein ek bag half-empty hota hai, toh waste roughly half a bag each hota hai. Phir hum kisi bhi size ke bags allow karte hain, toh andar koi room waste nahi hota — lekin jab toys jaate hain, toh woh doosron ke beech gaps punch karte hain. Gaps add karo aur kaafi room hai, phir bhi koi single gap ek bade toy ke liye kaafi wide nahi: yeh external waste hai, jo measure hota hai "kitni free space sabse bade single gap mein nahi hai." Do raaste bahar: compaction sab toys ko ek taraf slide karta hai toh gaps ek bade free space mein merge ho jaate hain (chahiye toys jo nailed down na hon — run-time addressing), aur yeh kabhi bhi sirf beech ke gaps fix karta hai, andar-bag waste kabhi nahi. Ya paging use karo: har bag ko same size ka kato toh koi empty bag kisi bhi zaroorat ko fit karta hai — external gaps form hi nahi ho sakte, har last bag mein ek tiny leftover ki cost par. Prevention expensive copy-everything cure ko beat karta hai.

Prefer this in Hinglish? → यह note Hinglish में.