Fragmentation — internal vs external, compaction: Exercises

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

Shuru karne se pehle, ek one-screen toolbox hai jo hum baar baar use karenge. Har symbol ko words mein spell out kiya gaya hai taaki pehli line koi bhi padh sake.

Formula Woh teen tools jo hum baar baar use karenge

Ek allocation ki internal waste. Ek process $S$ bytes maangti hai ( $S$ = "size wanted"). Memory sirf $B$ bytes ke fixed blocks mein di jaati hai ( $B$ = "block size"). Zaroorat ke whole blocks ki sankhya hai $N = ⌈ \frac{S}{B} ⌉$ , jahan $⌈ x ⌉$ ("ceiling of $x$ ") ka matlab hai agale whole number tak round up karo — kyunki tum ek block ka fraction nahi le sakte. $Internal = N \cdot B - S = ⌈ \frac{S}{B} ⌉ B - S$ Yeh "jo mila" minus "jo chahiye tha" hai.
External fragmentation ratio. Jab free memory alag-alag holes mein bikhari hoti hai, toh $0$ aur $1$ ke beech ka yeh number batata hai ki kitna bura hai: $Ratio = 1 - \frac{largest single free hole}{total free memory}$ $0$ = saari free memory ek clean block hai; $1$ ke paas = buri tarah bikhari hui hai.
Compaction allocated blocks ko ek taraf slide karta hai taaki saare holes ek ek contiguous free block mein merge ho jayein. Yeh sirf external fragmentation theek karta hai, aur iske liye run-time address binding (ek base/relocation register) chahiye taaki code move ho sake.

Level 1 — Recognition

Goal: sirf waste ka flavour naam karo aur formulas padho — abhi koi arithmetic tricks nahi.

Exercise 1.1

Ek process ko ek $4 KB$ page diya jaata hai lekin woh sirf $3 KB$ use karta hai. Fragmentation type ka naam batao aur wasted amount do.

Recall Solution 1.1

Waste process ke already owned ek block ke andar hai → internal fragmentation. Wasted $= 4 KB - 3 KB = 1 KB$ .

Exercise 1.2

Free memory $20 KB$ , $10 KB$ , $20 KB$ ke holes mein split hai. Ek process $40 KB$ maangti hai aur refuse kar di jaati hai. Fragmentation type ka naam batao.

Recall Solution 1.2

Total free $= 20 + 10 + 20 = 50 KB \geq 40 KB$ , phir bhi koi single hole itna bada nahi hai. Waste blocks ke beech mein rehti hai → external fragmentation.

Exercise 1.3

In do schemes mein se, Paging ya Segmentation, kaun sa external fragmentation se suffer karta hai, aur kaun sa internal se?

Recall Solution 1.3

Paging fixed-size frames use karta hai → koi bhi free frame kisi bhi request ke liye fit hota hai → koi external nahi, lekin partly-used last page se internal hota hai. Segmentation variable-size segments use karta hai → awkward leftover holes → external.

Level 2 — Application

Goal: dono formulas mein numbers plug karo, khaaskar ceiling ke saath.

Exercise 2.1

Ek process ko $S = 5300$ bytes chahiye. Blocks $B = 1024$ bytes ke hain. Blocks ki sankhya aur internal fragmentation compute karo.

Recall Solution 2.1

Blocks: $N = ⌈ \frac{5300}{1024} ⌉ = ⌈ 5.176 ⌉ = 6$ . Kyun 6? Paanch blocks $5 \times 1024 = 5120 < 5300$ dete hain, toh ek aur zaroor hai. Given: $6 \times 1024 = 6144$ bytes. Internal waste: $6144 - 5300 = 844$ bytes.

Exercise 2.2

$S_{1} = 2000$ , $S_{2} = 4097$ , $S_{3} = 8192$ bytes sizes ke teen processes ko har ek $B = 4096$ ke saath page kiya jaata hai. Teeno mein total internal fragmentation nikalo.

Recall Solution 2.2

$P_{1}$ : $N = ⌈ 2000/4096 ⌉ = 1$ , given $4096$ , waste $= 4096 - 2000 = 2096$ .
$P_{2}$ : $N = ⌈ 4097/4096 ⌉ = 2$ , given $8192$ , waste $= 8192 - 4097 = 4095$ . Kyun 2 blocks? Ek pura block se ek byte zyada hone par bhi ek poora doosra block force hota hai.
$P_{3}$ : $N = ⌈ 8192/4096 ⌉ = 2$ , given $8192$ , waste $= 8192 - 8192 = 0$ . Ek perfect multiple kuch bhi waste nahi karta. Total internal $= 2096 + 4095 + 0 = 6191$ bytes.

Exercise 2.3

Free holes $40 KB$ , $30 KB$ , $50 KB$ hain. External fragmentation ratio compute karo.

