Heap fragmentation: Question bank — Hinglish deep dive

5.1.17 · D5 · Coding › C Programming › Heap fragmentation

Ye items un misconceptions ko target karte hain jo ye topic invite karta hai: "free total" aur "largest hole" ko confuse karna, fragmentation ko leaks se confuse karna, yeh assume karna ki coalescing hamesha hoti hai, aur degenerate/edge cases bhool jaana.

Pehle ye Vocabulary chahiye

Neeche har trap char shabdon par tika hua hai. Shuru karne se pehle inhe pakka kar lo, taaki koi bhi symbol ya term surprise na kare.

Neeche ki picture poore page ka reference hai — woh "parking lot" jiske baare mein har sawaal asal mein baat kar raha hai.

Figure dekho: teen live blocks A, C do holes ko fence kar rahe hain. Total free bada ho sakta hai, lekin largest single hole (orange) woh hai jismein ek request fit honi chahiye. Yahi ek idea yahin ke zyaadaatar traps ko power karta hai.

Size symbols jo edge-cases use karte hain

Figure dekho: aapke $r$ requested bytes (blue), hidden $h$ -byte header (gray), aur rounded-up tail $W$ (red) jiske liye aapne pay kiya lekin kabhi use nahi kar sakte — woh red slice hi internal fragmentation hai.

True ya false — justify karo

Total free memory ≥ request size guarantee karta hai ki malloc succeed karega.

False — malloc ko ek contiguous range chahiye; free bytes live blocks ke aas-paas chhote non-adjacent holes ke roop mein bikre ho sakte hain (jaise figure s01 mein do holes hain), toh koi ek hole fit nahi hota.

Fragmentation ek tarah ki memory leak hai.

False — leak woh memory hai jo kabhi free nahi hoti (hamesha ke liye kho jaati hai); fragmented memory free hai aur track ki gayi hai, bas is tarah arrange ki gayi hai ki koi request satisfy nahi ho sakti.

Har allocation ko free karne se eventually sari fragmentation khatam ho jaati hai.

End mein True — jab sare live blocks khatam ho jaate hain toh poora heap ek hole mein coalesce ho jaata hai; lekin jab tak blocks live hain, doosron ko free karna unke aas-paas merge nahi kar sakta.

Ek fresh heap par sirf ek allocation ke saath bhi internal fragmentation ho sakti hai.

True — ek request ko block size

B (r)

(header

h

+ alignment

a

) tak round up karna

W

bytes us ek block ke andar waste karta hai, baaki heap par kuch bhi ho ya na ho.

External fragmentation ho sakti hai bhale hi har individual block sahi tarike se free kiya gaya ho.

True — sahi freeing leaks nahi fragmentation ko rokti hai; scattered order mein frees karne par bhi non-adjacent holes bante hain.

Stack ko heap jaisi hi fragmentation hoti hai.

False — stack strict LIFO order mein allocate/free karta hai, isliye freed space hamesha top ke adjacent hoti hai aur kabhi interior holes nahi chorta (dekho Stack vs Heap; jaise A push karna phir B push karna phir B pop karna hamesha topmost bytes free karta hai, koi interior gap nahi).

Ek bada malloc uske baad ek free heap ko fragment kar sakta hai.

False — ek alloc phir uska free heap ko ek coalesced hole mein chhodta hai; fragmentation ke liye mixed sizes ka scattered order mein free hona zaroori hai.

Coalescing kisi bhi do free holes ko merge karta hai jo ek saath exist karte hain.

False — coalescing sirf un holes ko merge karta hai jo memory mein physically adjacent hain; do holes ke beech ek live block (figure s01 mein block C) merge ko block karta hai.

Fixed-size blocks ka Pool allocator use karna external fragmentation khatam kar deta hai.

True — har hole exactly ek block size ka hota hai, isliye koi bhi freed block kisi bhi request mein fit hota hai; "too-small scattered hole" ki problem nahi hoti (haalaanki internal waste reh sakti hai).

