Contiguous Memory Allocation

Contiguous memory allocation is a memory-management scheme in which each process is assigned a single, continuous range of physical memory addresses, defined by a base (starting address) and a limit (size, or ending address). When the CPU generates a logical address, hardware adds the base register's value to translate it, and checks that the result stays below base + limit — otherwise it raises a protection fault. This is the direct hardware mechanism underlying Address Spaces and Relocation: relocation becomes a single addition, and protection becomes a single comparison. Two allocation disciplines exist. In fixed partitioning, physical memory is divided in advance into a fixed number of partitions, each of a predetermined size (equal or unequal), and each partition holds at most one process. In variable partitioning (also called dynamic partitioning), the OS carves out a hole of exactly the size a process requests from whatever free memory is available, so no partition boundaries are predetermined. Fixed partitioning is simpler and enables a very fast allocation decision (an array lookup), but leads to internal fragmentation — wasted space inside a partition when the process is smaller than the partition holding it. Variable partitioning fits processes exactly, but as processes come and go, memory becomes riddled with external fragmentation — small free holes between allocated blocks, none individually large enough to satisfy new requests, even though their sum might be. The placement problem in variable partitioning is: given a list of free holes and a new request of size n, which hole should the OS pick? Three classic policies answer this differently — first-fit (the first hole big enough), best-fit (the smallest hole big enough), and worst-fit (the largest hole available) — and each produces a different fragmentation pattern over time, which is the central engineering question this article resolves.

The OS maintains a data structure describing free memory — typically a linked list or array of `(base, size)` pairs called the free list, kept sorted by address so that adjacent free blocks can be detected and merged. Allocation is the search-and-split operation below; deallocation is the reverse, inserting a freed block back and coalescing it with any physically adjacent free neighbors. ``` // Free list: sorted list of holes, each hole = (base, size) // Allocated list: list of (base, size, owner) for bookkeeping function ALLOCATE(request_size, freelist, strategy): best = null for hole in freelist: // linear scan, O(k) holes if hole.size >= request_size: if strategy == FIRST_FIT: best = hole break // stop at first fit else if strategy == BEST_FIT: if best is null or hole.size < best.size: best = hole // keep smallest sufficient hole else if strategy == WORST_FIT: if best is null or hole.size > best.size: best = hole // keep largest hole if best is null: return ALLOCATION_FAILED // no hole big enough allocated_base = best.base if best.size == request_size: remove best from freelist // exact fit, no leftover else: best.base = best.base + request_size // shrink the hole best.size = best.size - request_size record (allocated_base, request_size) as allocated return allocated_base

function FREE(base, size, freelist): insert (base, size) into freelist, keeping sorted order by base // Coalesce with adjacent free neighbors, O(1) given sorted neighbors if left neighbor of (base,size) is free and left.base + left.size == base: merge left and (base,size) into one hole if right neighbor of (base,size) is free and base + size == right.base: merge (base,size) and right into one hole ``` For fixed partitioning, allocation is simpler: the OS keeps a table of partitions with a busy/free bit, and on request scans (or indexes) for the first free partition of adequate size: ``` function ALLOCATE_FIXED(request_size, partitions): for p in partitions: // usually O(1)-O(k), k = # partitions if p.free and p.size >= request_size: p.free = false return p.base return ALLOCATION_FAILED ``` The figure below shows the state of physical memory under variable partitioning after several allocations and frees, contrasting how first-fit, best-fit, and worst-fit would each place the same next request.

Notice the qualitative difference: first-fit and best-fit both happen to find an exact-size hole here and leave no new fragment, while worst-fit deliberately breaks the largest hole, guaranteeing the leftover remainder (45) is still fairly usable — that is worst-fit's philosophy, even though in general it tends to eliminate large holes quickly, leaving only mid-size ones for future large requests.

Time complexity. All three variable-partition strategies require scanning the free list in the worst case:

• First-fit: O(k) where k is the number of free holes, but averages better in practice because it stops at the first match — empirically close to O(k/2) for uniformly distributed hole sizes.
• Best-fit: O(k) always, since it must examine every hole to find the global minimum sufficient size (unless the free list is kept in a size-sorted balanced tree, reducing search to O(log k) at the cost of O(log k) updates on free/coalesce).
• Worst-fit: O(k) always, for the same reason as best-fit (finding a global maximum), though maintaining a max-heap of holes gives O(log k) if updates are handled carefully.
• Fixed partitioning: O(1) to O(k) depending on whether partitions are indexed by size class or scanned linearly; with k fixed partitions and a bitmap of free/busy, allocation is a bitmap scan, O(k) worst case, O(1) with a free list per size class.

Deallocation is O(1) amortized in all schemes if the free list is a doubly linked list sorted by address (coalescing checks only the immediate left/right neighbor), or O(log k) / O(k) if maintained sorted by size and re-insertion requires repositioning.

Space overhead is O(k) for the free-list metadata itself (a handful of words per hole), independent of process count — cheap compared to the memory being managed.

