An operating system has 35 MiB of free memory. A new process requests 30 MiB, yet the allocation fails.

There is no arithmetic mistake. The free space is split into two holes:

Neither hole is large enough to hold one continuous 30 MiB allocation.

This is the central difficulty of contiguous allocation. The allocator must find one uninterrupted address range large enough for each request. As allocations arrive and leave, free space can become divided into small pieces. The system may then have enough free bytes in total but no usable block of the required size.

That loss of usable capacity is called fragmentation.

Contiguous allocation is simple because each allocation occupies one interval. It becomes difficult because free intervals change shape over time.

Under contiguous allocation, every allocated object occupies one continuous range of physical addresses.

If a process receives a block starting at physical address base with length size, its assigned interval is:

For example:

Every physical byte assigned to the process lies between those two boundaries. No unrelated allocation can occupy a byte in the middle.

A simplified physical-memory layout might look like this:

The operating-system region is shown at low addresses only for illustration. Actual platform layouts vary. The important rule is that each process allocation is one physical interval.

This model also requires a way to prevent the process from accessing memory outside its interval and, when necessary, to let the process run without embedding one fixed physical start address into all its instructions. For this chapter, assume those protection and relocation responsibilities are provided. The focus here is how the operating system chooses and manages the intervals.

The representation is compact. For each allocation, the operating system can record a start address and a length:

Checking whether an address falls inside the interval is straightforward. Releasing the allocation is also conceptually simple: mark that interval free and see whether it touches another free interval.

The model has low bookkeeping overhead when the number of allocations is small. It works particularly well when:

Early operating systems and small embedded systems can benefit from this simplicity. Problems appear when allocation sizes and lifetimes vary unpredictably.

The simplest multi-process arrangement divides physical memory into a fixed set of partitions at system startup.

Each partition can hold at most one process. When a process arrives, the operating system selects a free partition large enough for it.

Partitions can be equal-sized or unequal-sized.

Equal partitions make selection easy, but one partition size rarely matches every workload. A process slightly larger than the partition cannot run even if several partitions are free. A small process wastes most of a large partition.

Unequal partitions support a wider range of process sizes. Small processes can use small partitions while large processes use large ones. The workload still has to match the predefined sizes reasonably well.

Fixed partitioning also limits how many processes can reside in memory at once. Four user partitions can hold no more than four processes, regardless of how little memory each process actually needs.

Its characteristic waste is internal fragmentation.

Internal fragmentation is unused space inside an allocated block.

Suppose a 50 MiB process is placed in a 64 MiB fixed partition:

The 14 MiB is physically present and belongs to the partition, but the allocator cannot give it to another process. It is internal to an allocation that is already marked busy.

For one allocation:

For the example:

If four processes request 10 MiB each and each receives a 16 MiB partition, total internal fragmentation is:

Internal fragmentation is not limited to fixed process partitions. Any allocator that rounds requests up can create it.

Suppose an allocator provides space only in multiples of 64 bytes:

Alignment, minimum block sizes, and allocation metadata can all increase the difference between useful payload and allocated size.

The important ownership test is:

If the wasted bytes lie inside a block that the allocator considers allocated, the waste is internal fragmentation.

Fixed partitions waste space when requests do not match their predefined sizes. Variable partitioning creates each partition according to the arriving request.

Start with 100 MiB of free user memory:

Allocate 20 MiB to Process A. The allocator splits the free interval:

Allocate 25 MiB to Process B, 15 MiB to Process C, and 30 MiB to Process D:

Each process receives a close match to its requested size. The large internal waste of fixed partitions is reduced.

The partition boundaries are now determined by runtime history. When Process B exits, its interval becomes a free hole:

There are 35 MiB free in total, but a 30 MiB request cannot fit. The largest hole is only 25 MiB.

This is external fragmentation.

External fragmentation occurs when free memory exists but is divided among nonadjacent holes.

For a request of size R, two values reveal the problem:

If:

then the request fails because of external fragmentation rather than a shortage of total free bytes.

In the preceding example:

The total is sufficient, but its shape is not.

The wasted capacity is called external because the holes sit outside the allocated blocks, between live allocations. Each hole is available to the allocator; it is simply too small for the current request.

Unlike internal fragmentation, external fragmentation cannot always be summarized as a fixed number of unusable bytes. A 25 MiB hole is useless for a 30 MiB request but perfectly useful for a 20 MiB request. The workload's request-size distribution matters.