free call karne ki frequency double karne se internal fragmentation kam hoti hai.

False — internal waste ek live block ke andar rounding ki wajah se rehti hai; aap use sirf us block ko free karke reclaim kar sakte ho, aur agla same-size alloc phir se waste karega.

Bade size-class gaps (jaise powers of two) hamesha fragmentation ko badhaate hain.

False — moti classes internal waste badhati hain lekin hole sizes ki variety ghatati hain, jo usually external fragmentation ghatata hai; yeh ek trade-off hai, strict worsening nahi.

Error pakdo

"malloc(40) fail hua, toh program ki memory khatam ho gayi."

Galat conclusion — failure ka matlab ho sakta hai ki largest single hole < 40 (figure s01 mein orange hole) bhale hi total free memory kaafi ho; yeh fragmentation hai, exhaustion nahi.

"Maine B ko free kiya jo live A aur C ke beech baitha hai, toh freed 30 bytes neighbouring free hole mein join ho jayenge."

Error — B ke neighbours live A aur live C hain, free holes nahi, isliye kuch coalesce nahi hota; 30 bytes ek isolated hole bane rehte hain.

"Fragmentation risk measure karne ke liye main time ke saath total free bytes track karunga."

Galat metric — total free high reh sakta hai jabki allocations fail hote hain; aapko largest contiguous hole track karna chahiye (ya largest-hole / total-free ka ratio).

"Internal fragmentation non-adjacent holes ki wajah se hoti hai."

Flavours confused hain — non-adjacent holes external fragmentation hai; internal fragmentation woh wasted tail

W

hai jo rounded-up block ke andar hoti hai (figure s02 mein red slice).

"FIFO order mein free karna (jis order mein allocate kiya) best coalesces karta hai."

Galat order — FIFO sabse purane block ko pehle free karta hai, jo usually naye live blocks ke neeche dab hota hai; LIFO (stack order) hi hai jo har free ko growing hole se touch karne deta hai.

"Ek compacting garbage collector internal fragmentation remove karta hai."

Overclaim — Garbage collection jo compact karta hai objects ko move karta hai external fragmentation remove karne ke liye; per-object rounded size

W

(internal waste) use move karne se nahi badlta.

"Kyunki Memory alignment bytes waste karta hai, alignment disable karne se sari fragmentation khatam ho jaayegi."

Galat aur dangerous — alignment drop karna faults ya slow access cause kar sakta hai, aur sirf internal waste ko touch karta hai, external fragmentation ke liye kuch nahi karta.

"malloc(1) sirf 1 byte reserve karta hai, isliye tiny allocations kabhi fragment nahi karte."

Error — minimum chunk size (jaise 16 ya 32 bytes) plus header ka matlab hai ki malloc(1) ek poora minimum chunk reserve karta hai; hazaron tiny allocs phir bhi heap ko bahut saare chhote blocks mein carve kar dete hain.

Why questions

malloc ko contiguous address range return kyun karna padta hai?

Kyunki ek returned pointer plus offset se aapke object mein linearly index hona chahiye; ek split object ko simple pointer arithmetic se address nahi kiya ja sakta.

Mixed-size allocation same-size allocation se zyaada fragment kyun karta hai?

Same-size blocks same-size holes chhodte hain jo koi bhi future request exactly refit kar sakti hai; mixed sizes odd sizes ke holes chhodte hain jo next request se rarely match karte hain.

Coalescing ko physical neighbour check kyun karna padta hai, free-list order nahi?

Do holes free-list mein adjacent ho sakte hain lekin memory mein door ho sakte hain; sirf woh bytes jo physically touch karte hain (jaise figure s01 dikhata hai) ek addressable range mein merge ho sakte hain.

LIFO / stack-order freeing fragmentation kyun avoid karta hai?

Har freed block hamesha last-created hole ke adjacent hota hai, isliye har free ek growing hole mein coalesce ho jaata hai, heap ko ek single block ki taraf wapas le jaata hai.

