Fragmentation — internal vs external, compaction: Worked examples

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

Yeh page ek drill hai. Hum parent topic ke do formulas lete hain aur unhe har tarah ke input ke against beat karte hain — clean numbers, exact fits, tiny processes, huge processes, degenerate "one hole" case, ek word problem, aur ek exam trap.

Shuru karne se pehle, teen symbols poore page ko carry karte hain. Hum inhe zero se define karte hain:

$⌈ ⌉$ marks ceiling hain — "agale pure number tak upar round karo". Hum $⌈ 2.44 ⌉ = 3$ ko padhte hain: "2.44 blocks exist nahi karta, isliye tumhe 3 pure blocks chahiye." Upar kyun aur neeche kabhi nahi? Kyunki neeche rounding karne se process ke kuch bytes bina ghar ke reh jaate — yeh illegal hai. Har bacha hua byte ek naya block force karta hai.

The scenario matrix

Yeh har distinct case class hai jo fragmentation tumhare saamne rakh sakta hai. Neeche ke examples mein har ek apna covered cell name karta hai.

Cell	Case class	Isme kya special hai
A	Internal, non-exact fit	$S$ ka $B$ ka multiple nahi → kuch waste
B	Internal, exact fit (degenerate)	$S$ $B$ ka multiple hai → waste zero
C	Internal, tiny process ( $S < B$ )	1 block chahiye, uska almost sab waste
D	Internal, many processes (system total)	kaafi tails ka sum; average $\approx B /2$ each
E	External, scattered holes	ratio 0 aur 1 ke beech
F	External, one single hole (degenerate)	ratio $= 0$ , perfectly healthy
G	External, request fails but total suffices	classic "enough but useless" trap
H	Compaction outcome	holes merge → request ab succeed karta hai
I	Word problem (real units, KB/MB)	English ko formulas mein translate karo
J	Exam twist	paging vs. compaction confusion / limiting behaviour

Example 1 — Cell A (internal, non-exact fit)

Worked example Ek process ko

$S = 5000$ B chahiye; block size $B = 2048$ B. Internal fragmentation nikalo. Forecast: padhne se pehle guess karo — kya waste 100 B ke karib hai ya 1000 B ke?

$N$ compute karo: $S / B = 5000/2048 = 2.44$ , isliye $N = ⌈ 2.44 ⌉ = 3$ . Yeh step kyun? Do blocks sirf $2 \times 2048 = 4096 < 5000$ bytes cover karte hain — kaafi nahi. Ek teesra block forced hai.
Memory diya gaya: $N \cdot B = 3 \times 2048 = 6144$ B. Yeh step kyun? Tumhe pure blocks ke liye charge kiya jaata hai, isliye tum physically 6144 bytes hold karte ho chahe tumne 5000 manga tha.
Internal waste: $6144 - 5000 = 1144$ B. Yeh step kyun? Waste = (jo tum hold karte ho) − (jo tum use karte ho). Sirf last block partial hai: usme $5000 - 4096 = 904$ used bytes hain, aur $2048 - 904 = 1144$ empty hai.

Verify: $904 + 1144 = 2048$ = ek full block. ✓ Last block ke do pieces use bilkul reconstruct karte hain.

Example 2 — Cell B (exact fit, degenerate: zero waste)

Example 3 — Cell C (tiny process, $S < B$ )

Example 4 — Cell D (system total, many processes)

Worked example Block

$B = 4096$ B (4 KB) wale system par teen processes. Sizes: $P_{1} = 6000$ B, $P_{2} = 4096$ B, $P_{3} = 100$ B. System ke across total internal fragmentation? Forecast: kaun sa ek process sabse zyada waste contribute karta hai?

$P_{1}$ : $N = ⌈ 6000/4096 ⌉ = ⌈ 1.46 ⌉ = 2$ ; diya gaya $= 8192$ ; waste $= 8192 - 6000 = 2192$ B. Yeh step kyun? Same per-process formula, ek baar har ek pe apply karo, phir sum karo.
$P_{2}$ : $6000$ ? Nahi — $4096/4096 = 1.0$ , $N = 1$ ; waste $= 4096 - 4096 = 0$ B. (Exact fit, ek system ke andar Cell B.)
$P_{3}$ : $N = ⌈ 100/4096 ⌉ = 1$ ; waste $= 4096 - 100 = 3996$ B. (Tiny, ek system ke andar Cell C.)
Total: $2192 + 0 + 3996 = 6188$ B. Yeh step kyun? System internal fragmentation har process ke last-block leftover ka sum hai.

Verify: average- $B /2$ rule predict karta hai $\approx 3 \times (4096/2) = 6144$ B; humara exact total 6188 B bilkul uske paas hai. ✓ Karib kyunki teen mein se do processes ke "random-ish" tails the; estimate sirf ek average hai.

Example 5 — Cell E & G (external: scattered holes, request fails)

Figure — Fragmentation — internal vs external, compaction

Total free: $40 + 30 + 50 = 120$ K. Yeh step kyun? Ratio sabse bada usable piece ko sari free memory se compare karta hai.

Largest block: $max (40, 30, 50) = 50$ K (figure mein amber bar).

Ratio: $1 - 50/120 = 1 - 0.4167 = 0.5833$ . Yeh step kyun? 1 ke karib ratio matlab free memory buri tarah shattered hai; yahan aadhe se zyada 50 K se upar kisi bhi request ke liye unusable hai.

