Contiguous Allocation & Fragmentation
Scenario
Imagine moving into a new neighborhood where you want to buy 3 adjacent houses for your extended family. There are 10 empty houses in the town, but they are scattered individually. Even though there is enough total space, you can't move in because the space isn't continuous.
Mental model
Memory must be allocated in single, unbroken blocks, which inevitably leaves small, unusable gaps over time.
Contiguous memory allocation forces a process to occupy a single, continuous block of physical memory. As processes load and exit, they leave behind empty spaces (holes). Over time, these holes become scattered. Fragmentation is the phenomenon where total free memory is sufficient, but no single contiguous block is large enough to satisfy a new request.
Explanation
In early operating systems, memory management was straightforward: when a program wanted to run, the OS found a single, unbroken chunk of physical memory large enough to hold the entire program. This is known as Contiguous Memory Allocation. The OS keeps track of which parts of memory are occupied and which are free (often called 'holes').
When a new process arrives, the OS must choose which hole to put it in. Common strategies include 'First Fit' (grabbing the first hole that is big enough), 'Best Fit' (finding the smallest hole that is large enough, leaving a tiny remnant), and 'Worst Fit' (taking the largest available hole, leaving a sizable chunk for future use). Regardless of the strategy used, contiguous allocation inevitably leads to a massive problem: Fragmentation.
There are two distinct types of fragmentation. The first is External Fragmentation. This happens when processes are continuously loaded and removed from memory. Over time, the free memory gets chopped into tiny, isolated pieces scattered across RAM. Eventually, a new process might ask for 10MB of RAM. The OS might have 50MB of total free space, but because it is broken into 1MB chunks, the contiguous allocation fails. The memory exists, but its fractured arrangement makes it useless.
To fix external fragmentation, the OS can perform 'Compaction'. This involves physically pausing processes, copying their data to clump them all together at one end of the memory, and merging the free space into a single large block at the other end. However, shifting gigabytes of memory is an incredibly slow and computationally expensive operation, stalling the entire system.
The second type is Internal Fragmentation. This occurs when memory is divided into fixed-size blocks (like partitions). If the OS allocates a 4MB partition to a process that only needs 3MB, that remaining 1MB inside the partition is entirely wasted. It belongs to the process, but the process isn't using it, and the OS can't give it to anyone else.
Key points
- First Fit vs Best Fit: First Fit is fast but creates unpredictable gaps. Best Fit saves large blocks but creates tiny, unusable slivers of external fragmentation.
- External Fragmentation: Total free memory is enough, but it is split into non-contiguous blocks that are too small to be used individually.
- Internal Fragmentation: Memory allocated to a process is slightly larger than requested, wasting space 'inside' the allocated block.
- Compaction: The expensive process of shuffling memory contents to merge all free space into one large contiguous block.
Common mistakes
- Confusing internal and external fragmentation: External fragmentation happens OUTSIDE the allocated blocks (between processes). Internal fragmentation happens INSIDE the allocated block (leftover space given to a process).
- Thinking compaction is a routine, cheap operation: Compaction requires halting execution, recalculating addresses, and physically copying data. It is a last-resort performance killer.
Glossary
- Contiguous Memory Allocation
- An older memory management technique where an entire program must be loaded into a single, continuous block of available RAM.
- First Fit
- A strategy where the operating system quickly scans memory and places a new program in the very first available empty space that is large enough to hold it.
- holes
- The scattered empty gaps or blocks of free memory that are left behind in RAM when programs finish running and release their space.
Recall questions
- What is the primary drawback of contiguous memory allocation?
- Which allocation strategy searches the entire list of free holes to find the smallest one that fits?
- How does memory compaction solve external fragmentation?
Questions & answers
A system has free memory blocks of 10KB, 20KB, and 30KB. A process requests 25KB. Which block is chosen using the First Fit strategy, assuming blocks are searched in order?
The 30KB block.
Approach: First Fit stops at the first block that is >= 25KB. 10 and 20 are too small. 30 is the first one that fits.
An OS allocates memory in fixed 4KB blocks. A process requires 9KB of memory. How much internal fragmentation occurs?
3KB.
Approach: The process needs 9KB. It will be allocated three 4KB blocks (12KB total). 12KB - 9KB = 3KB of wasted space inside the allocation.
Continue learning
Next: Paging & Page Tables