Non-Contiguous Memory Allocation
In the previous lesson, we saw that requiring a process to sit in one massive, unbroken block of memory (Contiguous Allocation) leads to a major problem: External Fragmentation.
Over time, the RAM gets chopped up into dozens of tiny, unusable gaps. A process might need 50 MB, and you might have 100 MB of total free space, but because that space is scattered in 5 MB chunks, the process cannot run.
Operating systems solved this by completely changing the rules. What if a process did not need to be in one continuous block? What if we could break the process apart and scatter it wherever we found free space?
The Core Concept
Non-Contiguous Memory Allocation allows a program to be divided into different blocks, which are then loaded into physical memory at different locations depending on what space is currently available.
Non-Contiguous Allocation: The process is split into pieces and scattered across available free holes in RAM.
By doing this, External Fragmentation is completely eliminated. As long as the TOTAL sum of free holes in the system is greater than or equal to the size of the process, the OS can load the process and run it.
The Tradeoff: Translation Overhead
This sounds like a perfect solution, but it introduces a massive new challenge: keeping track of everything.
In a contiguous system, the hardware only needs a single Base Register. If the OS knows the process starts at address 1000, and the CPU asks for instruction #50, the hardware simply calculates 1000 + 50 = 1050.
In a non-contiguous system, instruction #50 might be in RAM chip A, while instruction #51 might be miles away in RAM chip B. The OS now has to maintain a complex map (a data structure) for every single process, detailing exactly where every little piece went. Looking up this map slows things down.
How We Break Things Up
There are two primary ways an OS decides how to chop a process up:
1. Paging (Fixed-Size Chunks)
Paging divides the process's logical memory into strict, identical, fixed-size blocks called Pages. It divides the physical RAM into identical fixed-size blocks called Frames.
Paging: Every block is the exact same size, meaning ANY Page fits into ANY Frame perfectly.
Because every piece is the same size, the OS does not have to play Tetris. If a page needs to go into memory, any free frame will do. The OS maintains a "Page Table" to track which page went into which frame.
2. Segmentation (Variable-Size Chunks)
Segmentation divides the process based on logic rather than strict size. A program naturally has a main function, an area for global variables, and an area for external libraries. Segmentation chops the program along these logical lines.
This means the chunks (Segments) are all different sizes. The OS scatters these segments into free holes in RAM and maintains a "Segment Map Table" to track the starting address and limit of each piece.
| Technique | How it divides memory | Primary Advantage |
|---|---|---|
| Paging | Identical, fixed-size Pages/Frames. | Completely solves External Fragmentation. Allocation is trivial. |
| Segmentation | Variable-sized, logical segments. | Makes sharing logical modules (like a standard math library) between processes very easy and intuitive. |
Advantages and Disadvantages
| Advantages | Disadvantages |
|---|---|
| Eliminates External Fragmentation entirely (especially in Paging). | Requires complex translation hardware and OS data structures. |
| Maximizes overall memory utilization by filling scattered holes. | High translation overhead (page table lookups slow down execution). |
| Easily supports dynamic memory growth and Virtual Memory. | Still suffers from Internal Fragmentation (if the final page is partially full). |
Summary
Non-contiguous memory allocation is the backbone of all modern operating systems. By allowing processes to be broken apart and scattered, it maximizes the usage of available RAM and effectively kills external fragmentation.
The cost of this efficiency is the overhead of maintaining Translation Tables (Page Tables or Segment Tables) and the extra CPU cycles required to map logical addresses to scattered physical addresses on the fly.
Sort the Concepts
Classify the following characteristics as belonging to either Contiguous or Non-Contiguous Memory Allocation.