Contiguous memory allocation questions give you a list of free memory blocks (holes) and a list of processes that need memory, in order, and ask where each process goes. The four strategies differ only in which hole they pick.
The exercise (from Silberschatz, Operating System Concepts): holes of 100, 500, 200, 300 and 600 KB, in that order; processes of 212, 417, 112 and 426 KB, arriving in that order. Which algorithm makes the most efficient use of memory?
The four rules
- First fit: the first hole from the start that is big enough.
- Best fit: the smallest hole that is big enough.
- Worst fit: the largest hole.
- Next fit: like first fit, but start searching from where the last allocation was made.
In the usual (variable-partition) reading, a process takes only what it needs and the rest of the hole stays free for later processes.
First fit
| Process | Goes into | Hole left |
|---|---|---|
| 212 KB | 500 KB hole | 288 KB |
| 417 KB | 600 KB hole (100, 288, 200, 300 are too small) | 183 KB |
| 112 KB | the 288 KB leftover | 176 KB |
| 426 KB | nothing is big enough | must wait |
Best fit
| Process | Goes into | Hole left |
|---|---|---|
| 212 KB | 300 KB hole (smallest that fits) | 88 KB |
| 417 KB | 500 KB hole | 83 KB |
| 112 KB | 200 KB hole | 88 KB |
| 426 KB | 600 KB hole | 174 KB |
All four processes are placed.
Worst fit
| Process | Goes into | Hole left |
|---|---|---|
| 212 KB | 600 KB hole (largest) | 388 KB |
| 417 KB | 500 KB hole | 83 KB |
| 112 KB | the 388 KB leftover | 276 KB |
| 426 KB | the largest hole is now 300 KB | must wait |
Next fit
Starts at the 500 KB hole for 212 KB (288 left), moves on to the 600 KB hole for 417 KB (183 left), then continues from there: the 183 KB leftover takes 112 KB (71 left). 426 KB must wait.
The answer
Only best fit places all four processes, so it uses memory most efficiently here. Worst fit breaks up the big 600 KB hole early, which is exactly the hole the 426 KB process needed later.
This isn't a general law. Best fit tends to leave many tiny unusable holes over time (external fragmentation), and it has to search every hole. Exam answers are about the specific sequence you are given.
Fixed partitions: internal fragmentation
Some courses ask the same question with fixed partitions: each partition holds one process, and the space left inside it is wasted (internal fragmentation). With best fit the processes land in the 300, 500, 200 and 600 KB partitions, wasting 88 + 83 + 88 + 174 = 433 KB. Check which reading your question uses; the placements for the later processes change.
Check your answers
The memory allocation calculator runs first, best, worst and next fit on your own holes and processes, in both the variable and fixed readings, and explains each placement. For the next topics in the unit, see cache mapping and the page replacement simulator.