= External memory fragmentation
<External memory fragmentation> occurs when free capacity is divided among separated blocks so that a request for one sufficiently large contiguous block cannot be satisfied. It concerns the layout available to a particular allocator, rather than only the total free <computer memory>. In a fixed nonmoving pool, occupied blocks can separate free intervals that would have been useful if adjacent.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others>[Chapter17, “Free-Space Management”, introduction and §17.1, variable-size allocation and nonrelocatable live blocks]{ref}
For an original example, a104-<byte> pool contains free blocks of24,40 and16 <bytes>, separated by occupied blocks of16 and8 <bytes>. Total free capacity is80 <bytes>, but the <largest free memory block> is only40 <bytes>. A contiguous48-<byte> request therefore fails in this closed pool, assuming live blocks cannot move and ignoring metadata/alignment overhead.
\Image[/external-memory-fragmentation.png]
{title=Separated free blocks with enough total capacity but no contiguous48-byte allocation}
<Memory block coalescing> merges adjacent free intervals. If the occupied16-<byte> block between the first two holes is released, the neighboring24,16 and40-<byte> intervals can form one80-<byte> free block. Coalescing does not merge across a still-occupied interval. <Memory compaction> instead moves live data to collect free space, which requires a way to preserve or update references. An allocator generally cannot relocate an arbitrary live block behind an unchanged <C programming language> <pointer>.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others>[§17.1, relocation assumption; §17.2, splitting and coalescing]{ref}
The illustrative measure $1-L_{\max}/F_{\rm free}$ equals0.5 for the original layout, but it does not say that half the memory is universally unusable: requests no larger than16 <bytes> can still fit. Actual allocation success depends on request sizes and allocator policy. <Internal fragmentation> instead concerns unused space inside allocated units.
The contiguity requirement also needs its address space specified. A virtually contiguous block can use noncontiguous physical <page frames> through <virtual memory>. Physical page fragmentation and an application's heap holes are therefore different allocation-layer questions. Changing the physical mapping alone does not merge separated virtual holes around live objects.
Back to article page
