Memory is a finite physical resource. When we hand out chunks of it and later take them back, the leftover holes rarely line up with future requests. Fragmentation is the wasted memory that exists but cannot be used . There are exactly two flavours:
Internal fragmentation — wasted space inside a block we already gave out.External fragmentation — wasted space between blocks; free total is enough, but it's scattered.
If you remember only one line: Internal = waste hidden inside an allocation; External = enough free memory total, but no single piece is big enough.
The OS allocates memory in units . Two design choices create the two problems:
If units are fixed-size (paging, fixed partitions), a process that needs slightly more than a unit must take a whole extra unit → the unused tail is internal waste.
If units are variable-size (segmentation, dynamic partitions), processes come and go, leaving free holes of awkward sizes scattered around → external waste.
You cannot escape both at once with naive schemes — fixed sizes trade external for internal, variable sizes trade internal for external. This trade-off is the whole story.
Definition Internal fragmentationMemory allocated to a process but not used by it , lost because allocation happens in fixed-size chunks. It lives inside an allocated unit, so the process "owns" it but wastes it.
Intuition WHAT it feels likeYou order pizza only by the whole pizza, but you eat 6.5 slices of an 8-slice pizza. The 1.5 leftover slices are yours (allocated) but wasted. You can't give half a pizza to the next person.
A process needs S S S B B B
N = ⌈ S B ⌉ N = \left\lceil \frac{S}{B} \right\rceil N = ⌈ B S ⌉
Total memory given = N ⋅ B N \cdot B N ⋅ B
Internal = N ⋅ B − S = ⌈ S B ⌉ B − S \boxed{\text{Internal} = N\cdot B - S = \left\lceil \tfrac{S}{B}\right\rceil B - S} Internal = N ⋅ B − S = ⌈ B S ⌉ B − S
Worked example Worked: one processS = 5000 S = 5000 S = 5000 B = 2048 B = 2048 B = 2048
N = ⌈ 5000 / 2048 ⌉ = ⌈ 2.44 ⌉ = 3 N=\lceil 5000/2048\rceil = \lceil 2.44\rceil = 3 N = ⌈ 5000/2048 ⌉ = ⌈ 2.44 ⌉ = 3 Why? 2 blocks = 4096 < 5000, so we need a 3rd.Given = 3 × 2048 = 6144 = 3\times2048 = 6144 = 3 × 2048 = 6144
Internal waste = 6144 − 5000 = 1144 = 6144 - 5000 = 1144 = 6144 − 5000 = 1144 Why this step? The last block holds only 5000 − 4096 = 904 5000-4096=904 5000 − 4096 = 904 2048 − 904 = 1144 2048-904=1144 2048 − 904 = 1144
Worked example Average-case estimateIf process sizes are random relative to block size, the last block is on average half full . So expected internal waste per process ≈ B / 2 \approx B/2 ≈ B /2 Why? The leftover S m o d B S \bmod B S mod B [ 0 , B ) [0,B) [ 0 , B ) B − ( S m o d B ) B - (S\bmod B) B − ( S mod B ) B / 2 B/2 B /2 Takeaway: smaller blocks → less internal fragmentation, but more page-table overhead.
Definition External fragmentationTotal free memory is sufficient to satisfy a request, but it is split into non-contiguous holes , none individually large enough. The waste lives between allocations.
Intuition WHAT it feels likeA cinema has 50 empty seats, but a family of 6 can't sit together because the empties are scattered one-by-one across rows. Plenty of free seats; no usable block.
With variable-size allocation, after many allocate/free cycles the free list looks like Swiss cheese:
[ Used ][ free 40K ][ Used ][ free 30K ][ Used ][ free 50K ]
A request for 100K fails even though 40 + 30 + 50 = 120 K 40+30+50 = 120\text{K} 40 + 30 + 50 = 120 K
Holes: 40K, 30K, 50K. Total free = 120 =120 = 120 = 50 =50 = 50 = 1 − 50 / 120 = 0.583 = 1 - 50/120 = 0.583 = 1 − 50/120 = 0.583 Why this matters? Over half the free memory is unusable for any request bigger than 50K.
Shuffling allocated blocks together at one end of memory so all free holes merge into one large contiguous block . Solves external fragmentation. Requires relocatable code (dynamic address binding at run time, usually via a relocation/base register).
Slide everyone in the cinema to the front so all empty seats pool at the back — now the family of 6 fits. We can only do this if seats aren't nailed down (addresses must be re-bindable at runtime).
Worked example Before → AfterBefore: [A][free40][B][free30][C][free50]
After: [A][B][C][ free 120K (contiguous) ]
A 100K request now succeeds . Why? Holes summed to 120K; merging them gives one usable block.
Intuition Cost (why we don't compact constantly)Compaction copies memory and pauses processes ("stop the world"). Cost ∝ bytes moved. It's expensive, so OSes prefer to avoid external fragmentation in the first place → paging (fixed frames) eliminates external fragmentation entirely, paying only a small internal price.
Common mistake "Compaction fixes internal fragmentation."Why it feels right: compaction "tidies memory," so surely it removes all waste. The fix: internal waste lives inside a block the process owns — moving the block keeps the tail-waste with it. Compaction only merges the external gaps. Compaction → external only.
Common mistake "Paging causes external fragmentation."Why it feels right: processes are scattered across non-contiguous frames, looks fragmented. The fix: any free frame can serve any request because all frames are identical fixed size — so there are no unusable external holes . Paging trades it for internal fragmentation (last partial page). Paging: no external, some internal.
Common mistake "Smaller blocks are always better."Why it feels right: smaller block ⇒ smaller wasted tail ⇒ less internal fragmentation. The fix: tiny blocks mean a huge page table and more management overhead. It's a trade-off, not a free win.
Internal
External
Where waste is
inside allocated block
between blocks
Caused by
fixed-size allocation
variable-size allocation
Scheme
paging, fixed partitions
segmentation, dynamic partitions
Cured by
smaller blocks (limited)
compaction , paging
Recall Feynman: explain to a 12-year-oldImagine your toy box only fits toys in fixed-size bags. If your toy is small but the bag is big, the empty space in the bag is wasted — that's internal waste, inside the bag. Now imagine instead you have free shelf gaps between toys: lots of little gaps add up to plenty of space, but none is wide enough for a big toy. That's external waste. Compaction is pushing all the toys to one side so the gaps join into one big free space — now the big toy fits!
Mnemonic Remember the two"IN side is IN ternal, between is eX ternal (X = the gaps in between)."
And: C ompaction C onnects gaps → only fixes the eX ternal kind.
What is internal fragmentation? Memory allocated to a process but unused, wasted because allocation is in fixed-size blocks; the waste lies inside an allocated block.
What is external fragmentation? Total free memory is enough for a request but it's split into non-contiguous holes, none individually large enough.
Formula for internal fragmentation of one allocation (size S, block B)? ⌈ S / B ⌉ ⋅ B − S \lceil S/B\rceil \cdot B - S ⌈ S / B ⌉ ⋅ B − S .
Average internal waste per process relative to block size B? About
B / 2 B/2 B /2 (last block half-full on average).
External fragmentation ratio formula? 1 − largest free block total free memory 1 - \dfrac{\text{largest free block}}{\text{total free memory}} 1 − total free memory largest free block .
What does compaction do and which fragmentation does it cure? Slides allocated blocks together so free holes merge into one contiguous block; cures external fragmentation only.
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; it trades external for some internal fragmentation.
Why are smaller blocks not always better? Less internal waste but larger page tables and more management overhead — a trade-off.
Does compaction fix internal fragmentation? No — internal waste moves with the block; only external gaps are merged.
but adds page-table overhead
Intuition Hinglish mein samjhoDekho, memory ek limited resource hai aur OS use chunks me deta hai. Do tarah ki fragmentation hoti hai. Internal fragmentation tab hoti hai jab block fixed-size ka ho — jaise paging me frame fixed hota hai. Agar process ko 5000 byte chahiye aur block 2048 byte ka hai, to 3 block dene padenge (6144 byte), aur 1144 byte block ke andar waste ho jaate hain. Ye waste process ke paas hai par use nahi ho raha — isliye "internal".
External fragmentation tab hoti hai jab allocation variable-size ho (segmentation ya dynamic partition). Process aate-jaate rehte hain, aur beech-beech me chhote-chhote free holes ban jaate hain. Total free memory kaafi hoti hai (maan lo 120K) par koi single hole itna bada nahi ki request (100K) fit ho — gaps scattered hote hain. Cinema me 50 khaali seats par 6 logon ka family ek saath nahi baith pa raha — wahi feeling.
Compaction iska ilaaj hai: saare allocated blocks ko ek taraf khisko do, taaki saare free holes mil ke ek bada contiguous block ban jaaye — ab 100K wali request pass ho jaayegi. Par yaad rakho: compaction sirf external fix karta hai, internal nahi (kyunki internal waste block ke andar hota hai, block ke saath hi move ho jaata hai). Compaction mehnga hai (memory copy karni padti, processes ruk jaate), isliye OS often paging use karta hai jo external fragmentation hi nahi banne deta — bas thoda internal cost deta hai. Yahi 80/20 funda hai: "Internal = andar chhupa waste, External = total enough par koi single piece bada nahi."
