Contiguous Memory Allocation

Introduction

Before paging and segmentation existed, operating systems used a simpler approach: give each process a single contiguous block of memory. Just like assigning a hotel guest a range of consecutive room numbers, contiguous allocation assigns each process a continuous range of memory addresses with no gaps.

This is the simplest form of memory management — easy to understand and implement. However, it suffers from significant fragmentation problems that motivated the development of paging and segmentation. Understanding contiguous allocation is important both historically and because it illustrates fundamental allocation challenges that apply to many areas of computing.

Fixed Partitioning

The simplest scheme: divide memory into fixed-size partitions at boot time. Each partition holds exactly one process.

Problems: Internal fragmentation (space wasted within partitions), limited number of processes (one per partition), process size limited to partition size.

Variable Partitioning

A more flexible approach: partitions are created dynamically to match process sizes. No internal fragmentation since each partition exactly fits its process.

But when processes terminate and new ones arrive, memory becomes a patchwork of used and free blocks — external fragmentation.

Allocation Strategies

When a new process needs N bytes and there are multiple free holes, which hole should we use?

First Fit

Allocate from the FIRST hole that is big enough. Start searching from the beginning of memory.

Advantage: Fast — stops as soon as a suitable hole is found Disadvantage: Tends to fragment the beginning of memory

Best Fit

Allocate from the SMALLEST hole that is big enough. Must search the entire list.

Advantage: Leaves the smallest leftover fragment (saves large holes for large processes) Disadvantage: Creates many tiny useless fragments, slower (must scan all holes)

Worst Fit

Allocate from the LARGEST hole. The idea is that the leftover fragment will be large enough to be useful.

Advantage: Leftover fragments are larger and potentially usable Disadvantage: Quickly depletes the largest available blocks, generally performs worst

Example Comparison

External Fragmentation Problem

Over time, as processes are loaded and terminated, memory becomes fragmented into many small holes that individually are too small to satisfy requests, even though total free memory is sufficient.

Compaction

The solution to external fragmentation: move all processes together to create one large free block.

Problem: Compaction is expensive — must copy all process memory and update all addresses. Only possible if address binding is done at runtime (relocation registers).

50-Percent Rule

Empirical observation by Knuth: given N allocated blocks, approximately N/2 blocks will be free (holes). Approximately 1/3 of memory is wasted due to fragmentation. This is called the "50-percent rule" and demonstrates that external fragmentation is inherently unavoidable in variable-partition schemes.

Real-World Analogy

Contiguous allocation is like parking cars in a parking lot without marked spaces. Each car takes exactly the space it needs (no internal fragmentation). But when some cars leave, you get gaps between remaining cars that might be too small for a new SUV, even though total empty space is sufficient. Compaction is like asking everyone to drive forward and close the gaps — effective but disruptive.

Key Takeaways

• Contiguous allocation gives each process a single continuous block of memory
• Fixed partitions cause internal fragmentation; variable partitions cause external fragmentation
• First-fit is fast but fragments the front of memory; best-fit creates tiny useless holes
• External fragmentation means total free memory is sufficient but no single hole is large enough
• Compaction consolidates free space but is expensive and requires runtime address binding
• These fragmentation problems motivated the development of paging (fixed-size allocation)
• The 50-percent rule shows that about 1/3 of memory is typically wasted to fragmentation