External memory fragmentation 2026-11-05
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]
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
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]
Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others. §17.1, relocation assumption; §17.2, splitting and coalescing
The illustrative measure 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.
Free list 2026-11-05
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.
Memory allocation 2026-11-05
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 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.
Minimum free-block size 2026-11-05
The minimum free-block size is the smallest extent that an allocator's representation can retain as an independent free record. It depends on where the allocator stores a region's size, links and other metadata, as well as memory alignment. A region may contain unused bytes yet be too short to enter the free list. OSTEP demonstrates why allocator metadata must be counted: free records can be embedded inside the free regions themselves.[ref]
For a hypothetical allocator, let a free record need an8-byte size field and two8-byte links. Its raw metadata requires24 bytes. If all block lengths are multiples of16 bytes, its minimum independently representable size isThe exact fields and sizes are illustrative. An allocator with separate metadata, a singly linked record or another block granularity can have another minimum.
Suppose the same allocator uses an8-byte allocated-block header. An8-byte payload plus that header would occupy16 bytes before enforcing the minimum. Reserving32 bytes ensures that this block can later become an independent free record. Extra allocation space of this kind contributes to internal fragmentation. The allocator might instead use a distinct representation for tiny blocks, so the formula is a design constraint for the stated representation rather than a universal allocation rule.
A proposed split also needs to respect the minimum. Taking80 bytes from a96-byte extent leaves16 bytes, an unsplittable free-block remainder under this layout. Giving the caller the full96-byte extent avoids making an invalid free record but consumes extra storage. Taking32 bytes would leave64, which can be retained. Memory block coalescing can later join adjacent returned extents, but the allocator must have a valid way to represent each extent until that happens.
A hard disk drive pays substantial seek time to position the head and rotational latency to reach the desired sector. After that positioning, neighboring bytes stream past the head quickly. A larger transfer therefore amortizes positioning and command overhead over many bytes.
The physical sector also needs framing, synchronization and error-correcting redundancy. Transferring one byte at a time would spend an excessive fraction of the medium and controller work on that overhead. A controller buffer and a block transfer can efficiently deliver the sector to computer memory, often using direct memory access.
ThusThe choice is a compromise: excessively large blocks waste transfer time for small requests and can increase internal fragmentation in a file system.
Let a disk block number and a file number each occupy bytes. System B spends about bytes per physical block on successor/count, predecessor and owner, leaving payload bytes. It also needs its per-file header. In the traditional inode scheme, file data blocks are entirely payload; indexing occupies the fixed inode and separate indirect blocks.
For data blocks in a large densely occupied indirect tree, about lowest-level index blocks, next-level blocks and so on are needed. With , the asymptotic indexing space is approximatelyor about bytes when is large. ThusThis is a comparison of typical densely used structures. For a small file, the fixed inode dominates; near an indirect-level boundary, partly empty index blocks add overhead. Both schemes can waste part of the last block through internal fragmentation.
The main performance advantage is indexed access to an arbitrary file offset: the inode finds the required data block with at most three indirect levels, whereas System B may need to follow a long chain from one end. Index blocks can be cached and scanned in batches, leaving complete data blocks for transfers. The inode scheme also naturally supports sparse files, where absent data-block pointers represent zero-filled holes without allocating every intervening block.
There are additional costs. A cold lookup can require separate index-block reads, allocation near a boundary can require allocating and updating several index blocks, and small files can pay more fixed metadata cost. System B already has a tail pointer and can append with local chain updates, while its owner and predecessor fields can help recovery from surviving blocks. Losing a UNIX indirect block can disconnect many data blocks, and those blocks do not automatically carry System B's owner information. Thus the space and file offset access advantages do not imply uniformly cheaper updates or uniformly better recovery.
Unsplittable free-block remainder 2026-11-05
An unsplittable free-block remainder is the positive suffix left by a proposed allocation that is too small to retain as a valid independent free list record. Its size is below the allocator's minimum free-block size. The region still contains unused bytes, but the chosen representation cannot manage it as a separate free extent. The issue arises because free-region metadata can occupy the regions themselves.[ref]
Let a chosen block have size , let the proposed allocated extent after header/alignment rounding be , and let the minimum free size be . With remainder , an allocator that absorbs an undersized suffix usesThis is one possible policy, not a mandatory allocator interface. The absorbed suffix adds bytes of internal fragmentation beyond the bookkeeping and rounding already included in .
For an original example, take bytes, an8-byte allocated header,16-byte block granularity and bytes. A56-byte payload gives , leaving a representable32-byte free block. A57-byte payload instead gives , leaving an unusable16-byte suffix. Absorbing it reserves all96 bytes. Increasing the request by just one byte has therefore increased this allocation's occupied extent by32 bytes.
If and all extents are multiples of a granularity , a positive absorbed suffix is at most bytes. Without that granularity condition, the general integer-byte bound is . Choosing another free block or another representation can change the tradeoff. Later memory block coalescing can recover adjacent space when allocations are returned, but it does not make an invalid intermediate free record representable.
