Contiguous Memory Allocation

The allocation problem

When a process or segment needs memory, the OS must find a contiguous region of free physical memory large enough to hold it. This is the contiguous allocation problem — the prerequisite for base/limit or pure segmentation schemes.

Allocation strategies

Given a list of free memory holes, which hole should be allocated?

First-fit

Allocate the first hole that is large enough. Search starts from the beginning of the free list.

• Fast: stops searching as soon as a suitable hole is found.
• Wastes the front: small unusable fragments accumulate near the beginning of the list, but the end remains relatively clear.

Best-fit

Allocate the smallest hole that is large enough (the one that minimises leftover space). Must search the entire list (unless the list is sorted by size).

• Minimises wasted space within the chosen hole, but creates the smallest possible leftover fragments — which are often too small to be useful.
• Slower than first-fit (full search unless sorted).

Worst-fit

Allocate the largest hole. The leftover fragment should still be usable for future allocations.

• Counter-intuitive advantage: largest holes produce leftovers that are still large enough to be useful.
• Poor performance in practice: the largest hole is consumed, and subsequent large allocations may fail even though smaller holes remain.

Next-fit

Variant of first-fit: start searching from where the last allocation finished, not from the beginning. Distributes fragmentation more evenly, avoiding the “small holes at the front” problem of first-fit.

Buddy allocation

The buddy system is a compromise between contiguous allocation and paging. Memory is divided into blocks that are powers of two. When a request for $n$ bytes arrives, the allocator rounds up to the nearest power of 2 and finds a block of that size. If none is available, it splits a larger block into two “buddies” and recursively allocates from one of them.

When a block is freed, the allocator checks whether its buddy is also free; if so, the two are merged (coalesced) back into a larger block. This forms a binary tree structure.

Buddy allocation has internal fragmentation (rounding up to a power of 2) and limited external fragmentation (smaller than pure variable-size allocation, but not zero as in paging). Linux uses the buddy allocator to manage the free-frame pool.

The limits of contiguous allocation

Contiguous allocation requires that the entire process (or segment) fit into a single block of physical memory. This imposes a hard limit: a process larger than the largest free hole cannot run, even if the total free memory exceeds its size.

Paging solves this: a process’s address space is divided into fixed-size pages, each of which can be placed in any free frame. No contiguous allocation is needed at the physical level. A 100-page process can run even if the 100 free frames are scattered across physical memory.

Summary

• First-fit, best-fit, worst-fit, and next-fit trade off search time against fragmentation quality.
• The buddy system uses power-of-two splitting and coalescing for efficient heap management.
• Contiguous allocation imposes a hard “biggest hole” constraint; paging eliminates it.