A contiguous allocator gives each request one continuous region of memory. Repeated allocation and release scatter free space into holes. A large request can fail even when their combined size would be sufficient.
A 100 KB memory allocation simulator illustrating external fragmentation
1. Choose how to select a free hole
2. Request memory or play the example
Colored blocks are allocated; hatched areas are free. Click an allocated block to release it. Try Play example to see a complete scenario.
Three allocation policies
First-fit scans from the beginning and uses the first hole large enough for the request. The search is usually quick.
Best-fit chooses the smallest suitable hole. Although the leftover looks efficient, it may create many tiny unusable holes.
Worst-fit uses the largest hole to leave a large remainder. However, large holes can disappear quickly, making later large requests difficult.
External fragmentation
External fragmentation occurs when enough total space is free but it is scattered into holes too small for a contiguous request. Compare total free space with the largest free hole above.
Compaction moves allocated blocks together to create one large free region. Paging divides memory into fixed-size units so allocations need not be contiguous. Modern operating systems primarily use paging.