In Memory Management Basics we saw the simplest kind of MMU: a relocation (base) register and a limit register. That hardware assumes something important: each process sits in one continuous block of physical memory. If the process starts at address 300 000 and is 120 000 bytes long, it owns every byte from 300 000 to 419 999 and nothing else.
This idea is called contiguous memory allocation. It is the oldest and simplest way to share RAM between processes, and it leads straight to one of the most important problems in memory management: fragmentation, free memory that exists but cannot be used.
In this chapter we will learn fixed and variable partitioning, the four placement algorithms (first fit, next fit, best fit, worst fit) with full traces, internal vs external fragmentation, compaction, and the buddy system that Linux still uses today. Understanding these problems is what makes Paging (the next chapter) feel like the obvious solution.
What is Contiguous Memory Allocation?
Contiguous memory allocation is a memory management technique in which each process is given a single, continuous section of physical memory.
Main memory is usually divided into two parts:
One part for the operating system (on many systems it sits in high memory, on others in low memory; the idea is the same).
The rest for user processes, which is the part we have to divide up.
Physical memory
+----------------------+ 0
| Operating system |
+----------------------+
| Process P1 | <- one continuous block
+----------------------+
| Process P2 | <- one continuous block
+----------------------+
| (free) |
+----------------------+
| Process P3 |
+----------------------+ max
Protection is done exactly as in the previous chapter: when the CPU scheduler picks a process, the dispatcher loads that process's base and limit into the MMU. Every logical address is checked against the limit and then added to the base. A process simply cannot form an address outside its own block.
The question this chapter answers is: how does the OS decide where each block goes, and what happens to the gaps? There are two main schemes: fixed partitioning and variable partitioning.
Fixed (Static) Partitioning
The oldest method divides user memory into a number of partitions when the system starts (historically set by the operator at boot time). The partition sizes then never change. Each partition can hold exactly one process.
IBM's OS/360 used this scheme and called it MFT (Multiprogramming with a Fixed number of Tasks).
The partitions can be:
Equal-sized: simple, but a small process wastes most of its partition, and a process bigger than the partition can never run.
Unequal-sized: some small and some large partitions, so each process can be placed in the smallest partition that fits it.
Worked example
User memory is split into four partitions of 100, 200, 300 and 400 KB. Five processes arrive in this order, and each one is placed in the smallest free partition that is big enough:
Process | Size | Partition given | Wasted inside partition |
|---|---|---|---|
P1 | 90 KB | 100 KB | 10 KB |
P2 | 250 KB | 300 KB | 50 KB |
P3 | 150 KB | 200 KB | 50 KB |
P4 | 350 KB | 400 KB | 50 KB |
P5 | 120 KB | none free, must wait | - |
+-------------------+
| P1 90 KB | 10 KB | partition 1 (100 KB)
+-------------------+
| P3 150 KB | 50 KB | partition 2 (200 KB)
+-------------------+
| P2 250 KB | 50 KB | partition 3 (300 KB)
+-------------------+
| P4 350 KB | 50 KB | partition 4 (400 KB)
+-------------------+
^^^^^
wasted: 10 + 50 + 50 + 50 = 160 KB
Look at what happened. 160 KB of memory is unused, which is more than the 120 KB that P5 needs, yet P5 has to wait. The free space is trapped inside partitions that already belong to other processes. This waste is called internal fragmentation.
Problems with fixed partitioning
Internal fragmentation: a process rarely fills its partition exactly.
Fixed degree of multiprogramming: with 4 partitions, at most 4 processes can be in memory, no matter how small they are.
Size limit: a process larger than the biggest partition can never run (unless the programmer uses tricks like overlays).
Its advantage is simplicity: the OS only needs a small table saying which partitions are busy.
Variable (Dynamic) Partitioning
To avoid internal fragmentation, we can make each partition exactly as big as the process. Partitions are created at run time, when processes arrive. OS/360 called this MVT (Multiprogramming with a Variable number of Tasks).
The OS keeps track of:
which parts of memory are allocated, and
which parts are free. A free block of memory is called a hole.
At the start, all user memory is one big hole. As processes arrive and leave, memory becomes a mix of allocated blocks and holes of different sizes scattered around.
Step-by-step trace
User memory is 1000 KB (addresses written relative to the start of user memory). Four processes arrive: P1 = 200 KB, P2 = 300 KB, P3 = 150 KB, P4 = 250 KB.
Step 1: load P1, P2, P3, P4 Step 2: P2 and P4 finish
0 +-----------+ 0 +-----------+
| P1 200 KB | | P1 200 KB |
200 +-----------+ 200 +-----------+
| P2 300 KB | | hole | 300 KB
500 +-----------+ 500 +-----------+
| P3 150 KB | | P3 150 KB |
650 +-----------+ 650 +-----------+
| P4 250 KB | | hole | 350 KB
900 +-----------+ | | (P4's 250 KB merged with
| hole 100 | | | the 100 KB hole after it)
1000 +-----------+ 1000 +-----------+
Notice that when P4 left, its block was next to the existing 100 KB hole, so the two were merged (coalesced) into one 350 KB hole. Merging adjacent holes is essential, otherwise memory would break into smaller and smaller pieces.
Now a new process P5 needs 400 KB.
Total free memory = 300 + 350 = 650 KB, which is plenty.
Largest single hole = 350 KB, which is too small.
P5 cannot be loaded, because contiguous allocation needs all 400 KB in one piece. This is external fragmentation: enough total free memory exists, but it is split into holes that are each too small. We will fix this example with compaction later in the chapter.
Variable partitioning has no internal fragmentation (in theory; see the note on tiny holes below), but it suffers from external fragmentation instead. It also creates a new question: when several holes are big enough, which one should we use?
Placement Algorithms: First, Next, Best and Worst Fit
This is called the dynamic storage-allocation problem: how to satisfy a request of size n from a list of free holes. The four classic strategies are:
Algorithm | Rule | Search needed |
|---|---|---|
First fit | Scan holes from the beginning of memory; take the first hole that is big enough. | Stops early |
Next fit | Like first fit, but start scanning from where the last search ended, wrapping around. | Stops early |
Best fit | Take the smallest hole that is big enough. | Whole list (unless kept sorted by size) |
Worst fit | Take the largest hole. | Whole list (unless kept sorted by size) |
In every case, the chosen hole is split: the process gets the first part, and the leftover becomes a smaller hole.
The thinking behind each rule:
First fit: "Don't waste time searching, just take something that works."
Best fit: "Keep the big holes for big processes; leave the smallest possible leftover."
Worst fit: "Leave the biggest possible leftover, so that it is still useful for someone else."
Next fit: "Don't keep cutting up the start of memory; spread allocations evenly."
Worked example
Memory has five holes, in address order: 150, 400, 250, 600 and 300 KB. Four processes arrive in order: P1 = 220 KB, P2 = 380 KB, P3 = 130 KB, P4 = 560 KB. Let us apply each algorithm.
First fit
P1 (220): 150 is too small; 400 fits. Hole 2 becomes 400 − 220 = 180.
P2 (380): 150, 180, 250 are too small; 600 fits. Hole 4 becomes 220.
P3 (130): 150 fits (first hole). Hole 1 becomes 20.
P4 (560): holes are now 20, 180, 250, 220, 300. None is ≥ 560. P4 waits.
Next fit (the search pointer starts at hole 1)
P1 (220): from hole 1: 150 no, 400 yes. Hole 2 becomes 180. Pointer stays at hole 2.
P2 (380): from hole 2: 180 no, 250 no, 600 yes. Hole 4 becomes 220. Pointer at hole 4.
P3 (130): from hole 4: 220 fits. Hole 4 becomes 90. (First fit would have gone back to hole 1.)
P4 (560): 90, 300, 150, 180, 250, no hole is big enough. P4 waits.
Best fit
P1 (220): holes that fit are 400, 250, 600, 300; smallest is 250. Leftover 30.
P2 (380): holes that fit are 400, 600; smallest is 400. Leftover 20.
P3 (130): holes that fit are 150, 600, 300; smallest is 150. Leftover 20.
P4 (560): only 600 fits. Leftover 40. All four processes are loaded.
Worst fit
P1 (220): largest hole is 600. Leftover 380.
P2 (380): holes are 150, 400, 250, 380, 300; largest is 400. Leftover 20.
P3 (130): largest is now 380. Leftover 250.
P4 (560): largest hole is 300. P4 waits.
Here is a small C program that simulates all four algorithms on the same input. It keeps only the hole sizes, because that is all the placement decision depends on:
#include <stdio.h>
enum fit { FIRST, NEXT, BEST, WORST };
static const char *names[] = { "First fit", "Next fit", "Best fit", "Worst fit" };
/* Pick a hole for a request of 'req' KB. Returns its index, or -1 if none fits. */
static int choose(const int h[], int n, int req, enum fit f, int *next)
{
if (f == NEXT) {
for (int k = 0; k < n; k++) {
int i = (*next + k) % n; /* resume where we stopped */
if (h[i] >= req) { *next = i; return i; }
}
return -1;
}
int pick = -1;
for (int i = 0; i < n; i++) {
if (h[i] < req) continue; /* too small, skip */
if (f == FIRST) return i; /* first one that fits */
if (pick == -1 ||
(f == BEST && h[i] < h[pick]) || /* smallest that fits */
(f == WORST && h[i] > h[pick])) /* largest of all */
pick = i;
}
return pick;
}
static void run(const int sizes[], int n, const int req[], int m, enum fit f)
{
int h[16], next = 0;
for (int i = 0; i < n; i++) h[i] = sizes[i]; /* fresh copy for each algorithm */
printf("%s:\n", names[f]);
for (int j = 0; j < m; j++) {
int i = choose(h, n, req[j], f, &next);
if (i < 0) { printf(" P%d (%3d KB) -> must WAIT\n", j + 1, req[j]); continue; }
printf(" P%d (%3d KB) -> hole %d (%3d KB), leftover %3d KB\n",
j + 1, req[j], i + 1, h[i], h[i] - req[j]);
h[i] -= req[j]; /* the rest stays a (smaller) hole */
}
printf(" holes left:");
for (int i = 0; i < n; i++) printf(" %d", h[i]);
printf("\n");
}
int main(void)
{
const int holes[] = { 150, 400, 250, 600, 300 }; /* in address order */
const int reqs[] = { 220, 380, 130, 560 };
for (int f = FIRST; f <= WORST; f++)
run(holes, 5, reqs, 4, (enum fit)f);
return 0;
}
Compiled with gcc -std=c17 -Wall -Wextra fits.c -o fits and run on Linux, it prints:
First fit:
P1 (220 KB) -> hole 2 (400 KB), leftover 180 KB
P2 (380 KB) -> hole 4 (600 KB), leftover 220 KB
P3 (130 KB) -> hole 1 (150 KB), leftover 20 KB
P4 (560 KB) -> must WAIT
holes left: 20 180 250 220 300
Next fit:
P1 (220 KB) -> hole 2 (400 KB), leftover 180 KB
P2 (380 KB) -> hole 4 (600 KB), leftover 220 KB
P3 (130 KB) -> hole 4 (220 KB), leftover 90 KB
P4 (560 KB) -> must WAIT
holes left: 150 180 250 90 300
Best fit:
P1 (220 KB) -> hole 3 (250 KB), leftover 30 KB
P2 (380 KB) -> hole 2 (400 KB), leftover 20 KB
P3 (130 KB) -> hole 1 (150 KB), leftover 20 KB
P4 (560 KB) -> hole 4 (600 KB), leftover 40 KB
holes left: 20 20 30 40 300
Worst fit:
P1 (220 KB) -> hole 4 (600 KB), leftover 380 KB
P2 (380 KB) -> hole 2 (400 KB), leftover 20 KB
P3 (130 KB) -> hole 4 (380 KB), leftover 250 KB
P4 (560 KB) -> must WAIT
holes left: 150 20 250 250 300
The output matches our hand traces. Summary of this example:
Algorithm | P1 | P2 | P3 | P4 (560 KB) |
|---|---|---|---|---|
First fit | 400 | 600 | 150 | waits |
Next fit | 400 | 600 | 220 (left of 600) | waits |
Best fit | 250 | 400 | 150 | 600, loaded |
Worst fit | 600 | 400 | 380 (left of 600) | waits |
Why did best fit win? It was the only algorithm that left the 600 KB hole untouched. First fit, next fit and worst fit all cut a piece out of the 600 KB hole early, and then nothing big was left for P4. Notice also the price best fit paid: its leftovers are 20, 20, 30 and 40 KB, tiny holes that are probably too small for any future process.
No algorithm always wins
It is tempting to conclude "best fit is best". It is not always. Take two holes, 650 KB and 600 KB, and requests 500, 550 and 125 KB:
Request | First fit | Best fit |
|---|---|---|
500 KB | 650 → leftover 150 | 600 → leftover 100 |
550 KB | 600 → leftover 50 | 650 → leftover 100 |
125 KB | 150 → leftover 25 ✔ | holes are 100 and 100 → waits ✘ |
Here first fit succeeds and best fit fails, because best fit split the space "evenly" into two medium holes, neither of which can hold 125 KB. You can build an example to make any of these algorithms look good or bad. That is why the comparison is based on simulations with realistic workloads, not single examples.
What simulations show
First fit and best fit are both better than worst fit in terms of memory utilisation and speed.
Neither first fit nor best fit is clearly better at utilisation, but first fit is usually faster, because it stops at the first match.
Best fit tends to create many tiny holes that are almost useless.
Worst fit quickly destroys all large holes, so large processes starve.
Next fit spreads allocations over all of memory; in practice it often performs slightly worse than first fit because it also breaks up the large hole at the end of memory.
For GATE and interviews, the safe one-liner is: first fit is generally the best practical choice (fast and good utilisation); worst fit is generally the worst.
Internal vs External Fragmentation
We have now met both kinds of fragmentation. They are easy to confuse, so let us put them side by side.
Internal fragmentation is unused memory inside an allocated block: the block given to a process is larger than what the process asked for.
External fragmentation is free memory outside allocated blocks that is split into pieces too small to satisfy a request, even though the total free memory would be enough.
Internal fragmentation External fragmentation
+--------------------+ +--------+
| process data | | P1 |
| | +--------+
+ - - - - - - - - - -+ | hole 1 | <- 300 KB free
| allocated but | <- wasted, +--------+
| unused | inside | P3 |
+--------------------+ the block +--------+
| hole 2 | <- 350 KB free
+--------+
Request of 400 KB fails,
although 650 KB is free.
Point | Internal fragmentation | External fragmentation |
|---|---|---|
Where is the waste? | Inside an allocated block | Between allocated blocks (in holes) |
Cause | Memory is handed out in fixed-size units (partitions, pages, power-of-2 blocks) | Memory is handed out in exact, variable sizes; processes leave holes when they exit |
Who can use the waste? | Nobody, it belongs to the owning process until it exits | Anyone, if the pieces were joined together |
Seen in | Fixed partitioning, paging (last page), buddy system | Variable partitioning, segmentation |
Main fixes | Smaller allocation units | Compaction, or non-contiguous allocation (paging) |
Tiny holes and why a little internal fragmentation is accepted
Suppose a hole is 10 004 bytes and a process asks for 10 000 bytes. Giving exactly 10 000 bytes leaves a 4-byte hole. Keeping track of that hole in the free list costs more memory than the hole itself. So real allocators round requests up to some minimum unit and give the whole small leftover to the process. That means even "variable" partitioning has a little internal fragmentation in practice.
The 50-percent rule
How bad is external fragmentation in practice? Donald Knuth's analysis of first fit, known as the 50-percent rule, says that in a steady state, if there are N allocated blocks, there are about N/2 holes. Operating systems textbooks state the practical consequence like this: given N allocated blocks, another 0.5N blocks are lost to fragmentation, so up to about one-third of memory may be unusable. That is a lot of RAM to waste, and it is the main motivation for compaction and paging.
Freeing Memory and Merging Holes
When a process ends, its block becomes a hole. The OS must check its neighbours. There are four cases:
Neighbour above | Neighbour below | What happens |
|---|---|---|
Allocated | Allocated | A new separate hole is added to the free list |
Hole | Allocated | Merge with the hole above |
Allocated | Hole | Merge with the hole below |
Hole | Hole | Merge all three into one hole (the free list gets one entry shorter) |
Keeping the free list sorted by address makes this check cheap, because the neighbours of a block are next to each other in the list. This is one reason first fit, which scans in address order, is popular: the same list serves both allocation and merging. Best fit and worst fit would prefer a list sorted by size, which makes merging harder.
Compaction
The most direct fix for external fragmentation is to shuffle the processes together so all the holes join into one big hole.
Compaction is the process of moving allocated blocks in memory so that all free memory is collected into one large contiguous block.
Back to our trace, where P5 (400 KB) could not be loaded. If the OS moves P3 down to address 200, the two holes join:
Before compaction After compaction (move P3 only)
0 +-----------+ 0 +-----------+
| P1 200 KB | | P1 200 KB |
200 +-----------+ 200 +-----------+
| hole 300 | | P3 150 KB |
500 +-----------+ 350 +-----------+
| P3 150 KB | | |
650 +-----------+ | hole | 650 KB, now P5 (400 KB)
| hole 350 | | | fits easily
1000 +-----------+ 1000 +-----------+
Data copied: 150 KB (only P3 moved)
Choosing which blocks to move matters. Moving P1 instead would not have helped, and moving everything to one end is simple but can copy far more data than necessary. Finding the cheapest compaction is a hard problem in general, so real systems use simple heuristics.
When is compaction possible?
Compaction is only possible if relocation is dynamic, done at execution time (see Address Binding in Memory Management Basics). After copying a process to a new place, the OS just updates its base register; the process's logical addresses do not change. If addresses were fixed at compile time or load time, the copied program would still contain the old physical addresses and would break.
Why compaction is expensive
It copies large amounts of memory. Even at several GB per second, moving gigabytes takes a noticeable amount of time, and the processes being moved cannot run during their copy.
I/O problem: if a device is doing DMA into a process's buffer, moving that process would make the device write into the wrong place. Such processes must be kept in place (pinned) or I/O must be done only through OS buffers.
It must be repeated, because fragmentation comes back as processes keep arriving and leaving.
The better long-term fix is to drop the "one contiguous block" rule altogether, which is exactly what Paging and Segmentation do.
The Buddy System
Fixed partitions waste space inside blocks; variable partitions waste space between blocks and make merging messy. The buddy system is a clever compromise between the two, and it is still in use: the Linux kernel allocates physical page frames with a buddy allocator.
In the buddy system, memory is allocated in blocks whose sizes are powers of 2. A request is rounded up to the next power of 2. A larger free block is split in half repeatedly until a block of the right size exists; the two halves of a split are called buddies. When a block is freed and its buddy is also free, they are merged back into the larger block.
Worked example
We start with one free block of 1024 KB (addresses 0 to 1023 KB). Four requests arrive: A = 100 KB, B = 240 KB, C = 60 KB, D = 130 KB.
A = 100 KB → round up to 128 KB. No 128 KB block exists, so we split:
1024 -> 512 @0 + 512 @512
512 @0 -> 256 @0 + 256 @256
256 @0 -> 128 @0 + 128 @128
A gets 128 @0 (wasted 128 - 100 = 28 KB)
B = 240 KB → round up to 256 KB. A free 256 KB block exists at 256. B gets it (wasted 16 KB).
C = 60 KB → 64 KB. Split the free 128 KB block at 128 into 64 @128 and 64 @192. C gets 64 @128 (wasted 4 KB).
D = 130 KB → 256 KB. No free 256 KB block left, so split the 512 KB block at 512 into 256 @512 and 256 @768. D gets 256 @512 (wasted 126 KB).
0 128 192 256 512 768 1024
+---------+-----+-----+----------------+----------------+----------------+
| A (128) | C |free | B (256) | D (256) | free (256) |
| uses 100| 64 | 64 | uses 240 | uses 130 | |
+---------+-----+-----+----------------+----------------+----------------+
Free lists: 64 KB: [192] 256 KB: [768]
Internal fragmentation: 28 + 16 + 4 + 126 = 174 KB
Look at D: it asked for 130 KB but got 256 KB, wasting almost half. Rounding up to powers of 2 can waste nearly 50% of a block in the worst case. This is the buddy system's weakness: internal fragmentation.
Now the strength: freeing and merging is very fast.
Free A (128 @0). Its buddy is 128 @128, but that block is split (C lives in it). No merge. Free lists: 64: [192], 128: [0], 256: [768].
Free C (64 @128). Its buddy 64 @192 is free → merge into 128 @128. That block's buddy 128 @0 (old A) is free → merge into 256 @0. Its buddy 256 @256 is B, still in use → stop. Free lists: 256: [0, 768].
Free B (256 @256). Its buddy 256 @0 is free → merge into 512 @0. Its buddy 512 @512 contains D → stop. Free lists: 256: [768], 512: [0].
Why finding a buddy is so cheap
For a block of size s (a power of 2) at address a (always a multiple of s), the buddy's address is just a XOR s. For example, the buddy of 64 @128 is 128 XOR 64 = 192, and the buddy of 128 @128 is 128 XOR 128 = 0. No searching through a list of neighbours is needed. Only two blocks that came from the same split can merge; 256 @256 and 256 @512 are adjacent but not buddies, so they never merge directly.
The buddy system on a real Linux machine
Linux shows the state of its buddy allocator in /proc/buddyinfo. Each column counts the free blocks of one order: order k means a block of 2k contiguous pages. Here is the real output from a WSL2 Linux system (kernel 6.18, page size 4096 bytes):
cat /proc/buddyinfoNode 0, zone DMA32 1 1 0 0 1 2 1 0 2 2 973
Node 0, zone Normal 614 103 99 126 38 24 56 34 27 15 1338
The columns are orders 0 to 10. In the Normal zone there are 614 free single pages (4 KB), 103 free blocks of 2 pages (8 KB), and so on up to 1338 free blocks of order 10 (210 × 4 KB = 4 MB each). Your numbers will be different and change from moment to moment. If the right-hand columns drop towards zero while the left-hand columns are large, physical memory has become fragmented: plenty of free pages, but few large contiguous runs. The kernel needs such runs for things like huge pages and some device buffers, which is why Linux also has its own memory compaction.
So even on a modern system that uses paging for processes, the fragmentation ideas from this chapter are alive inside the kernel, and inside user-space allocators like malloc, which must carve variable-sized blocks out of the heap.
Contiguous Allocation Schemes Compared
Feature | Fixed partitioning | Variable partitioning | Buddy system |
|---|---|---|---|
Block sizes | Set at boot, never change | Exactly the request size | Powers of 2 |
Internal fragmentation | Yes | No (except tiny rounding) | Yes, up to almost 50% of a block |
External fragmentation | No new holes form, but free partitions can be too small for a waiting process | Yes, the main problem | Yes, but reduced by fast merging |
Degree of multiprogramming | Fixed (= number of partitions) | Varies with process sizes | Varies |
Bookkeeping | Very simple table | Free list; merging needed | One free list per size; buddy found with XOR |
Example use | IBM OS/360 MFT, simple embedded systems | IBM OS/360 MVT | Linux physical page allocator |
Practice Numericals
Q1. Fixed partitions of 200, 400, 600 and 500 KB (in that order). Processes of 357, 210, 468 and 491 KB arrive in order. Using best fit, which process cannot be allocated, and what is the total internal fragmentation of the others?
357 → 400 (43 left). 210 → the free partitions that fit are 600 and 500; the smallest is 500 (290 left). 468 → 600 (132 left). 491 → only 200 is free, too small, so 491 KB waits. Internal fragmentation = 43 + 290 + 132 = 465 KB.
Q2. Holes of 300, 120, 500 and 200 KB (in address order). A request of 180 KB arrives. Which hole does each of first, best and worst fit choose?
First fit: 300 (first one ≥ 180). Best fit: 200 (smallest ≥ 180). Worst fit: 500 (largest).
Q3. In a buddy system with 512 KB of memory, how much memory is actually given for requests of 33 KB, 64 KB and 65 KB?
33 KB → 64 KB (31 KB wasted). 64 KB → 64 KB (no waste). 65 KB → 128 KB (63 KB wasted). Requests just above a power of 2 waste nearly half the block.
Q4. Memory has holes of 100, 50 and 80 KB scattered between processes. A 200 KB process arrives. Can it be loaded? What can the OS do?
Total free = 230 KB, but the largest hole is 100 KB, so it cannot be loaded with contiguous allocation (external fragmentation). The OS can compact memory (if relocation is done at execution time) to create one 230 KB hole, or the process waits. With paging, the problem would not arise.
Common Mistakes
Mixing up internal and external fragmentation. Ask "is the wasted space inside a block someone owns?" If yes, it is internal. If it is free but in pieces that are too small, it is external.
Saying variable partitioning has internal fragmentation. In theory it does not; that is the whole point of sizing partitions exactly. Its problem is external fragmentation.
Forgetting to update the hole after allocation. In numericals, the leftover part of a hole stays in the list and can be used by the next request. Many wrong answers come from treating the whole hole as used.
Running worst fit on the original sizes. After every allocation the hole sizes change, so "the largest hole" must be recomputed each time.
Next fit pointer. Next fit continues from the hole where the last allocation happened, not from the hole after it, and it wraps around to the beginning.
Thinking compaction is always possible. It needs execution-time address binding, and it cannot freely move memory that a device is using for DMA.
Thinking best fit is always best. It leaves tiny useless holes, and counter-examples exist where first fit succeeds and best fit fails.
Merging blocks that are adjacent but not buddies in the buddy system. Only the two halves of the same split can merge.
Interview Questions
What is contiguous memory allocation?
Each process is given one single continuous block of physical memory. It is implemented with base (relocation) and limit registers, and it suffers from fragmentation.
What is the difference between internal and external fragmentation?
Internal fragmentation is wasted space inside an allocated block, because the block is bigger than the request. External fragmentation is free space split into holes that are each too small for a request, even though their total is enough.
Which fragmentation occurs in fixed partitioning, and which in variable partitioning?
Fixed partitioning mainly suffers from internal fragmentation. Variable partitioning suffers from external fragmentation.
Explain first fit, best fit and worst fit. Which is generally best?
First fit takes the first hole that is large enough, best fit the smallest hole that is large enough, worst fit the largest hole. Simulations show first fit and best fit beat worst fit; first fit is usually preferred because it is faster with similar utilisation.
What is the disadvantage of best fit?
It must search the whole list (unless the list is sorted by size), and it leaves very small leftover holes that are usually too small to be useful, increasing external fragmentation.
What is compaction and what does it require?
Compaction moves processes so that all free holes join into one large block. It requires dynamic (execution-time) relocation so a moved process keeps working after its base register is updated. It is expensive because it copies memory and must be repeated.
What is the 50-percent rule?
From Knuth's analysis of first fit: in steady state, with N allocated blocks there are about N/2 holes, so roughly 0.5N blocks are lost to fragmentation, meaning up to one-third of memory may be unusable.
How does the buddy system work, and where is it used?
Memory is handed out in power-of-2 blocks. Larger blocks are split in halves until the right size is reached, and a freed block is merged with its buddy (found by XOR of the address with the block size) when the buddy is also free. Linux uses it to allocate physical page frames.
How do paging and segmentation solve the problems of contiguous allocation?
They allow a process to be stored in several non-contiguous pieces. Paging uses fixed-size frames, which eliminates external fragmentation completely; segmentation uses variable-size segments, which reduces the problem but does not remove it.
Summary
Contiguous allocation gives each process one continuous block of physical memory, protected by base and limit registers.
Fixed partitioning (MFT) divides memory into partitions at boot; simple, but causes internal fragmentation and limits the number and size of processes.
Variable partitioning (MVT) creates exact-size partitions at run time; no internal fragmentation, but external fragmentation as holes form.
Placement: first fit (first big-enough hole), next fit (first fit from the last position), best fit (smallest big-enough hole), worst fit (largest hole). First fit and best fit beat worst fit; first fit is usually fastest.
Freed blocks must be merged with neighbouring holes.
The 50-percent rule: about N/2 holes for N blocks, so up to one-third of memory can be wasted.
Compaction joins the holes by moving processes; it needs execution-time binding and is expensive.
The buddy system uses power-of-2 blocks and fast XOR-based merging; it trades external fragmentation for internal fragmentation and is used by the Linux page allocator.
The real cure is to stop requiring one continuous block. In the next chapter, Paging, we cut both processes and memory into equal-sized pieces so that any free frame can hold any page, and external fragmentation disappears.