Codex @codex  0

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.^[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.

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.^[ref]

The illustrative measure $1-L_{\max }/F_{\mathrm{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.

A free list records free memory regions or reusable allocation units so an allocator can find storage for a request. In a variable-size pool, a record typically needs a block's location and length. A linked implementation also stores a link to another free record; these records can occupy the free blocks themselves. The term can also describe the allocator's logical inventory when its search structure is more elaborate than one linked chain.^[ref]

For an illustrative inventory of free extents of16,32 and48 bytes, a24-byte request cannot use the first extent but can use either later one, before metadata and alignment are counted. Choosing the32-byte extent leaves an8-byte remainder if split exactly. Whether that remainder can become a free-list entry depends on the minimum free-block size.

Suppose an explicitly hypothetical in-block free record needs an8-byte length field and an8-byte next-link field. Its16-byte metadata cannot fit in that8-byte remainder. The allocator can instead give the request the entire32-byte block, leaving8 bytes of internal fragmentation, or choose another layout or block. Metadata placement is therefore part of allocation capacity, rather than an afterthought.

When a block is returned, memory block coalescing can combine it with adjacent free neighbors and update the inventory. Address order can make adjacency checks convenient; other orderings can favor allocation searches. A list that contains enough total free bytes may still lack one sufficiently large extent, producing external memory fragmentation. The search policy, split rule, metadata layout and coalescing policy jointly determine which requests succeed.

The largest free memory block is the longest contiguous free region available within a specified allocation pool and address space. If free-block lengths are $s_1,\dots ,s_n$,For an empty free-block set, take $L_{\max }=0$. The largest block and total free capacity answer different questions: a contiguous request can fail even when $F_{\mathrm{free}}$ exceeds its size. This is the central layout issue in external memory fragmentation.^[ref]

For free lengths24,40 and16 bytes, $F_{\mathrm{free}}=80$ bytes and $L_{\max }=40$ bytes. A48-byte contiguous request fails in that fixed, nonmoving pool before metadata and memory alignment are considered. Coalescing an additional freed separator can increase $L_{\max }$ without requiring the allocator to obtain another region from the operating system.

Raw extent length can overstate payload capacity. For a block $[a,b)$, an illustrative header requirement $h$ and payload alignment $A$, choose aligned payload startThe aligned free-block capacity in this simple layout is $\max (b-p,0)$. A32-byte block starting at0 with an8-byte header and16-byte payload alignment has $p=16$ and only16 bytes of payload capacity. A24-byte payload therefore fails despite a raw32-byte extent. Actual allocator layouts can impose further constraints.

The quantity also depends on the allocation layer. A large virtually contiguous block need not occupy contiguous physical page frames. Comparing $L_{\max }$ values without specifying virtual versus physical space, allocator pool and usable payload convention can therefore mix distinct fragmentation problems.

Memory allocation reserves computer memory for a program’s data and makes that storage accessible through memory addresses. Allocation determines where data can live and how long the storage remains available; initialization determines the data’s initial value. A language can arrange storage automatically for local variables, retain storage for the duration of a program, or request storage dynamically while the program runs.

In the C programming language, malloc(n) requests a block of $n$ bytes and returns a pointer to it, or a null pointer if allocation fails. Successful allocation does not initialize those bytes. The free operation releases a previously allocated block for subsequent allocation; accessing it through an old pointer is no longer valid.^[ref][ref] Allocation and deallocation are therefore separate from reading and writing an object. Deallocation need not erase its former contents or immediately return its storage to the operating system.

For a process using virtual memory, a contiguous interval of memory addresses does not require a contiguous interval of physical memory. The memory management unit can map successive virtual pages to different physical page frames. Conversely, a successful small allocation may be satisfied from an existing free block without asking the operating system for another page.

Two small bookkeeping examples explain why free capacity alone does not determine whether an allocation succeeds. If an allocator rounds a 17-byte request up to a 32-byte allocation unit, 15 bytes are unused inside that unit: internal fragmentation, before counting any allocator metadata. If two free 32-byte blocks are separated by an occupied block, a request for one contiguous 48-byte block cannot fit in either hole, even though 64 bytes are free. That is external memory fragmentation, under the assumption that the occupied block cannot be moved and no further storage is available. Adjacent free blocks can sometimes be combined; separated ones require a different placement or movement strategy.