Fragmentation in Operating Systems

Fragmentation is memory that exists as free space but cannot be used because it sits in unusable gaps. External fragmentation is free memory scattered between allocated blocks, where no single gap is large enough on its own, while internal fragmentation is wasted space inside an allocated block that is bigger than what it holds.

3 min read

Fragmentation is memory that technically exists as free space but can't actually be used, because it's scattered into pieces too small or too oddly placed to satisfy a real request. There are two distinct kinds, and they come from opposite causes.

External fragmentation

External fragmentation happens with variable-sized contiguous allocation. As processes are loaded and later freed, the free memory that's left behind ends up scattered in multiple separate gaps between still-allocated blocks. Even if the total free memory across all these gaps would be more than enough for a new process, no single gap might be big enough on its own, since the new process needs one contiguous chunk.

Worked example. Physical memory has allocated blocks at 0-99 and 300-399, with two separate free gaps: 100-199 (100 units) and 400-599 (200 units). Total free memory is 300 units. A new process needs 250 contiguous units. Even though 300 units are free in total, neither individual gap (100 or 200 units) is big enough, so the request fails despite enough total free space existing. That's external fragmentation.

Internal fragmentation

Internal fragmentation happens with fixed-size allocation (like paging, which divides memory into fixed-size frames). If a process's actual memory need doesn't divide evenly into the fixed block size, the last block allocated to it is bigger than what it actually uses, and the leftover space inside that block is wasted, unusable by any other process, since the whole block is already assigned.

Worked example. Page size is 4KB. A process needs exactly 10KB. It gets allocated 3 full pages (12KB total), since a partial page can't be shared with another process. 2KB of the third page is allocated but genuinely unused, wasted internally inside a block that already "belongs" to this process. That 2KB is internal fragmentation.

The fix for each

External fragmentation is fixed by compaction (physically shifting all allocated blocks together to consolidate free memory into one contiguous chunk) or, more commonly in modern systems, by abandoning contiguous allocation entirely in favor of paging, since fixed-size blocks eliminate the "gaps between variable-size blocks" problem altogether.

Internal fragmentation, ironically, is a direct side effect of the very fix for external fragmentation (fixed-size pages). It's generally addressed by choosing a smaller page size (less wasted space per allocation, at the cost of needing more page-table entries to track more, smaller pages) rather than eliminated outright.

Where this matters in real systems

Modern operating systems overwhelmingly favor paging (fixed-size allocation) specifically because external fragmentation is the more damaging problem in practice: it can eventually make a system unable to satisfy a large request even with plenty of total free memory, whereas internal fragmentation just wastes a bounded, predictable, usually small amount per process. Linux's default 4KB page size is itself a real, deliberate tradeoff point between these two costs.

What interviewers actually ask about fragmentation

  • "What's the difference between internal and external fragmentation?" External fragmentation is free memory scattered into unusable gaps between allocated blocks (a variable-size allocation problem); internal fragmentation is wasted space inside an allocated block that's bigger than what's actually needed (a fixed-size allocation problem).
  • "Which allocation scheme causes which kind of fragmentation?" Variable-size contiguous allocation causes external fragmentation; fixed-size allocation (paging) causes internal fragmentation.
  • "How do you fix external fragmentation?" Compaction, or switching to a fixed-size allocation scheme like paging entirely.
  • "Why do most modern operating systems accept internal fragmentation instead of external fragmentation?" Because internal fragmentation is bounded and predictable (at most one partial page wasted per process), while external fragmentation can grow unpredictably and eventually block large allocations even when total free memory is sufficient.

Key takeaways

  • External fragmentation is scattered unusable gaps between variable-size allocated blocks.
  • Internal fragmentation is wasted space inside a fixed-size block bigger than what's actually needed.
  • Compaction or switching to paging fixes external fragmentation; a smaller page size reduces (but doesn't eliminate) internal fragmentation.
  • Modern systems generally accept internal fragmentation as the lesser, more predictable cost.
All 205 OS interview questions

Browse all Operating Systems topics

Log in to save which topics you've read across every subject.

Frequently asked questions

What's the difference between internal and external fragmentation?

External fragmentation is free memory scattered into unusable gaps between allocated blocks (a variable-size allocation problem); internal fragmentation is wasted space inside an allocated block that's bigger than what's actually needed (a fixed-size allocation problem).

Which allocation scheme causes which kind of fragmentation?

Variable-size contiguous allocation causes external fragmentation; fixed-size allocation (paging) causes internal fragmentation.

How do you fix external fragmentation?

Compaction, or switching to a fixed-size allocation scheme like paging entirely.

Why do most modern operating systems accept internal fragmentation instead of external fragmentation?

Because internal fragmentation is bounded and predictable (at most one partial page wasted per process), while external fragmentation can grow unpredictably and eventually block large allocations even when total free memory is sufficient.