external fragmentation

Imagine a parking lot that is half empty, but the empty spaces are single gaps scattered between parked cars — one here, two there. A bus arrives needing three spaces in a row, and there is nowhere to put it, even though plenty of total space is free. External fragmentation is exactly this: enough free memory exists in total, but it is broken into small pieces, none large enough for the request.

Concretely, external fragmentation happens with contiguous allocation as processes start and finish at different times. Each time a process leaves, it returns its block as a hole; each time one is placed, it carves a hole and leaves a smaller remainder. Over time the free memory becomes a checkerboard of holes. A new process needs one contiguous run, so even if the sum of all holes is far bigger than the process, it may not fit because no single hole is big enough. The wasted space lies outside (between) the allocated blocks — hence external.

Why it matters: external fragmentation is the central flaw of contiguous allocation, and no choice of first-fit, best-fit, or worst-fit cures it — they only reshape the leftovers. The two real cures are compaction (shuffle the in-use blocks together to merge the holes, which is costly) and, more decisively, paging, which lets a process occupy many non-contiguous frames so it never needs one big contiguous run at all. Contrast this with internal fragmentation, where the waste is inside an allocated block.