Correctness argument. The allocator must satisfy two invariants at all times: 1. Disjointness invariant: no two allocated blocks, and no allocated block and free hole, overlap in address range. 2. Completeness invariant: every byte of managed memory is accounted for as either exactly one allocated block or exactly one free hole. `ALLOCATE` preserves both: it only ever shrinks an existing hole from one end (updating `base` and `size` together) or removes it entirely on an exact match, so the union of all holes and allocations never changes and no overlap is introduced — this follows by induction on the number of allocation calls, since the base case (empty allocation history) trivially satisfies both invariants, and each call is a pure split operation on one hole. `FREE` preserves the invariants symmetrically: it reinserts the freed range as a hole (restoring completeness) and then merges with adjacent free neighbors only when their address ranges are exactly touching (`left.base + left.size == base`), which by the disjointness invariant on holes guarantees the merged region is still a single, non-overlapping contiguous hole.

Why fragmentation is provably unavoidable in the long run. Consider variable partitioning under any placement policy. As processes of varying sizes arrive and depart in essentially arbitrary order, the sequence of splits (which shrink holes without ever recombining differently-shaped chunks except via exact address-adjacency) implies that holes can only be merged if they are adjacent survivors — but nothing prevents an allocated block from permanently separating two holes that would otherwise merge into something large enough for a future request. This is a direct consequence of the disjointness invariant: a live process occupying the middle of memory is an immovable wall (without relocation, which contiguous allocation without compaction does not perform), so external fragmentation accumulates as a structural certainty, not merely a bad-luck outcome. Analytically, under randomized request/release patterns, the well-known 50% rule (derived by Knuth) states that if there are n allocated blocks, the expected number of holes is about n/2, so roughly one-third of memory can become unusable fragments even with optimal-looking policies — this is a statistical regularity, not an artifact of a specific algorithm.

Honest tradeoffs.

• First-fit is fast and tends to leave larger holes toward the high-address end of memory, but accumulates small unusable slivers near the front where scanning always begins.
• Best-fit minimizes the size of leftover fragments per allocation, which sounds optimal, but this is precisely why it is bad in aggregate: it manufactures many tiny, likely-useless holes, since "closest fit" leftovers are by construction small.
• Worst-fit avoids tiny leftovers per-call but destroys the few large holes fastest, which can starve future large requests even though small requests are served comfortably.
• Fixed partitioning avoids external fragmentation entirely (partition boundaries never move) but guarantees internal fragmentation whenever process size doesn't match partition size — and if partition sizes are unequal but static, some size classes may be perpetually oversubscribed while others sit idle.

None of these can be "fixed" purely by algorithm choice; the underlying limitation is contiguity itself, which is exactly the motivation for relaxing it in Segmentation and Paging: Basic Concept.

Suppose physical memory (excluding a fixed 30-unit OS region) spans addresses 30–300, giving 270 units of user memory, initially one giant hole. Requests arrive and depart in this order:

We trace first-fit and best-fit side by side. Free list starts as `[(30, 270)]`.

In this particular trace, first-fit and best-fit coincide because at each step there was only one hole large enough to matter — the divergence between algorithms only shows up when multiple holes simultaneously satisfy a request. Let's continue with a divergent step:

Here, too, they coincide — the (180,10) hole is both first and smallest. Now push one more divergent case:

The two algorithms only visibly diverge in placement when the free list simultaneously contains two-or-more holes that both satisfy a request — a scenario easy to construct (e.g., two 200-unit free holes and a 205-unit hole with a request for 190 would make best-fit pick the 200-unit ones while first-fit picks whichever appears first in scan order), and this is a faithful reflection of reality: the algorithms behave identically on many inputs and differ only on specific adversarial-looking configurations, which is exactly why choosing between them in a real allocator requires workload-specific tuning rather than a universal "best" answer. Final state after step 8: memory holds A, C, D, F, G allocated with a single trailing hole of 25 units — external fragmentation is modest here because C sits as an isolated block between B's old space and the tail, but note that no future request larger than 25 can be satisfied without either relocating C or waiting for further frees, even though total free space could exceed the request if it were contiguous — the textbook signature of external fragmentation.

Contiguous allocation was the default memory model in the earliest multiprogrammed operating systems, when memory was scarce, expensive, and treated as one physical resource to be sliced directly — long before virtual memory decoupled logical from physical addresses.

Contiguous allocation concepts persist wherever a resource must be handed out as one unbroken chunk. Embedded and real-time operating systems (many RTOS memory pools, small IoT kernels) still use fixed or variable partition schemes directly, because their memory footprints are small and predictable enough that fragmentation is manageable and the simplicity/speed of base-limit translation is worth it. General-purpose kernel memory allocators — the buddy system and slab allocators in Linux, for instance — descend conceptually from these placement ideas, managing physically contiguous pages for DMA-capable devices and kernel objects that cannot tolerate scattered pages. GPU memory managers and some database buffer pools also allocate contiguous regions for large sequential buffers where address-translation overhead must stay minimal. Understanding first-fit, best-fit, and worst-fit — and precisely why each produces internal versus external fragmentation — is the essential stepping stone to why virtual memory systems introduced Segmentation (contiguous logical segments mapped flexibly onto physical memory) and ultimately Paging: Basic Concept (fixed-size frames that eliminate external fragmentation by design, at the cost of new problems like internal fragmentation within a page and translation overhead).

Ask the tutor: How does the buddy system allocator resolve some of these fragmentation trade-offs while still allocating physically contiguous memory?