Difficulty: Beginner
What is fragmentation? Explain internal and external fragmentation, contiguous allocation strategies (first, best, worst fit) and the ways to reduce fragmentation.
Fragmentation is a simple idea that trips up many people because the two flavours have confusing names. The everyday picture is a parking garage. If every parking slot is a fixed size, a small car wastes some space in its slot: that unused space is inside an allocated slot, and nobody else can use it. That is internal fragmentation. Now imagine a lot with no marked slots where cars of different sizes come and go. After many arrivals and departures you end up with many small gaps between cars. The total free space may be enough for a bus, but no single gap is big enough. That is external fragmentation.
Internal fragmentation occurs when memory is allocated in fixed-size blocks and the process does not need the whole block. The wasted space lies inside the allocated block. Paging is the standard example: if a process needs 10,000 bytes and pages are 4,096 bytes, it needs 3 pages (12,288 bytes), and the last page wastes 2,288 bytes. On average, about half a page per process is wasted. Fixed-partition memory schemes and buddy allocators also show this, since requests are rounded up to a power of two.
External fragmentation occurs with variable-size allocation, such as dynamic partitioning or segmentation. As processes are loaded and terminated, free memory breaks into many non-contiguous holes. Enough total memory may be free, yet a request cannot be satisfied because no single hole is large enough. Related is the 50 percent rule: with first fit, roughly one third of memory may become unusable due to fragmentation.
To choose which hole to allocate from, allocators use placement strategies. First fit takes the first hole big enough; it is fast and typically performs well. Next fit continues from where the last search ended. Best fit picks the smallest hole that fits; it minimizes leftover size but scans the whole list and tends to create many tiny useless slivers. Worst fit picks the largest hole, hoping the remainder is still usable, but it is generally the poorest performer in simulations.
Consider a small example. Holes are 100 KB, 500 KB, 200 KB, 300 KB, 600 KB in order, and requests are 212 KB, 417 KB, 112 KB and 426 KB. First fit places 212 in 500 (leaving 288), 417 in 600 (leaving 183), 112 in the 288 remainder (leaving 176), and 426 finds no hole: it must wait. Best fit places 212 in 300, 417 in 500, 112 in 200, and 426 in 600, satisfying all four. Worst fit places 212 in 600, 417 in 500, 112 in the 388 remainder, and 426 must wait. This shows that no strategy always wins.
How do we reduce fragmentation? For external fragmentation, compaction shuffles the used memory together to create one large hole; it needs run-time relocation and is expensive. The better solution is non-contiguous allocation: paging eliminates external fragmentation entirely because any frame can hold any page. Segmented paging and buddy or slab allocation also help. For internal fragmentation, use smaller page sizes, although that increases page table size, or size-classed allocators such as slab allocation in the Linux kernel which pre-sizes objects.
The summary line to give: internal fragmentation is waste inside allocated memory, external fragmentation is waste between allocations, paging trades external for internal, and segmentation does the reverse.
fragmentation, internal fragmentation, external fragmentation, compaction, memory allocation