Contiguous Allocation

01 Introduction

Lessons 8.1 through 8.3 established the physical and conceptual foundations of memory management: the memory hierarchy, address binding, and the mechanisms for loading code on demand. This lesson turns to the first concrete allocation policy. The system has a fixed amount of physical memory, and several processes want to use it. How should the operating system divide the memory among them?

The simplest answer, and the one that dominated early time-sharing systems, is contiguous allocation: each process is given a single region of physical memory large enough to hold its entire address space, and the region is contiguous — the process's logical addresses 0 through size−1 map to consecutive physical addresses base through base+size−1. This is exactly the base-and-limit scheme from Lesson 8.2, and it is the natural way to use the memory-management unit introduced there. Each process has its own base and limit, the MMU translates logical to physical addresses by adding the base, and the limit check enforces protection.

The interesting problem is not the translation but the allocation. Suppose the operating system has been running for a while, and memory is carved into a sequence of regions: some allocated to processes, some free. A new process arrives and needs N bytes. Which free region should the operating system assign? The obvious answer — "any region large enough" — is not a complete policy, because in general there are several regions large enough, and the choice affects how well the remaining memory can serve future requests. This is the placement problem, and the three classical algorithms that solve it — first-fit, best-fit, and worst-fit — are the subject of this lesson.

The lesson also introduces the two structural problems that arise in any contiguous allocation scheme. Fragmentation is the accumulation of small, unusable free regions that no future request can fit, either because they are between allocated blocks (external fragmentation) or because they are inside an allocated block that is larger than the process needed (internal fragmentation). Compaction is the technique of moving the allocated blocks together to consolidate the free regions, which is expensive because it requires copying processes in memory. Fragmentation is the subject of Lesson 8.5; this lesson introduces it and illustrates it in the worked example.

The lesson closes with the relationship between contiguous allocation and the mechanisms of the rest of the unit. Contiguous allocation is the simplest member of the family of allocation schemes, and it has the most severe limitations. The limitations are what motivate the segmentation of Lesson 8.6 and the paging of Unit 9. Understanding the simple scheme thoroughly is what makes the design of the more elaborate ones legible.

02 Learning objectives

This lesson contributes to U8.3 and U8.4, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

• Operating System Concepts — Chapter 9, Section 9.2, Contiguous Memory Allocation. The standard treatment of the three placement algorithms and the free-list data structure.
• Silberschatz et al. — Chapter 9, Section 9.2. Read the worked example carefully; the sequence of requests and the placement of each process under the three algorithms is the canonical illustration and appears in almost every treatment of the topic. Work through the numbers yourself before reading the solution.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.2, A Memory Abstraction: Address Spaces. The section on memory allocation algorithms and the discussion of first-fit, next-fit, best-fit, and worst-fit.
• OSTEP — Chapter 17, Free Space Management. The clearest available treatment of free-space management from the perspective of a memory allocator. OSTEP's treatment of the free list, splitting, coalescing, and the trade-offs between the placement policies is the basis for the worked example in this lesson.
• Knuth, D. E. — The Art of Computer Programming, Volume 1: Fundamental Algorithms, Section 2.5, Dynamic Storage Allocation. The classical treatment of the free-list data structures and the placement policies, written from the perspective of a storage allocator for a language runtime.
• Wilson, P. R., Johnstone, M. S., Neely, M., & Boles, D. — Dynamic Storage Allocation: A Survey and Critical Review. Proceedings of the International Workshop on Memory Management, 1995. A comprehensive survey of the placement policies and their empirical behaviour on real workloads. Read sections 1–3 for the conceptual framework.
• Linux man pages: man 3 malloc, man 3 free, man 2 brk, man 2 sbrk, man 2 mmap, man 5 proc (the /proc/<pid>/maps and /proc/<pid>/statm interfaces).

04 Core content

4.1 The contiguous allocation model

In the contiguous allocation model, each process occupies a single contiguous region of physical memory. The region's size is the size of the process's address space — the sum of its code, data, heap, and stack. The region's starting address is chosen by the operating system when the process is created, and it does not change for the lifetime of the process.

The operating system maintains two pieces of information:

• For each allocated region, the process that owns it, the region's start address, and its size. This is enough to set the base and limit registers when the process runs, and to identify the region when the process terminates.
• For each free region, the region's start address and its size. These free regions are collectively called the free list or hole list. The free list is a data structure — historically a linked list, in modern systems usually a tree or a bitmap — that records the available memory.

When a process terminates, its region is returned to the free list. If its neighbours are also free, the three regions are merged into a single larger free region, a process called coalescing. Coalescing is essential: without it, the free list would accumulate many small regions that individually are too small for any future request but together would be sufficient.

