Dynamic allocation results in fragmentation. Since we allocate in contiguous blocks, and we can’t move memory around after allocation (for the programmer’s sanity), we get fragments: small contiguous blocks of memory that can’t handle allocation (like a “hole” in memory). There are three requirements for fragmentation:
- Different allocation lifetimes
- Different allocation sizes
- Inability to relocate previous allocations
External fragmentation: allocate different sized blocks, no room for an allocation between the blocks Internal fragmentation: allocate fixed sized block, so wasted space within a block
Allocators want to minimise fragmentation