4.2.24
Memory ek finite physical resource hai. Jab hum uske chunks dete hain aur baad mein wapas lete hain, toh bache hue holes future requests ke saath rarely align hote hain. Fragmentation woh wasted memory hai jo exist toh karti hai, lekin use nahi ho sakti . Iske exactly do flavours hain:
Internal fragmentation — wasted space andar ek block ke jisko hum already de chuke hain.External fragmentation — wasted space beech mein blocks ke; free total enough hai, lekin scattered hai.
Agar sirf ek line yaad karni ho: Internal = waste jo ek allocation ke andar chupi hai; External = total free memory enough hai, lekin koi ek piece itna bada nahi.
OS memory ko units mein allocate karta hai. Do design choices se do problems create hoti hain:
Agar units fixed-size hain (paging, fixed partitions), toh ek process jisko ek unit se thoda zyada chahiye, use poora extra unit lena padta hai → unused tail internal waste hai.
Agar units variable-size hain (segmentation, dynamic partitions), toh processes aate-jaate rehte hain, aur awkward sizes ke free holes idhar-udhar chhor jaate hain → external waste hoti hai.
Aap naive schemes se dono se ek saath nahi bach sakte — fixed sizes external ko internal se trade karti hain, variable sizes internal ko external se trade karti hain. Yahi poori kahani hai.
Definition Internal fragmentationMemory jo ek process ko allocate ki gayi lekin uske dwara use nahi hui , kyunki allocation fixed-size chunks mein hoti hai. Yeh ek allocated unit ke andar rehti hai, isliye process uski "owner" toh hai lekin ise waste karti hai.
Intuition WHAT it feels likeAap pizza sirf poore pizza ke roop mein order kar sakte ho, lekin aap 8-slice pizza mein se 6.5 slices khaate ho. Bache 1.5 slices tumhare hain (allocated) lekin waste hain. Aap agले person ko aadha pizza nahi de sakte.
Ek process ko S B
N = ⌈ B S ⌉
Total memory di gayi = N ⋅ B
Internal = N ⋅ B − S = ⌈ B S ⌉ B − S
Worked example Worked: ek processS = 5000 B = 2048
N = ⌈ 5000/2048 ⌉ = ⌈ 2.44 ⌉ = 3 Kyun? 2 blocks = 4096 < 5000, isliye 3rd block chahiye.Diya gaya = 3 × 2048 = 6144
Internal waste = 6144 − 5000 = 1144 Yeh step kyun? Last block mein sirf 5000 − 4096 = 904 2048 − 904 = 1144
Worked example Average-case estimateAgar process sizes block size ke relative random hain, toh last block average pe half full hota hai. Toh expected internal waste per process ≈ B /2 Kyun? Leftover S mod B [ 0 , B ) B − ( S mod B ) B /2 Takeaway: chhote blocks → less internal fragmentation, lekin zyada page-table overhead.
Definition External fragmentationTotal free memory ek request satisfy karne ke liye sufficient hai , lekin woh non-contiguous holes mein split hai , koi bhi individually itna bada nahi. Waste between allocations rehti hai.
Intuition WHAT it feels likeEk cinema mein 50 empty seats hain, lekin 6 log ka ek family saath nahi baith sakta kyunki empties rows mein ek-ek karke scattered hain. Plenty of free seats; koi usable block nahi.
Variable-size allocation mein, bahut saare allocate/free cycles ke baad free list Swiss cheese jaisi lagti hai:
[ Used ][ free 40K ][ Used ][ free 30K ][ Used ][ free 50K ]
100K ki request fail hoti hai even though 40 + 30 + 50 = 120 K
Holes: 40K, 30K, 50K. Total free = 120 = 50 = 1 − 50/120 = 0.583 Yeh kyun matter karta hai? Half se zyada free memory 50K se bade kisi bhi request ke liye unusable hai.
Allocated blocks ko memory ke ek end par saath shuffle karna taaki saare free holes ek bade contiguous block mein merge ho jayein . External fragmentation solve karta hai. Relocatable code chahiye (dynamic address binding at run time, usually ek relocation/base register ke through).
Cinema mein sab ko aage slide karo taaki saari empty seats peeche pool ho jayein — ab 6 log ka family fit ho jaata hai. Hum yeh tabhi kar sakte hain agar seats nailed down na hon (addresses ko runtime pe re-bindable hona chahiye).
Worked example Before → AfterBefore: [A][free40][B][free30][C][free50]
After: [A][B][C][ free 120K (contiguous) ]
100K ki request ab succeed karti hai. Kyun? Holes 120K tak sum hue; unhe merge karne se ek usable block milta hai.
Intuition Cost (why we don't compact constantly)Compaction memory copy karta hai aur processes ko pause karta hai ("stop the world"). Cost ∝ bytes moved. Yeh expensive hai, isliye OSes prefer karte hain ki pehle hi external fragmentation se bachen → paging (fixed frames) external fragmentation ko completely eliminate karta hai, sirf thodi internal ki price dekar.
Common mistake "Compaction internal fragmentation fix karta hai."Kyun sahi lagta hai: compaction "memory tidy karta hai," toh surely woh saari waste remove kar deta hai. Fix: internal waste ek block ke andar rehti hai jo process ki own hai — block ko move karne se tail-waste bhi saath chalti hai. Compaction sirf external gaps merge karta hai. Compaction → external only.
Common mistake "Paging external fragmentation cause karta hai."Kyun sahi lagta hai: processes non-contiguous frames mein scattered hain, fragmented lagta hai. Fix: koi bhi free frame kisi bhi request serve kar sakta hai kyunki saare frames identical fixed size ke hain — isliye koi unusable external holes nahi hote. Paging usse internal fragmentation ke liye trade karta hai (last partial page). Paging: no external, some internal.
Common mistake "Chhote blocks hamesha better hote hain."Kyun sahi lagta hai: chhota block ⇒ chhota wasted tail ⇒ less internal fragmentation. Fix: tiny blocks matlab ek huge page table aur zyada management overhead. Yeh ek trade-off hai, free win nahi.
Internal
External
Waste kahaan hai
allocated block ke andar
blocks ke beech
Kis wajah se
fixed-size allocation
variable-size allocation
Scheme
paging, fixed partitions
segmentation, dynamic partitions
Cure
chhote blocks (limited)
compaction , paging
Recall Feynman: ek 12-saal-ke bachche ko explain karoSocho tumhara toy box sirf fixed-size bags mein toys fit karta hai. Agar tumhara toy chhota hai lekin bag bada hai, toh bag mein bachi jagah waste hai — yeh internal waste hai, bag ke andar . Ab socho tumhare paas toys ke beech free shelf gaps hain: bahut saare chhote gaps mile karke kaafi jagah bante hain, lekin koi bhi ek bade toy ke liye itna wide nahi. Yeh external waste hai. Compaction matlab saare toys ko ek taraf push karna taaki gaps mil karke ek badi free space ban jayein — ab bada toy fit ho jaata hai!
"IN side is IN ternal, between is eX ternal (X = beech ke gaps)."
Aur: C ompaction C onnects gaps → sirf eX ternal kind fix karta hai.
What is internal fragmentation? Ek process ko allocate ki gayi lekin unused memory, wasted kyunki allocation fixed-size blocks mein hoti hai; waste ek allocated block ke andar hoti hai.
What is external fragmentation? Total free memory ek request ke liye enough hai lekin non-contiguous holes mein split hai, koi bhi individually itna bada nahi.
Formula for internal fragmentation of one allocation (size S, block B)? ⌈ S / B ⌉ ⋅ B − S
Average internal waste per process relative to block size B? About B /2
External fragmentation ratio formula? 1 − total free memory largest free block
What does compaction do and which fragmentation does it cure? Allocated blocks ko saath slide karta hai taaki free holes ek contiguous block mein merge ho jayein; sirf external fragmentation cure karta hai.
What hardware/binding requirement does compaction need? Relocatable code with run-time address binding (base/relocation register).
Which scheme eliminates external fragmentation, and what does it trade for? Paging — fixed-size frames; yeh external ko kuch internal fragmentation se trade karta hai.
Why are smaller blocks not always better? Less internal waste lekin bade page tables aur zyada management overhead — ek trade-off hai.
Does compaction fix internal fragmentation? Nahi — internal waste block ke saath move hoti hai; sirf external gaps merge hote hain.
but adds page-table overhead