The translation of logical to physical addresses is performed by the base-and-limit mechanism of Lesson 8.2: the base register holds the region's start address, and the limit register holds its size. The MMU adds the base to each logical address and checks the result against the limit. Protection is therefore automatic: a process cannot reach beyond its own region, because the limit check rejects any address at or beyond the boundary.

4.2 Fixed partitioning

The simplest form of contiguous allocation is fixed partitioning. The operating system divides memory into a fixed number of partitions at startup, and each partition is permanently assigned a fixed size and a fixed position. When a process is loaded, it is assigned to one of the partitions that is large enough to hold it.

Fixed partitioning comes in two flavours.

• Equal-size partitions. All partitions are the same size. This is simple to implement, because any free partition is interchangeable with any other. It has two serious problems. First, a process larger than the partition size cannot be run at all, no matter how much memory is available elsewhere in the system. Second, a process smaller than the partition size wastes the difference: if the partition is 1 MB and the process needs 100 KB, 900 KB are wasted. This waste is called internal fragmentation.
• Unequal-size partitions. The partitions are of different sizes, chosen to match the expected distribution of process sizes. A small process can use a small partition, a large process a large one, and the waste is reduced. The problem is that the assignment of processes to partitions is now a bin-packing problem, which is NP-hard, and the operating system must use a heuristic. A process that fits none of the available partitions cannot be run, and a process that fits only one may wait while that partition is occupied by a smaller process that fits elsewhere.

Fixed partitioning was used in the earliest multiprogrammed systems, where the number and size of the partitions were chosen at system configuration time based on the expected workload. It is essentially extinct in modern general-purpose systems, because it cannot adapt to the actual mix of processes: if the workload changes, the partition sizes are wrong, and the system either wastes memory or cannot run the processes. Its historical importance is that it introduced the terminology — partitions, internal and external fragmentation — that later schemes inherited.

4.3 Variable partitioning

The alternative is variable partitioning. The operating system does not divide memory into partitions at startup. Instead, it allocates each process exactly as much memory as it needs, taking the space from the free list. A process of 200 KB is given a 200 KB region; a process of 1 MB is given a 1 MB region. There is no fixed upper limit on the size of a process, and there is no internal waste within a region.

Variable partitioning is the model used by modern contiguous allocation systems, and it is what the rest of this lesson assumes. Its advantages are flexibility — the partition sizes track the process sizes automatically — and the absence of internal fragmentation. Its disadvantage is that the free list fragments: as processes are allocated and freed, the free memory accumulates in small regions scattered between the allocated regions. This is external fragmentation, and it is the principal problem of variable partitioning.

4.4 The placement problem

When a process requests N bytes of memory, the operating system searches the free list for a region of at least N bytes. In general, several such regions exist, and the choice of which to use is the placement problem. The three classical answers are first-fit, best-fit, and worst-fit.

First-fit

Allocate the first region in the free list that is large enough. The search stops as soon as a suitable region is found. First-fit is the simplest algorithm, and it is also the fastest, because it does not examine the entire list. Its name is slightly misleading: the region chosen is the first one that fits, not the first one that is exactly the right size. If the first region happens to be exactly N bytes, it is used with no waste; if it is larger, it is split and the remainder goes back on the free list.

Best-fit

Allocate the smallest region in the free list that is large enough. The search must examine the entire list, because the best fit may be anywhere. The intuition is that best-fit leaves the smallest remainder, and therefore preserves the larger regions for future requests that need them. The intuition is partly right and partly wrong: best-fit does minimise the immediate waste, but the small remainders it produces are often too small to be useful, and they accumulate as unusable fragments. This is the fragmentation problem, and it is discussed in Lesson 8.5.

Worst-fit

Allocate the largest region in the free list. The search must examine the entire list, because the largest region may be anywhere. The intuition is the opposite of best-fit: by taking the largest region, the algorithm leaves the largest possible remainder, which is most likely to be useful for a future request. In practice, worst-fit performs poorly, because it consumes the large regions that future large requests will need, and it leaves remainders that are themselves large and quickly fragmented. The algorithm is instructive precisely because its intuition is plausible but its behaviour is not what the intuition suggests.

All three algorithms share a common structure. They search the free list for a region of sufficient size, allocate N bytes from it, and split the region if it is larger than needed. The difference is only in which region each one chooses when several qualify.

4.5 Splitting and coalescing

The free list is a dynamic data structure, and it must be updated on every allocation and every free. Two operations are essential.

Splitting

