Internal vs External Fragmentation
Learn the difference between internal and external fragmentation in memory management, with paging and compaction examples.
Expected Interview Answer
Internal fragmentation is wasted space inside an allocated block because it is larger than what was requested, while external fragmentation is wasted space between allocated blocks — free memory that exists in total but is scattered into pieces too small individually to satisfy a new request.
Internal fragmentation happens when an allocator hands out fixed-size chunks — such as pages, buddy-system power-of-two blocks, or slab objects — and a request smaller than the chunk size still consumes the whole chunk, leaving the leftover space inside that block permanently unusable by anyone else until the block is freed. External fragmentation happens with variable-sized allocation, such as a heap using first-fit or best-fit over contiguous memory: as blocks of different sizes are allocated and freed over time, the free memory ends up split into many small, non-contiguous holes, so even though the sum of free space might satisfy a large request, no single hole is big enough. Paging largely eliminates external fragmentation for physical memory because pages are fixed-size and any free page can back any needed page, but paging trades this for internal fragmentation on the last partially used page of each allocation. Compaction (relocating allocated blocks to consolidate free space) fixes external fragmentation but cannot help with internal fragmentation, since the wasted space is trapped inside blocks that are already in use.
- Distinguishes two root causes of wasted memory, guiding the right fix for each
- Explains why paging trades external fragmentation for internal fragmentation
- Clarifies why compaction only helps external, not internal, fragmentation
- Foundation for reasoning about buddy system, slab, and segmentation trade-offs
AI Mentor Explanation
Internal fragmentation is like reserving a full team dressing room for a single player: the whole room is theirs, but most of the space inside sits unused for the entire session. External fragmentation is like a stadium with plenty of empty seats overall, but scattered as single seats and pairs across different stands, so a group of twenty fans travelling together cannot find one contiguous block even though enough total seats exist. The first wastes space inside a reserved unit; the second wastes space between reserved units.
Step-by-Step Explanation
Step 1
Internal fragmentation source
A fixed-size allocation unit (page, buddy block, slab slot) is larger than the request, wasting space inside it.
Step 2
External fragmentation source
Variable-sized allocation and deallocation over time splits free memory into small, scattered, non-contiguous holes.
Step 3
Detection
Internal waste is measured per allocated block; external waste is measured by comparing total free memory to the largest contiguous free hole.
Step 4
Mitigation
Internal: choose allocation granularity carefully (slabs for common sizes). External: use paging, or compact/relocate blocks to merge holes.
What Interviewer Expects
- A precise definition distinguishing waste inside a block vs waste between blocks
- A concrete example of each (paging for internal, heap fragmentation for external)
- Understanding that paging trades external fragmentation for internal fragmentation
- Knowing compaction addresses external but not internal fragmentation
Common Mistakes
- Swapping the two definitions
- Claiming paging eliminates fragmentation entirely
- Thinking compaction can reduce internal fragmentation
- Not being able to give a concrete example of either type
Best Answer (HR Friendly)
“Internal fragmentation is wasted space stuck inside a chunk of memory that got reserved but is not fully used. External fragmentation is wasted space scattered between reserved chunks — the free memory adds up to enough, but it is broken into pieces too small individually to fit a new request. Fixed-size systems like paging tend to waste a little space inside each unit, while variable-size systems like a general heap tend to scatter free space around instead.”
Code Example
/* Internal fragmentation: waste inside one allocated block */
size_t internal_frag(size_t requested, size_t block_size) {
return block_size - requested; /* space inside the block never used */
}
/* External fragmentation: free memory exists but is too scattered */
int external_frag_blocks_request(size_t total_free, size_t largest_hole,
size_t requested) {
if (requested > total_free) return -1; /* not enough memory at all */
return (requested > largest_hole) ? 1 : 0; /* 1 = blocked despite enough total free */
}Follow-up Questions
- Why does paging eliminate external fragmentation but introduce internal fragmentation?
- How does memory compaction address external fragmentation?
- How does the slab allocator minimize internal fragmentation for common object sizes?
- How does segmentation differ from paging in terms of fragmentation trade-offs?
MCQ Practice
1. Internal fragmentation refers to?
Internal fragmentation is the unused portion left inside a block once it is larger than the actual request it serves.
2. Which technique primarily fixes external fragmentation?
Compaction moves allocated blocks together so scattered free holes merge into one large contiguous region, directly addressing external fragmentation.
3. Why does paging trade external fragmentation for internal fragmentation?
Fixed-size pages remove the scattering problem of variable-sized allocation, but an allocation that does not exactly fill its last page wastes the remainder — internal fragmentation.
Flash Cards
What is internal fragmentation? — Wasted space inside an allocated block because it exceeds the actual request size.
What is external fragmentation? — Free memory scattered into holes too small individually to satisfy a new request, despite enough total free space.
Does paging cause internal or external fragmentation? — Internal, on the last partially used page of an allocation.
What fixes external fragmentation? — Compaction (relocating blocks to merge free holes) or using fixed-size paging.