Koi Arena allocator apni lifetime ke dauran interior fragmentation se immune kyun hota hai?

Woh har allocation ke liye ek pointer aage badhata hai aur sab kuch ek saath free karta hai, isliye koi interior holes kabhi nahi bante — allocation sirf ek cursor ko move karna hai.

Requests ko alignment quantum ke multiple tak round up karna waste kyun karta hai?

Request plus header

r + h

rarely exactly block boundary par utarta hai, isliye ceiling use

a

ke next multiple tak push karta hai aur gap

W

untouchable internal waste ban jaata hai (dekho malloc and free).

Ek heap "50% free" hote hue bhi us size se aadhi request fail kyun kar sakta hai?

Free half bahut saare tiny holes mein bikri ho sakti hai jo live blocks se alag hain, isliye largest hole request se kaafi chhota hota hai.

Power-of-two size classes ek fragmentation type ko doosre ke badle mein kyun trade karte hain?

Next power of two par snap karna

W

badhata hai (zyaada internal waste) lekin sirf kuch distinct block sizes produce karta hai, isliye freed holes future requests mein zyaada baar refit hoti hain (kam external waste).

Edge cases

malloc(0) — kya yeh fragment karta hai?

Edge case — woh NULL ya ek unique tiny pointer return kar sakta hai, lekin koi usable payload request nahi karta; minimum chunk size ke saath woh phir bhi ek minimum chunk of overhead reserve karta hai, minor internal cost contribute karta hai, external fragmentation nahi.

Exactly block size request karna (jaise

r + h

perfectly

a

ka multiple) — internal waste?

Zero rounding waste — request already block boundary par land karti hai, isliye

B (r) = r + h

aur

W = 0

, sirf header khud ke alawa.

Ek hole aur ek request usi hole ke size ki wali heap — fragmentation?

Koi nahi — ek single hole jo request exactly fill kare ideal case hai; external aur (agar boundary-aligned ho toh) internal waste dono zero hain.

Do adjacent free holes jiske beech koi live block nahi — kya yeh fragmentation hai?

Stable fragmentation nahi — ek sahi allocator adjacent holes ko turant ek mein coalesce karta hai, isliye woh immediately ek bade hole ki tarah behave karte hain.

Saare allocations identical size, kisi bhi order mein freed — external fragmentation?

Koi jo requests rok sake nahi — har hole ek block ke barabar hota hai, isliye koi bhi same-size request kisi bhi hole mein fit ho jaati hai adjacency ki parwah kiye bina; scattered frees yahan harmless hain.

malloc(1) ek allocator par jiska minimum chunk 16 bytes hai — kitna internal waste?

h

header bytes plus 16-byte minimum tak round up ke saath, almost poora chunk waste hai —

W \approx 16 - 1 = 15

payload bytes lost (header count karne se pehle), isliye tiny requests sabse bure internal-waste offenders hain.

Same pointer ko do baar free karna (double free) — kya yeh fragmentation se related hai?

Unrelated bug — double free free-list corrupt karta hai (undefined behaviour), jo ek correctness fault hai, naa ki woh "free but unusable" arrangement jo fragmentation define karta hai.

Recall Ek-line summary jo yaad rakhni hai

Fragmentation largest contiguous hole ke baare mein hai, kabhi total free bytes ke baare mein nahi; external = live blocks se fenced scattered holes, internal = block/size-class par rounding se wasted tail $W$ ; dono leak nahi hain.

Connections

Heap fragmentation — parent topic jise ye traps drill karte hain
malloc and free — woh allocator jiska free-list aur headers in questions mein probe kiya gaya hai
Memory leaks — woh bug jisse fragmentation ko baar baar confuse kiya jaata hai
Stack vs Heap — kyun stack in sab se bacha rehta hai (strict LIFO, koi interior holes nahi)
Memory alignment — internal-waste edge cases ki jad
Pool allocator / Arena allocator — designs jo external fragmentation se bachte hain
Garbage collection — compaction aur woh kya karta hai (aur kya nahi) fix karta