A simple diagnostic score is sometimes defined as:

If all free memory forms one hole, the score is 0. As free memory is split into many similarly small holes, the score approaches 1. This is a heuristic, not a universal metric: it ignores alignment and the sizes of future requests.

A system can suffer from both at once. A variable-size allocator may round each request for alignment, producing internal slack, while the free intervals between allocations become externally fragmented.

The distinction depends on the allocator's boundary. Space that looks internal at one layer may be managed by another allocator inside that block. Always ask which allocator owns the decision and whether it can currently give those bytes to a different request.

When a free hole is larger than a request, the allocator normally splits it.

Suppose a 40 MiB request is placed in a 64 MiB hole:

The allocator records the 40 MiB interval as occupied and returns the remaining 24 MiB interval to its collection of holes.

Alignment can make the split less tidy. If the allocation must begin at a particular address boundary, the allocator may need to leave padding before it:

The prefix and suffix remain externally free if they are large enough to track and reuse. If one fragment is smaller than the allocator's minimum usable block, the allocator may absorb it into the allocation, turning it into internal fragmentation.

Splitting therefore changes both bookkeeping and future choices. A placement that satisfies today's request can leave a remainder that is either useful or too small for likely future work.

When a process releases its interval, the allocator marks the range free. It should then check whether the new hole touches an existing free hole.

Return to this state:

If Process D exits, its 30 MiB block touches the trailing 10 MiB hole. The two ranges can be coalesced:

The allocator has the same 65 MiB total free space before and after coalescing. What improves is the size of the largest hole: it grows from 30 MiB to 40 MiB.

Coalescing works only for physically adjacent intervals. The 25 MiB hole cannot merge with the 40 MiB hole because Process C lies between them.

A conceptual free operation is:

Keeping holes ordered by address makes neighbor discovery straightforward. Other organizations may accelerate allocation searches but need additional bookkeeping to find adjacent ranges during coalescing.

Coalescing should normally happen promptly. Delaying it leaves multiple small records for what is physically one large free interval and can cause avoidable allocation failures.

When several holes can satisfy a request, the allocator needs a placement policy. The choice affects search time and the pattern of remainders left behind.

First fit

First fit scans holes from the beginning and chooses the first one large enough.

It often stops searching quickly. The beginning of memory can accumulate small holes because it is examined repeatedly.

Next fit

Next fit is similar to first fit, but the next search resumes after the previous placement rather than restarting at the beginning.

It spreads searches across the address range and can reduce repeated scanning of the same prefix. Its fragmentation behavior depends heavily on request history.

Best fit

Best fit chooses the smallest hole that can satisfy the request.

The immediate goal is to preserve larger holes. Unless holes are indexed by size, finding the best candidate requires examining every hole. Best fit can also produce many tiny remainders that are difficult to reuse.

Worst fit

Worst fit chooses the largest available hole.

It tries to leave a sizable remainder instead of a tiny one. The policy can consume the allocator's best option for a future large request, and it also requires finding the largest candidate.

There is no policy that eliminates external fragmentation for arbitrary sequences of variable-sized allocations and frees. Each policy changes where and how fragmentation develops.

Consider these free-hole sizes, listed in address order:

Requests arrive for:

Assume a chosen hole is split and the unused remainder stays in the same position.

With first fit:

After the first three allocations, 959 KiB remains free, but the largest hole is 300 KiB. The 426 KiB request fails because the free space is externally fragmented.

With best fit:

Best fit happens to satisfy all four requests in this trace. That does not prove it is always superior. A different sequence can make its small remainders unusable and leave first fit with better options.

With worst fit:

This trace illustrates why placement decisions must be evaluated across a workload, not one request at a time. The best immediate remainder is not necessarily the best long-term state.

For a simple unsorted free list containing H holes, these policies can require scanning O(H) entries per allocation. Indexing holes by size can improve candidate search, but maintaining indexes and coalescing information adds complexity.

Classic analyses of first-fit allocation describe a result called the 50-percent rule.

Under assumptions about random request sizes and lifetimes in a steady workload, the expected number of free holes is approximately half the number of allocated blocks:

The name refers to the count of holes relative to allocated blocks, not a guarantee that exactly 50 percent of memory is wasted.

If average hole and allocated-block sizes were similar, N allocated blocks plus 0.5N holes would place about one-third of the total space in holes. Real results vary with allocation sizes, lifetimes, placement policy, alignment, and coalescing behavior.