100 K request: ek contiguous hole mein land karni chahiye. Largest 50 K $< 100$ K hai → fail, chahe $120 > 100$ . Yeh step kyun? Process ko di jaane wali memory contiguous honi chahiye; tum ek request ke liye teen alag holes ko nahin jod sakte.

Verify: $0.5833 \approx 7/12$ ; aur indeed $1 - 50/120 = (120 - 50) /120 = 70/120 = 7/12$ . ✓ Request fail hoti hai kyunki koi single hole $\geq 100$ K nahi hai.

Example 6 — Cell F (degenerate external: one hole, ratio zero)

Example 7 — Cell H (compaction holes ko merge karta hai)

A, B, C ko front par slide karo: saare used blocks ek end ke against pack ho jaate hain (figure ka top → bottom). Yeh step kyun? Compaction physically allocated blocks ko saath copy karta hai; iske liye run-time relocatable addresses chahiye (ek base/relocation register), warna copied code galat jagahon ko point karega.

Holes merge ho jaate hain: freed space ek block of $40 + 30 + 50 = 120$ K ban jaata hai. Yeh step kyun? Kuch free ya create nahi kiya gaya — wahi same 120 K ab scattered ki jagah contiguous hai.

Naya ratio: $1 - 120/120 = 0$ .

100 K request: $120 \geq 100$ ek block mein → succeed karti hai. Yeh step kyun? Ab ek single hole kaafi bada hai, jo bilkul wahi hai jo request ko chahiye.

Verify: total free unchanged ( $120$ K pehle aur baad mein — compaction move karta hai, delete nahi); ratio $0.5833 \to 0$ drop hua. ✓ Aur $120 \geq 100$ , isliye success. Note karo A, B, C ke andar internal waste untouched hai — compaction sirf external theek karta hai.

Example 8 — Cell I (word problem, real units)

Worked example Ek file server disk ko 4 KB clusters mein allocate karta hai. Ek user 12,000 files store karta hai, har ek exactly 1 KB. (a) Kitna space

charge hoga? (b) Kitna internal fragmentation hai? ( $1 KB = 1024$ B use karo.) Forecast: har 1 KB file ek 4 KB cluster mein — per file waste guess karo.

Per file: $S = 1024$ B, $B = 4096$ B. $N = ⌈ 1024/4096 ⌉ = ⌈ 0.25 ⌉ = 1$ cluster. Yeh step kyun? 1 KB file ko bhi ek pure 4 KB cluster chahiye — yeh Cell C hai jo 12,000 baar repeat ho raha hai.
Waste per file: $4096 - 1024 = 3072$ B $= 3$ KB.
Total charged: $12000 \times 4096 = 49, 152, 000$ B $= 48000$ KB $= 46.875$ MB. Yeh step kyun? Har file ek full cluster occupy karta hai; count se multiply karo.
Total internal waste: $12000 \times 3072 = 36, 864, 000$ B $= 36000$ KB $= 35.156$ MB. Yeh step kyun? Per-file tails ka sum karo.

Verify: useful data $= 12000 \times 1024 = 12, 288, 000$ B; aur $12, 288, 000 + 36, 864, 000 = 49, 152, 000$ = total charged. ✓ Poore $75%$ disk waste hai — large blocks ke saath tiny files ka khatraa.

Example 9 — Cell J (exam twist: kaun sa cure, aur limit)

Worked example Judge karne ke liye exam claim:

"Segmentation se paging par switch karne se SARI fragmentation remove ho jaayegi." Paging mein frame $B$ ke saath, ek process ke liye worst-case internal waste kya hai, aur kaun si fragmentation bachi rehti hai? Forecast: true ya false — kya paging zero waste deta hai?

Paging ke under External: koi bhi free frame kisi bhi request ko fit karta hai (sare frames same size), isliye koi unusable external holes nahi bante → external fragmentation $= 0$ . Yeh step kyun? Yeh fixed-size units ki strength hai — koi awkward-size gaps form nahi ho sakte.
Paging ke under Internal: process ka last page partial hota hai. Worst case process ek page boundary se 1 byte cross karta hai, isliye woh ek extra frame leta hai jisme se $B - 1$ bytes waste hote hain. Yeh step kyun? Maximum tail waste almost ek full frame se kam hai.
Worst-case internal per process $= B - 1$ bytes. Yeh step kyun? $S mod B = 1$ waste $B - 1$ deta hai, jo sabse bada waste hai jo ek single leftover byte force kar sakta hai.
Verdict: claim false hai. Paging external fragmentation remove karta hai lekin har process ke liye $B - 1$ bytes tak internal waste rakhta hai.

Verify: $B = 4096$ , $S = 4097$ lo. $N = ⌈ 4097/4096 ⌉ = 2$ ; waste $= 2 \times 4096 - 4097 = 8192 - 4097 = 4095 = B - 1$ . ✓ Bound tight hai.

Recall Pure matrix ki one-line recall

Internal formula ::: $⌈ S / B ⌉ B - S$ ; zero sirf tab jab $S$ $B$ ka multiple ho; worst case $B - 1$ ; system total = tails ka sum (average mein $\approx B /2$ each). External ratio ::: $1 - \frac{largest free block}{total free}$ ; ek hole ke liye 0, memory shatter hone par 1 ki taraf badhta hai; compaction ise 0 kar deta hai total free ko change kiye bina.

Parent topic par wapas jao. Related machinery: Paging, Segmentation, Dynamic Memory Allocation, Memory Allocation Strategies, Virtual Memory, Address Binding.