Recall Solution 2.3

Total free $= 40 + 30 + 50 = 120 KB$ . Largest hole $= 50 KB$ . $Ratio = 1 - \frac{50}{120} = 1 - 0.4167 = 0.5833$ Aadhi se zyada free memory $50 KB$ se bade kisi bhi request ke liye unusable hai.

Level 3 — Analysis

Goal: averages, trade-offs, aur allocations ki sequences ke baare mein reason karo.

Exercise 3.1

Ek system $200$ processes run karta hai, har ek $B = 4096$ bytes ke saath paged hai, aur process sizes $B$ ke relative effectively random hain. Total internal fragmentation estimate karo, aur reasoning explain karo.

Recall Solution 3.1

Ek random size ke liye, aakhri (partial) block average mein aadha bhara hota hai, isliye expected waste per process $\approx B /2 = 4096/2 = 2048$ bytes. Kyun $B /2$ ? Leftover $S mod B$ , $[0, B)$ par uniform hai, isliye wasted tail $B - (S mod B)$ average $B /2$ hota hai. Total estimate $= 200 \times 2048 = 409600$ bytes $\approx 400 KB$ .

Exercise 3.2

Wahi $200$ processes. Ek engineer block size ko half karke $B = 2048$ kar deta hai. Expected internal fragmentation ka kya hota hai, aur hidden cost kya hai?

Recall Solution 3.2

Naya expected waste per process $\approx B /2 = 1024$ bytes; total $\approx 200 \times 1024 = 204800$ bytes $\approx 200 KB$ . Internal waste roughly half ho jaati hai. Hidden cost: chote blocks matlab process per zyada blocks, isliye page table badhti hai (store aur walk karne ke liye zyada entries). Yeh ek trade-off hai, free win nahi — Memory Allocation Strategies dekho.

Exercise 3.3

$100 KB$ ki memory variable partitions se allocate ki jaati hai. Requests aati hain: allocate $30 KB$ (A), $20 KB$ (B), $30 KB$ (C); phir B free karo; phir $25 KB$ (D) request karo. First-fit (Dynamic Memory Allocation / Memory Allocation Strategies) use karte hue, kya D fit hota hai? Jab D aata hai us moment ka external fragmentation ratio compute karo.

Recall Solution 3.3

A, B, C ke baad layout (addresses low→high): $[A 30] [B 20] [C 30]$ , tail hole ke saath $100 - 80 = 20 KB$ . B free karo: layout $[A 30] [free 20] [C 30] [free 20]$ . Ab free holes: $20 KB$ aur $20 KB$ ; total free $= 40 KB$ , largest $= 20 KB$ . D ko $25 KB$ chahiye: first-fit holes scan karta hai, $20 < 25$ aur $20 < 25$ paata hai → D fail, chahe $40 \geq 25$ . $Ratio = 1 - \frac{20}{40} = 0.5$ Neeche dii picture dekho.

Figure — Fragmentation — internal vs external, compaction

Level 4 — Synthesis

Goal: tools combine karo — compaction, ratios, aur before/after reasoning.

Exercise 4.1

Exercise 3.3 ki failing state lo: $[A 30] [free 20] [C 30] [free 20]$ inside $100 KB$ . Compaction apply karo, phir request D ( $25 KB$ ) dobara attempt karo. Layout, naya ratio, aur kitne kilobytes move hue dikhao.

Recall Solution 4.1

Compact: C ko A ke against slide karo taaki dono holes upar pool ho jayein: $[A 30] [C 30] [free 40]$ . Ab single free block $40 KB \geq 25 KB$ hai → D fit ho jaata hai. D rakhne ke baad: $[A 30] [C 30] [D 25] [free 15]$ . Naya ratio (D rakhne se pehle): $40 KB$ ka ek hole → $Ratio = 1 - \frac{40}{40} = 0$ (perfectly consolidated). Bytes moved: sirf $C$ ko slide karna pada (A pehle se bottom par hai). Toh $30 KB$ copy hue. Cost bytes moved ke proportional hai.

Exercise 4.2

Ek colleague propose karta hai: "ratio ko $0$ par rakhne ke liye har free ke baad compact karo." Iske khilaf do reasons do, aur woh scheme batao jo is poore problem ko sidestep karta hai.

Recall Solution 4.2

Compaction memory copy karta hai aur processes ko pause karta hai ("stop the world"); har free ke baad karna un blocks ko relocate karne mein bahut CPU time waste karta hai jo shayad kuch seconds baad phir free ho jayein.
Iske liye processes ko run time par relocatable hona chahiye aur har event par base registers re-update karne padte hain — har event par overhead. Sidestep: Paging fixed frames use karta hai isliye external fragmentation ho hi nahi sakti — koi bhi frame kisi bhi request ke liye fit hota hai — small internal waste ki keemat par. Virtual Memory bhi dekho, jo paging ke upar layer karta hai.

