What Causes External Fragmentation and How Is It Solved?
What causes external fragmentation and how compaction and paging solve it — explained with examples and an OS interview question.
Expected Interview Answer
External fragmentation happens when free memory becomes scattered into many small, non-contiguous holes so that even though total free space is sufficient, no single hole is large enough to satisfy a new allocation request, and it is solved by compaction, paging, or segmentation with paging.
As processes are repeatedly allocated and freed in contiguous memory, the freed holes end up interspersed between still-allocated blocks, so the free space becomes fragmented into pieces too small individually to be useful even though their sum is large. Compaction physically shuffles allocated blocks together to merge all free holes into one large contiguous region, but it is expensive because it requires copying live memory and relocating references, so it is normally done rarely and preferably when the system is idle. The more common long-term solution is to abandon contiguous allocation altogether: paging divides physical memory into fixed-size frames and a process’s address space into equal-size pages, so any free frame anywhere in memory can satisfy any page request, eliminating external fragmentation by construction (at the cost of a small amount of internal fragmentation in the last page). Segmentation with paging combines logical segmentation for the programmer’s view with paged allocation underneath, getting both benefits. Most production operating systems today rely on paging precisely because it sidesteps external fragmentation entirely rather than trying to allocate around it.
- Explains why free memory can be plentiful yet unusable
- Compaction: merges holes, but costly to run frequently
- Paging: eliminates external fragmentation structurally
- Foundation for understanding why modern OSes use paging
AI Mentor Explanation
External fragmentation is like a stadium car park where cars have parked and left all day, leaving scattered single-car gaps between other parked cars — plenty of total empty space exists, but no gap is long enough for a team bus to park. Compaction is like staff asking every driver to shift forward so all the gaps merge into one long space at the end, which takes time and cooperation. Paging is like switching to numbered individual parking bays anywhere in the lot, so the bus is simply split across several separate bays instead of needing one contiguous stretch.
Step-by-Step Explanation
Step 1
Repeated alloc/free
Processes are allocated and freed over time in contiguous memory, leaving scattered holes between live blocks.
Step 2
Fragmentation appears
Total free space is sufficient, but no single hole is large enough for a new request.
Step 3
Compaction (short-term fix)
The OS relocates allocated blocks together to merge all holes into one contiguous region, updating references.
Step 4
Paging (structural fix)
Fixed-size frames let any free frame satisfy any page request, eliminating the need for contiguous allocation entirely.
What Interviewer Expects
- A precise definition distinguishing external from internal fragmentation
- Compaction as a valid but costly mitigation
- Paging (or segmentation with paging) as the structural solution
- Awareness of the trade-off compaction/paging introduce
Common Mistakes
- Confusing external fragmentation with internal fragmentation
- Thinking compaction is free or instantaneous
- Not knowing paging removes external fragmentation by design
- Assuming best-fit allocation alone solves fragmentation
Best Answer (HR Friendly)
“External fragmentation happens when free memory ends up scattered into small unusable pieces instead of one usable block, even though there is technically enough free space in total. Operating systems either periodically shuffle memory together to merge the gaps, which is costly, or — more commonly today — avoid the problem altogether by breaking memory into small fixed-size pieces so any request can be satisfied from scattered free pieces without needing one contiguous chunk.”
Code Example
struct hole { int start; int size; };
int total_free(struct hole *holes, int n) {
int total = 0;
for (int i = 0; i < n; i++) total += holes[i].size;
return total;
}
int largest_hole(struct hole *holes, int n) {
int max = 0;
for (int i = 0; i < n; i++)
if (holes[i].size > max) max = holes[i].size;
return max;
}
/* Fragmented if enough total free space exists but no single hole fits */
int is_fragmented(struct hole *holes, int n, int request) {
return total_free(holes, n) >= request && largest_hole(holes, n) < request;
}Follow-up Questions
- How is internal fragmentation different from external fragmentation?
- Why is compaction expensive, and when does an OS typically run it?
- How does the buddy allocation system reduce fragmentation?
- Does paging fully eliminate all fragmentation, or just external fragmentation?
MCQ Practice
1. External fragmentation occurs when?
External fragmentation is free space split into non-contiguous pieces, none large enough alone, even though the sum is sufficient.
2. What does compaction do to address external fragmentation?
Compaction physically moves live allocations together so all free space consolidates into a single usable block.
3. Why does paging eliminate external fragmentation?
Since pages map to any available frame independently, scattered free frames remain fully usable without needing to be contiguous.
Flash Cards
What is external fragmentation? — Free memory scattered into holes too small individually to satisfy a request, despite sufficient total free space.
What is compaction? — Relocating allocated blocks to merge scattered free holes into one contiguous region.
Why does paging avoid external fragmentation? — Fixed-size frames let any free frame satisfy any page request, so contiguity is never required.
Does paging cause any fragmentation? — Yes — a small amount of internal fragmentation in the last, partially used page.