Fragmentation and Compaction
The two types of fragmentation
Memory allocation strategies inevitably leave portions of physical memory unused. The wasted space falls into two categories:
External fragmentation exists when the total free memory is enough to satisfy a request, but no single contiguous block is large enough. The free space is scattered in fragments between allocated regions. This is the hallmark of segmentation and variable-sized partition schemes.
Internal fragmentation exists when memory is allocated in fixed-size units (e.g., pages, or fixed partitions) and the requested size is not an exact multiple of the unit size. The unused bytes inside the allocated unit are internal fragmentation. Paging minimises external fragmentation at the cost of internal fragmentation (the last page of a segment is typically partially filled).
The 50-percent rule (a heuristic)
For a first-fit variable-partition allocator under statistical assumptions (allocations and deallocations equally likely, various sizes), roughly one-third of memory is wasted in external fragmentation on average. This is a rule of thumb; real behaviour depends on the workload’s allocation patterns.
Compaction
Compaction reassembles all free memory into one contiguous block by moving allocated segments together. With execution-time binding, compaction is straightforward: update the base registers of each segment that was moved. No data copying is needed (well, the data must move, but the MMU remaps it — actually, compaction does involve copying data; the point is that programmes don’t need to be relinked).
Compaction cost grows with the amount of memory being moved, and the system must be paused (or at least the affected processes suspended) while it happens. This is one reason paging superseded pure segmentation: paging never needs compaction.
Fragmentation in paging
Paging eliminates external fragmentation entirely. Physical memory is divided into fixed-size frames (say 4 KB). The OS maintains a free-frame list. Any free frame can satisfy any page request — there is no requirement for contiguous allocation. The only fragmentation is internal: the last page of a segment is rarely exactly 4 KB. At most, one page per process wastes up to 4095 bytes (half a page on average).
Fragmentation comparison
| Scheme | External fragmentation | Internal fragmentation |
|---|---|---|
| Contiguous allocation (base/limit) | Yes — primary problem | None |
| Segmentation (variable sizes) | Yes — primary problem | None |
| Paging (fixed sizes) | None | Yes — last page of each segment, average 2 KB/page wasted |
| Paged segmentation | Minimal (segments are paged) | Yes — within pages |
Summary
- External fragmentation: free space scattered; allocation fails despite sufficient total free memory.
- Internal fragmentation: waste inside an allocated block because the request is smaller than the allocation unit.
- Paging eliminates external fragmentation; compaction is the (expensive) cure for segmentation.
- A single page of internal fragmentation per process segment is the price paging pays.