Exercise 4.3

Ek $256 MB$ region poori tarah $16 MB$ each ke fixed partitions mein carve ki gayi hai. Naun processes sizes $9, 15, 16, 3, 12, 16, 10, 7, 14$ MB ki hain, har ek ek partition mein rakhi gayi hain. Total internal fragmentation aur baaki empty partitions ki sankhya compute karo.

Recall Solution 4.3

Partitions available $= 256/16 = 16$ . Processes placed $= 9$ , toh empty partitions $= 16 - 9 = 7$ . Internal waste per placed process $= 16 - S$ (har ek exactly ek $16 MB$ partition fill karta hai): $(16 - 9) + (16 - 15) + (16 - 16) + (16 - 3) + (16 - 12) + (16 - 16) + (16 - 10) + (16 - 7) + (16 - 14)$ $= 7 + 1 + 0 + 13 + 4 + 0 + 6 + 9 + 2 = 42 MB .$ Note: woh $7$ empty partitions ( $112 MB$ ) unallocated free space hain, internal fragmentation nahi — internal sirf allocated partitions ke andar waste count karta hai.

Level 5 — Mastery

Goal: design karo, ek full trade-off quantify karo, aur choice defend karo.

Exercise 5.1

Tumhe $1000$ processes serve karni hain jo average $S = 5000$ bytes each ki hain, ek aisi machine par jahan page-table cost $8$ bytes per page-table entry hai (process ke har use hone wale frame ke liye ek entry). Block size $B = 4096$ vs $B = 1024$ ko (a) total expected internal fragmentation aur (b) total page-table bytes par compare karo. Tum kaun sa choose karoge, aur kyun?

Recall Solution 5.1

(a) Internal fragmentation (expected $\approx B /2$ per process):

$B = 4096$ : $1000 \times 2048 = 2048000$ bytes $\approx 2.05 MB$ .
$B = 1024$ : $1000 \times 512 = 512000$ bytes $\approx 0.51 MB$ .

(b) Page-table bytes (entries per process $= ⌈ S / B ⌉$ , $\times 1000 \times 8$ ):

$B = 4096$ : $⌈ 5000/4096 ⌉ = 2$ entries → $1000 \times 2 \times 8 = 16000$ bytes.
$B = 1024$ : $⌈ 5000/1024 ⌉ = 5$ entries → $1000 \times 5 \times 8 = 40000$ bytes.

Combined overhead (waste + table):

$B = 4096$ : $2048000 + 16000 = 2064000$ bytes.
$B = 1024$ : $512000 + 40000 = 552000$ bytes.

$B = 1024$ choose karo: iska total overhead yahan bahut kam hai kyunki internal-fragmentation saving ( $\approx 1.5 MB$ ) extra page-table cost ( $24 KB$ ) se kahin zyada hai. Caveat: agar processes tiny hoon (har ek almost ek page ke barabar), toh table cost dominate kar sakti hai — hamesha numbers run karo.

Exercise 5.2

Design decision: ek real-time system lambi pauses tolerate nahi kar sakta lekin variable-size segments run karta hai jo externally fragment hote hain. Yeh compaction use karne se mana karta hai (bahut disruptive hai). Ek aisi scheme propose karo jo external fragmentation ko without a stop-the-world pause remove kare, aur woh fragmentation cost batao jo tum return mein accept karte ho.

Recall Solution 5.2

Segmentation (variable blocks) se Paging (fixed frames) par switch karo. Kyunki har frame identical hai aur koi bhi frame kisi bhi request ko satisfy karta hai, external fragmentation bilkul khatam ho jaata hai bina kisi relocation pass ke — koi copying nahi, koi pause nahi. Cost accepted: har process ke last partial page par thodi internal fragmentation (expected $\approx B /2$ ). Yeh classic trade hai: thodi internal waste do aur external waste aur compaction pauses se azaadi pao. Virtual Memory ko upar layer karne se phir tumhe saare frames ek saath resident rakhne ki bhi zaroorat nahi rehti.

Recall Har level ka one-line recap

L1 flavour naam karo ::: block ke andar = internal; blocks ke beech = external. L2 formulas plug karo ::: $⌈ S / B ⌉ B - S$ aur $1 - \frac{largest}{total}$ ; hamesha round up karo. L3 averages ke baare mein reason karo ::: expected internal waste $\approx B /2$ per process; chota $B$ help karta hai lekin page table bloat hoti hai. L4 compaction apply karo ::: yeh holes ko ratio $0$ par merge karta hai, cost $\propto$ bytes moved; empty partitions internal waste nahi hain. L5 design & defend karo ::: total overhead = internal waste + table cost minimize karo; paging external ko bina pause ke khatam karta hai.