When a region of size S is chosen for a request of N bytes, and S > N, the region is split: N bytes are allocated to the process, and the remaining S − N bytes are returned to the free list as a new region. If S == N, the entire region is allocated and no remainder is produced. Some allocators also require a minimum region size — typically enough to hold the metadata for a free region — and if the remainder would be smaller than this minimum, the entire region is allocated to the process and the small remainder is wasted. This is one source of internal fragmentation.

Coalescing

When a process terminates and its region is returned to the free list, the operating system checks whether the region's immediate neighbours in physical memory are also free. If so, the regions are merged into a single larger region, and the list is updated accordingly. Coalescing is what prevents the free list from accumulating into an unusable collection of small fragments. Without coalescing, a system that repeatedly allocated and freed would end up with the free memory scattered in pieces too small for any future request — even though the total free memory would be large.

Coalescing is easy in a contiguous allocation scheme, because the free list can be kept sorted by start address, and a region's neighbours can be identified by their positions in the sorted list. In more sophisticated schemes — with non-contiguous regions, or with the allocator managing a heap with its own metadata — the coalescing operation is more involved.

4.6 Comparing the three algorithms

The three algorithms differ in their search time, in their memory utilisation, and in the size of the fragments they leave.

The empirical result is the most important and the least intuitive. First-fit is generally the best of the three algorithms on real workloads, despite being the simplest and despite not scanning the entire list. The reason is that first-fit tends to allocate from the head of the free list, so the free regions near the head are used and split, while the regions further along remain large and intact. The result is a distribution of region sizes that is skewed: many small regions at the front (useful for small requests) and a few large regions at the back (useful for large requests). This distribution happens to match the distribution of request sizes in most workloads, where many small requests and a few large requests are the norm.

Best-fit's behaviour is the opposite: by always choosing the smallest sufficient region, it produces small remainders, and the free list accumulates many tiny fragments that cannot serve any future request. The algorithm's name suggests that it produces the best fit, but the fit is best for the current request, not for the system as a whole. Worst-fit's behaviour is straightforwardly poor: by always consuming the largest region, it destroys the large regions that future large requests need, and the algorithm rapidly fragments the memory into pieces too small for anything.

The lesson from this comparison is that the relationship between an algorithm's local decision rule and its global behaviour is not obvious. Best-fit's rule minimises waste at each step, but produces a global outcome that is worse than first-fit's. Worst-fit's rule is the opposite of best-fit's, but produces a global outcome that is worse than both. First-fit's rule is the simplest, and it produces the best outcome. This is a recurring theme in operating-systems design: the intuition of a local rule is often a poor guide to its global behaviour, and empirical measurement is necessary to know which policy is actually best.

4.7 Compaction

A second technique for dealing with fragmentation is compaction. The operating system moves all the allocated regions to one end of memory, consolidating the free regions into a single large region. After compaction, the free memory is a single contiguous block, and any future request can be satisfied from it, regardless of its size.

Compaction is expensive. It requires the operating system to copy each process's entire address space to a new location, and to update the process's base register to reflect its new location. If the process is running, it must be suspended during the copy. For a system with many processes and large address spaces, the total cost of a compaction can be milliseconds — significant for an interactive system, and prohibitive if compaction happens frequently.

Compaction is only possible if addresses are bound at execution time. In a system with compile-time or load-time binding, the process's internal addresses are absolute, and moving the process would require adjusting every reference inside it, which is impractical at runtime. With execution-time binding, the process's internal addresses are logical, and the translation is performed by the MMU using the base register, so moving the process requires only updating the base register. This is a significant advantage of execution-time binding, and it is the reason compaction is feasible at all in a modern system.

In practice, compaction is rarely used. It is too expensive for an interactive system, and the memory savings are usually available through other means. Paging, the subject of Unit 9, eliminates external fragmentation entirely by allowing a process's address space to be split across non-contiguous physical pages. Once paging is available, compaction is unnecessary.

4.8 Protection with base and limit

The protection mechanism that accompanies contiguous allocation is the base-and-limit scheme from Lesson 8.2. Each process has its own base and limit, and the MMU checks every access against the limit before performing the translation. Because each process's region is contiguous and disjoint from every other process's region, this mechanism is sufficient: a process can only reach its own memory, and any attempt to reach outside its region causes a fault.

The base and limit registers are part of the process's state, saved and restored on every context switch. When the scheduler switches from one process to another, it writes the new process's base and limit into the MMU before resuming execution. If this write were omitted, the new process would run with the old process's translation, and its accesses would reach the old process's memory — a catastrophic protection failure. The update of the base and limit registers is therefore a mandatory and non-optional part of the context switch.