The rule is useful as intuition: external fragmentation is not a rare edge case in long-running variable-size allocation. It is not a capacity formula for a production system.

Coalescing cannot merge holes separated by live allocations. Compaction addresses that problem by moving allocated blocks together.

Before compaction:

There are 65 MiB free, but the largest hole is 40 MiB. A 50 MiB request fails.

Move Process C next to Process A:

The total free memory remains 65 MiB, but it now forms one hole. The 50 MiB request can succeed.

Compaction has substantial requirements:

The cost is proportional to the amount of live memory moved, not merely the number of holes removed. On a large system, copying gigabytes can consume memory bandwidth and create a noticeable pause.

Compaction removes external fragmentation only for the space it can rearrange. It does not recover unused bytes inside allocated blocks, so it does not solve internal fragmentation.

Contiguous allocation is easy when an allocation's size never changes. Growth creates another placement problem.

Suppose Process A occupies 20 MiB and needs 8 MiB more:

The total free memory is sufficient, but Process B prevents A from extending its interval. The operating system has only a few choices:

Reserving extra capacity makes growth cheap but creates internal fragmentation while that capacity is unused. Moving allocations avoids permanent slack but costs time and requires relocatability.

This tension appears whenever an allocator promises one continuous block whose eventual size is unknown.

An “out of memory” result does not always mean the same thing.

For request size R, inspect:

If total_free < R, the system lacks raw free capacity.

If total_free >= R but largest_hole < R, external fragmentation prevents the allocation.

If a nominally large-enough hole cannot satisfy the required address alignment, layout constraints prevent placement. Adjusting the start can leave a prefix and suffix whose usable sizes matter.

If the allocation must remain within a fixed partition or other boundary, free memory elsewhere is irrelevant.

These cases may produce the same failure at the caller, but they suggest different remedies. Adding capacity can help a true shortage. Coalescing or compaction can help external fragmentation. Changing block sizes can reduce internal fragmentation. A placement policy can change future hole distribution but cannot manufacture capacity.

Fragmentation and leaks both make memory appear unavailable, but they describe different allocator states.

With a memory leak, an allocation remains marked in use even though the application no longer has a useful way to reach or release it. The allocator does not consider those bytes free.

With internal fragmentation, an allocation is still legitimate, but the block contains unused slack.

With external fragmentation, the allocator knows that bytes are free, but they are split into holes that do not fit a request.

The distinction affects diagnosis:

Compaction cannot fix a leak because leaked blocks are still considered live. Coalescing cannot recover internal slack because it lies inside allocated boundaries.

Modern process address spaces can present a logically contiguous range without requiring the complete range to occupy one physically contiguous block. That flexibility avoids the requirement that every process fit into one large physical hole.

Physical contiguity still matters in constrained environments and for operations that explicitly require it. Examples include:

The same fragmentation vocabulary also applies outside whole-process physical allocation. File extents, storage volumes, memory arenas, and object allocators can all contain allocated blocks separated by holes.

The allocator boundary must remain clear. A range can be contiguous in a process's logical view while the operating system stores it noncontiguously in physical memory. Conversely, a low-level component may specifically require physical contiguity even though application code only sees a logical pointer.

When a contiguous allocation fails or utilization looks poor, identify the allocator's actual block map before drawing conclusions.

Useful quantities include:

allocated - requested reveals internal slack. Comparing largest_hole with total_free reveals the shape of external free space. Looking only at total free memory hides both problems.

Allocation traces are particularly valuable because fragmentation depends on order. The same set of final live allocations can leave different hole layouts depending on which requests arrived, where they were placed, and which blocks were released first.

Contiguous allocation gives each request one uninterrupted physical address interval. Fixed partitioning is simple but wastes unused space inside allocated partitions, producing internal fragmentation. Variable partitioning matches request sizes more closely but creates free holes between live allocations, producing external fragmentation.

Splitting turns one large hole into an allocation and a remainder. Coalescing reunites adjacent free holes. First fit, next fit, best fit, and worst fit choose different holes and therefore create different fragmentation patterns. No placement policy prevents fragmentation for every possible request sequence.

Internal fragmentation is measured inside allocated blocks. External fragmentation is revealed when total free space is sufficient but the largest eligible hole is too small. Compaction can combine external holes by moving live allocations, but it is costly and cannot recover internal slack.

The central diagnostic lesson is:

Capacity answers how many bytes are free; fragmentation answers whether those bytes have a usable shape.