Contiguous Memory Allocation
In the early days of operating systems, memory management was straightforward: when a process needed to run, the OS found a single, unbroken block of memory large enough to hold it. This approach is known as Contiguous Memory Allocation.
Under this model, every process is contained in a single contiguous section of memory. If a process needs 50 MB of RAM, the OS must find 50 MB of consecutive, unbroken space. It cannot give the process two separate 25 MB chunks.
The Layout of Memory
Physical memory is generally divided into two main regions:
- Operating System Space: Usually placed in low memory, accompanied by the interrupt vector.
- User Space: The remaining memory, positioned in high memory, where user processes are loaded.
A typical RAM layout showing the OS reserved space and Contiguous User Processes.
Hardware Protection
When multiple processes share memory, the OS must ensure they do not read from or write to each other's memory space. In a contiguous allocation system, this is handled elegantly by two hardware registers:
- Base (Relocation) Register: Contains the physical starting address of the process.
- Limit Register: Contains the total length (size) of the logical address space.
Every time the CPU generates an address, the hardware checks it. If the logical address is greater than or equal to the Limit Register, it throws a "trap" (fatal error). If it is valid, the Base Register is added to it to find the physical address. This guarantees a process can NEVER access memory outside its contiguous block.
Fixed Partitioning
The simplest way to allocate contiguous memory is to divide the RAM into a fixed number of partitions at boot time. Each partition can hold exactly one process.
Fixed Partitioning leads to Internal Fragmentation: space wasted inside an allocated partition.
The major flaw here is Internal Fragmentation. If a partition is 10 MB, and a process only needs 3 MB, the OS puts the 3 MB process in the partition. The remaining 7 MB of space inside that partition sits completely empty and cannot be used by any other process until the current one finishes.
Variable (Dynamic) Partitioning
To solve the internal fragmentation problem, modern contiguous systems use variable partitioning. The OS keeps a table indicating which parts of memory are available (free holes) and which are occupied.
When a process arrives, the OS searches for a hole large enough for it and allocates EXACTLY the amount of memory requested. No space is wasted inside the allocation block.
Variable Partitioning leads to External Fragmentation: total free space is sufficient, but scattered.
While this eliminates Internal Fragmentation, it creates External Fragmentation. As processes load and exit at different times, holes of various sizes are left behind. Eventually, the OS might have 50 MB of total free space, but it is scattered across 10 different 5 MB holes. A process needing 20 MB will be denied, even though enough total space exists.
Dynamic Storage Allocation Algorithms
When a process needs memory, and there are multiple free holes large enough to fit it, how does the OS choose which hole to use? There are three standard strategies:
| Algorithm | How It Works | Pros & Cons |
|---|---|---|
| First-Fit | Scans memory from the beginning and allocates the first hole that is big enough. | Fastest method, but tends to heavily fragment the front of the memory space. |
| Best-Fit | Scans ALL holes and allocates the smallest hole that is big enough. | Leaves the smallest possible leftover fragment, but is slower (requires searching the whole list) and creates tiny, useless leftover holes. |
| Worst-Fit | Scans ALL holes and allocates the largest available hole. | Leaves the largest possible leftover fragment (which might be big enough for another process), but quickly uses up the largest blocks of memory. |
Advantages and Disadvantages
| Advantages | Disadvantages |
|---|---|
| Simple to implement and manage. | Suffers heavily from Internal or External Fragmentation. |
| Excellent execution speed (hardware translation requires only adding the base register). | Difficult to dynamically grow the size of a process once allocated. |
| No complex translation tables needed, saving OS memory overhead. | Memory utilization is generally poor compared to non-contiguous methods. |
Summary
Contiguous memory allocation is conceptually simple and very fast to execute in hardware. However, because it demands unbroken consecutive blocks of memory, it suffers heavily from fragmentation.
To combat this, the OS can run a process called "compaction" to shuffle memory and merge all holes into one large block, but this is incredibly expensive in terms of CPU time. These limitations eventually pushed OS design toward non-contiguous solutions like Paging.