What Is Fragmentation?
Learn internal vs external memory fragmentation, how paging and compaction address it, with code and interview-ready answers.
Expected Interview Answer
Fragmentation is the wasted memory that builds up as blocks are allocated and freed over time, leaving usable space scattered in pieces too small or too oddly placed to satisfy new requests.
External fragmentation happens when free memory is broken into many small, non-contiguous holes between allocated blocks, so even though total free space is enough, no single hole is large enough for a new request. Internal fragmentation happens when a fixed-size allocation unit (like a page or a block) is larger than what a process actually needs, wasting the leftover space inside that unit. Operating systems fight external fragmentation with paging or compaction, and fight internal fragmentation by choosing allocation granularities that balance overhead against waste. Both forms reduce effective memory utilization even when raw free memory looks plentiful.
- Explains why free memory totals can be misleading
- Distinguishes external vs internal fragmentation clearly
- Connects to real OS mitigations: paging, compaction, slab allocation
- Shows up directly in memory allocator and GC interview questions
AI Mentor Explanation
A stadium sells seats in a single long row, and as fans buy and leave in random clusters, the empty seats end up scattered as isolated singles and doubles across the row. A group of six friends cannot sit together anymore even though six total seats are free, because no six are adjacent — that scattering is external fragmentation. If instead the stadium sells seats only in fixed blocks of four and a group of three buys a block, the unused fourth seat is wasted internal fragmentation. Reorganizing fans into a fresh block of adjacent seats mirrors compaction.
Step-by-Step Explanation
Step 1
Allocate and free
As processes request and release memory blocks of varying sizes, holes of different sizes appear between allocated regions.
Step 2
External fragmentation
Free space exists but is split into small non-contiguous holes, so a large request fails despite enough total free memory.
Step 3
Internal fragmentation
Fixed-size allocation units (pages, blocks) are bigger than the request, wasting the leftover space inside the unit.
Step 4
Mitigation
Paging avoids external fragmentation by using fixed-size frames; compaction physically moves data to merge holes; slab allocators reduce internal waste for common sizes.
What Interviewer Expects
- Clear distinction between internal and external fragmentation
- Why paging eliminates external fragmentation but not internal
- Awareness of compaction and its cost (requires stopping the world briefly)
- A concrete example of each type, not just definitions
Common Mistakes
- Using "fragmentation" as one vague term without splitting internal vs external
- Claiming paging removes fragmentation entirely
- Forgetting that compaction has a real runtime cost
- Confusing disk fragmentation with memory fragmentation
Best Answer (HR Friendly)
“Fragmentation is wasted memory that piles up over time. External fragmentation is when free memory is scattered in small pieces so a big request cannot find a contiguous slot, even though enough total space is free. Internal fragmentation is when a fixed-size chunk given to a process is bigger than what it actually needs, wasting the leftover inside that chunk.”
Code Example
#include <stdio.h>
#define POOL_SIZE 100
typedef struct Block {
int start;
int size;
int free;
struct Block *next;
} Block;
/* After many alloc/free cycles, free blocks end up scattered:
[used 0-19][free 20-29][used 30-49][free 50-54][used 55-79][free 80-99]
Total free = 10 + 5 + 20 = 35, but the largest contiguous free
run is only 20 -- a request for 30 fails despite 35 being free. */
int find_contiguous(Block *head, int needed) {
for (Block *b = head; b != NULL; b = b->next) {
if (b->free && b->size >= needed) {
return b->start;
}
}
return -1; /* external fragmentation: no single hole is big enough */
}
int main(void) {
Block b3 = {80, 20, 1, NULL};
Block b2 = {55, 25, 0, &b3};
Block b1 = {50, 5, 1, &b2};
Block b0 = {30, 20, 0, &b1};
Block head = {20, 10, 1, &b0};
int addr = find_contiguous(&head, 30);
printf("Address for 30 units: %d\n", addr); /* prints -1 */
return 0;
}Follow-up Questions
- How does paging prevent external fragmentation?
- Why does the buddy allocator trade some internal fragmentation for fast merging?
- What is memory compaction and why is it expensive?
- How do slab allocators reduce internal fragmentation for kernel objects?
MCQ Practice
1. External fragmentation occurs when:
External fragmentation is free space scattered across many small non-adjacent holes, not a shortage of total free memory.
2. Internal fragmentation is best described as:
Internal fragmentation is the leftover unused space inside a fixed-size unit like a page or block once a smaller request is placed in it.
3. Which technique directly addresses external fragmentation by relocating in-use blocks?
Compaction physically moves allocated blocks together to merge scattered free holes into one contiguous region.
Flash Cards
External fragmentation — Free memory split into small, non-contiguous holes so large requests fail despite enough total free space.
Internal fragmentation — Wasted space inside a fixed-size allocation unit that is bigger than the actual request.
Compaction — Moving allocated blocks together to merge scattered free holes into one contiguous region; costly at runtime.
Paging vs fragmentation — Paging avoids external fragmentation using fixed-size frames, but can still cause internal fragmentation in the last partial page.