The protection mechanism has one significant limitation. It enforces that a process can reach only its own region, but it cannot enforce finer-grained protection within the region. In particular, it cannot distinguish the process's code from its data, so a process that accidentally writes to its own code section — corrupting its own instructions — is not caught by the protection mechanism. Modern systems address this by using segmentation (Lesson 8.6) or paging (Unit 9), which allow each region to have its own permissions.

4.9 Common misconceptions

05 Worked example

The following example traces the three placement algorithms on the canonical workload, showing where each process is placed and what the free list looks like after each allocation.

# Python sketch
def first_fit(holes, request):
    for i, (start, size) in enumerate(holes):
        if size >= request:
            return i
    return None

def best_fit(holes, request):
    best = None
    for i, (start, size) in enumerate(holes):
        if size >= request:
            if best is None or size < holes[best][1]:
                best = i
    return best

def worst_fit(holes, request):
    worst = None
    for i, (start, size) in enumerate(holes):
        if size >= request:
            if worst is None or size > holes[worst][1]:
                worst = i
    return worst

def allocate(holes, request, policy):
    i = policy(holes, request)
    if i is None:
        return False, holes
    start, size = holes[i]
    if size == request:
        holes.pop(i)
    else:
        holes[i] = (start + request, size - request)
    return True, holes

# Test with the canonical workload
for name, policy in [("first-fit", first_fit),
                     ("best-fit", best_fit),
                     ("worst-fit", worst_fit)]:
    holes = [(0, 600), (600, 500), (1100, 200),
             (1300, 300), (1600, 600)]
    print(f"--- {name} ---")
    for pid, req in enumerate([212, 417, 112, 426]):
        ok, holes = allocate(holes, req, policy)
        print(f"P{pid+1} = {req} KB: {'allocated' if ok else 'FAILED'}")
        print(f"  holes: {holes}")

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• Contiguous allocation gives each process a single region of physical memory. The region's base and limit are set in the MMU, and the translation is performed by the base-and-limit scheme from Lesson 8.2.
• The operating system maintains a free list that records each free region's start address and size. When a process requests memory, the free list is searched for a region large enough.
• Fixed partitioning divides memory into a fixed set of partitions at startup. It is simple, but it cannot adapt to the actual sizes of the processes and it wastes memory through internal fragmentation. It is essentially extinct in modern general-purpose systems.
• Variable partitioning allocates each process exactly as much memory as it needs, taking the space from the free list. It is the model used by modern contiguous allocation systems. Its disadvantage is external fragmentation: the free memory accumulates in small regions scattered between the allocated regions.
• The three classical placement algorithms are first-fit (allocate from the first region large enough), best-fit (allocate from the smallest region large enough), and worst-fit (allocate from the largest region).
• First-fit is the simplest and the fastest. Best-fit minimises the immediate waste but produces small remainders that accumulate as fragments. Worst-fit leaves the largest remainders but destroys the large regions that future large requests need.
• The empirical result, on real workloads, is that first-fit is generally the best of the three. Its characteristic distribution — many small holes at the front of the list, a few large holes at the back — matches the distribution of request sizes in most workloads.
• Splitting is the operation of dividing a hole when a request is smaller than the hole. Coalescing is the operation of merging a freed region with its adjacent free neighbours. Coalescing is essential to prevent the free list from accumulating into an unusable collection of small fragments.
• Compaction moves all allocated regions to one end of memory, consolidating the free memory into a single large region. It requires execution-time binding, and it is rarely used because it is expensive and paging provides a better solution.
• Contiguous allocation is the foundation of every other allocation scheme. The vocabulary it introduces — holes, free lists, splitting, coalescing, external and internal fragmentation, the placement problem — is used throughout the rest of the unit and in every discussion of memory allocation.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Section 9.2.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 17, Free Space Management. Available online at ostep.org.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.2.
• Knuth, D. E. The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed., Section 2.5, Dynamic Storage Allocation. Addison-Wesley, 1997.
• Wilson, P. R., Johnstone, M. S., Neely, M., & Boles, D. Dynamic Storage Allocation: A Survey and Critical Review. Proceedings of the International Workshop on Memory Management, 1995.
• Peterson, J. L., & Norman, T. A. Buddy Systems. Communications of the ACM, 1977. The original paper on the buddy system, which is presented in Lesson 8.5.
• Bonwick, J. The Slab Allocator: An Object-Caching Kernel Memory Allocator. USENIX Summer Conference, 1994. The original paper on the slab allocator.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The kernel's own allocators: the buddy system and the slab allocator.
• Linux man-pages: man 3 malloc, man 3 free, man 3 malloc_usable_size, man 2 brk, man 2 mmap, man 5 proc.