What is Contiguous Memory Allocation?
Learn contiguous memory allocation, first-fit vs best-fit vs worst-fit, and why it leads to external fragmentation.
Expected Interview Answer
Contiguous memory allocation is a memory management scheme where each process is assigned a single unbroken block of physical memory addresses, with the OS tracking free and used regions and choosing among strategies like first-fit, best-fit, or worst-fit to place each new process.
In contiguous allocation, physical memory is divided into a set of variable-sized partitions, and when a process needs memory, the OS searches its list of free holes for one large enough to hold it: first-fit picks the first hole that fits and is fast but can leave awkward small leftovers near the start of memory, best-fit picks the smallest hole that still fits to minimize wasted space per allocation but can leave many tiny unusable slivers, and worst-fit picks the largest hole to keep leftover fragments as large as possible, though it tends to perform worst overall in practice. Because process sizes and lifetimes vary, memory freed by exiting processes creates holes of different sizes scattered between still-allocated processes, so contiguous allocation is inherently prone to external fragmentation over time, and can require compaction to consolidate free space. It also demands that a process’s entire memory footprint fit into one physical block at once, which limits multiprogramming to whatever fits in physical RAM and offers no isolation benefit beyond simple base/limit register bounds checking. This is why modern operating systems replaced pure contiguous allocation with paging, which allocates in fixed-size, non-contiguous frames and eliminates external fragmentation entirely, though contiguous allocation is still conceptually foundational and appears in simplified embedded or early-boot memory management.
- Simple to implement with just base and limit registers for bounds checking
- Fast address translation — no page table lookups needed
- Foundational concept for understanding fragmentation before paging
- Still used in constrained embedded or early-boot memory contexts
AI Mentor Explanation
Contiguous memory allocation is like assigning each touring team one unbroken block of adjacent hotel rooms rather than scattering them across different floors — the whole squad must fit in one continuous run of rooms. When a team checks out, that block becomes a free run of rooms of a specific size, and the front desk must find a new team whose squad size fits that exact run, or a bigger one, using a first-fit or best-fit policy. Over a busy season, checkouts of different-sized squads leave scattered runs of free rooms that do not line up, mirroring external fragmentation.
Step-by-Step Explanation
Step 1
Track free holes
The OS maintains a list of free contiguous regions and allocated partitions in physical memory.
Step 2
Search for a fit
When a process arrives, the OS searches free holes using first-fit, best-fit, or worst-fit to find one large enough.
Step 3
Allocate and bound
The process is placed in the chosen hole; base and limit registers record its start address and size for bounds checking.
Step 4
Free and fragment
When the process exits, its block becomes free again, potentially leaving a scattered hole that contributes to external fragmentation.
What Interviewer Expects
- Definition tied to each process occupying one unbroken physical memory block
- Ability to name and contrast first-fit, best-fit, and worst-fit
- Understanding that contiguous allocation is inherently prone to external fragmentation
- Knowing paging replaced it in modern general-purpose OS memory management
Common Mistakes
- Confusing contiguous allocation with paging
- Thinking best-fit always wastes the least memory in practice
- Not mentioning external fragmentation as the core weakness
- Forgetting base/limit registers as the simple protection mechanism used
Best Answer (HR Friendly)
“Contiguous memory allocation means giving each running program one single, unbroken chunk of memory rather than spreading it across scattered pieces. It is simple and fast to work with, but because programs come and go with different sizes, the free space left behind gets chopped into odd-sized gaps over time, which is exactly the fragmentation problem that later led operating systems to switch to paging instead.”
Code Example
struct hole { size_t start, size; struct hole *next; };
/* returns start address of allocated region, or -1 if no hole fits */
long first_fit_alloc(struct hole **free_list, size_t requested) {
struct hole *prev = NULL, *h = *free_list;
while (h) {
if (h->size >= requested) {
long addr = h->start;
h->start += requested;
h->size -= requested;
if (h->size == 0) { /* hole fully consumed */
if (prev) prev->next = h->next; else *free_list = h->next;
free(h);
}
return addr;
}
prev = h;
h = h->next;
}
return -1; /* no hole large enough: external fragmentation may be the cause */
}Follow-up Questions
- What are the trade-offs between first-fit, best-fit, and worst-fit?
- Why does contiguous allocation lead to external fragmentation over time?
- How does paging eliminate the problems of contiguous allocation?
- What role do base and limit registers play in contiguous allocation?
MCQ Practice
1. In contiguous memory allocation, what must be true for a process to be loaded?
Contiguous allocation requires the whole process to occupy a single continuous run of physical addresses, unlike paging.
2. Which allocation strategy searches for the smallest hole that still fits the request?
Best-fit scans all holes and picks the smallest one that satisfies the request, aiming to minimize leftover space per allocation.
3. What is the primary weakness of contiguous memory allocation?
Because allocations and frees leave holes of varying sizes scattered across memory, contiguous allocation is inherently susceptible to external fragmentation.
Flash Cards
What is contiguous memory allocation? — Assigning each process one unbroken block of physical memory addresses.
Name the three placement strategies. — First-fit, best-fit, and worst-fit.
Main weakness of contiguous allocation? — It is prone to external fragmentation as processes of different sizes allocate and free memory.
What replaced pure contiguous allocation in modern OSes? — Paging, which uses fixed-size, non-contiguous frames.