Memory Allocation Algorithms
Given a list of free holes and a request, which hole do you use? First fit takes the first that works, best fit the tightest, worst fit the largest. The counterintuitive result is that best fit is usually not best.
The Problem Being Solved
Contiguous memory allocation gives each process one unbroken run of memory, and the memory allocation algorithms in OS are the rules that decide which run it gets. Over time, as processes come and go, free memory becomes a list of holes of differing sizes. When a request for n bytes arrives and several holes are large enough, the allocator must pick one — and memory allocation algorithms is the name for that choice.
The choice matters because the leftover determines future external fragmentation. Allocating 12 KB from a 13 KB hole leaves a 1 KB sliver that will likely never be used again. Allocating the same 12 KB from a 60 KB hole leaves 48 KB, which is useful. Every placement decision either creates a usable remainder or a dead one.
The three classical strategies — first fit, best fit, worst fit memory allocation — are the standard comparison, and the standard result is not the intuitive one.
- Several holes may fit; the allocator must choose
- The leftover decides future fragmentation
- A tight fit leaves a sliver nothing can reuse
- A loose fit consumes a hole large requests need
First Fit, Best Fit, Worst Fit
First fit scans from the start of the hole list and takes the first hole large enough. It is the fastest of the three because it stops early, and it does not need the list sorted. Its known weakness is that small unusable slivers accumulate at the low-address end, which the scan then has to walk past on every request.
Best fit scans the whole list and takes the smallest hole that fits, on the reasoning that this wastes the least. It must examine every hole unless the list is size-sorted, and the intuition is wrong: taking the tightest fit is precisely what produces remainders too small to reuse. Best fit is the strategy most reliably criticised in the literature for exactly the property its name advertises.
Worst fit takes the largest hole, reasoning that the remainder will be big enough to be useful. It also scans the whole list, and it performs worst in practice — it consumes the large holes that future large requests will need, so the allocator runs out of big contiguous runs quickest.
Next fit is first fit with memory: the scan resumes where the last one stopped rather than restarting. This avoids re-walking the sliver-heavy start of the list, spreading allocations more evenly, at the cost of fragmenting the whole space rather than concentrating damage at one end.
- First fit — first hole that fits, stops scanning early
- Best fit — tightest hole, must scan the whole list
- Worst fit — largest hole, performs worst in practice
- Next fit — resumes the scan where the last one ended
What Measurement Says
Simulation studies going back to Knuth and repeated many times since put first fit and next fit ahead of best fit on both storage utilisation and speed, with worst fit last on both. The theoretical framing is the fifty-percent rule: under first fit at equilibrium, if N blocks are allocated, roughly 0.5N are lost to holes, meaning about a third of memory is unusable.
The reason best fit underperforms is worth stating precisely, because the causation is what gets remembered wrongly. It is not that best fit wastes more space per allocation — it wastes less, by definition. It is that the space it leaves is systematically the least useful shape: a large number of very small fragments, each too small to satisfy any real request, and each still costing a list entry to track.
Modern general-purpose allocators have largely moved past this comparison by avoiding the single-hole-list model entirely. Segregated free lists keep separate lists per size class, so the search is O(1) into the right class rather than a scan. Buddy allocators make coalescing cheap. The classical three remain the right teaching example because they isolate the placement decision from everything else.
- First and next fit beat best fit on space and speed
- Best fit fails by leaving many unusable fragments
- The fifty-percent rule: about a third of memory lost
- Segregated free lists replace the scan entirely
One hole list, one request, three strategies — and best fit loses
# First fit, best fit, worst fit on the same hole list. The interesting
# output is not which fits -- it is the SHAPE of the leftovers each creates.
def first_fit(holes, size):
for i, h in enumerate(holes):
if h >= size: # stop at the first that works
return i
return -1
def best_fit(holes, size):
best, bi = None, -1
for i, h in enumerate(holes): # must scan the whole list
if h >= size and (best is None or h < best):
best, bi = h, i # tightest fit -> smallest remainder
return bi
def worst_fit(holes, size):
worst, wi = None, -1
for i, h in enumerate(holes):
if h >= size and (worst is None or h > worst):
worst, wi = h, i # largest hole -> biggest remainder
return wi
def run(strategy, holes, requests):
holes = list(holes)
for r in requests:
i = strategy(holes, r)
if i < 0:
return holes, "FAILED on %d" % r
holes[i] -= r # the remainder stays as a hole
return holes, "all placed"
HOLES = [100, 500, 200, 300, 600]
REQS = [212, 417, 112, 426]
for name, f in [("first", first_fit), ("best", best_fit), ("worst", worst_fit)]:
holes, verdict = run(f, HOLES, REQS)
print("%-5s fit: %-26s %s" % (name, holes, verdict))
print("total free in every case: %d KB" % sum(run(first_fit, HOLES, REQS)[0]))
// The three classical placement strategies over one free list.
#include <iostream>
#include <vector>
#include <string>
int firstFit(const std::vector<int>& h, int size) {
for (int i = 0; i < (int)h.size(); ++i)
if (h[i] >= size) return i; // first that fits, stop early
return -1;
}
int bestFit(const std::vector<int>& h, int size) {
int bi = -1;
for (int i = 0; i < (int)h.size(); ++i) // must scan all of it
if (h[i] >= size && (bi < 0 || h[i] < h[bi])) bi = i;
return bi; // tightest -> tiny remainder
}
int worstFit(const std::vector<int>& h, int size) {
int wi = -1;
for (int i = 0; i < (int)h.size(); ++i)
if (h[i] >= size && (wi < 0 || h[i] > h[wi])) wi = i;
return wi; // largest -> burns big holes
}
std::string run(int (*pick)(const std::vector<int>&, int),
std::vector<int> holes, const std::vector<int>& reqs) {
for (int r : reqs) {
int i = pick(holes, r);
if (i < 0) return "FAILED on " + std::to_string(r);
holes[i] -= r; // the remainder stays a hole
}
return "all placed";
}
int main() {
std::vector<int> holes {
100, 500, 200, 300, 600
}, reqs {
212, 417, 112, 426
};
std::cout << "first: " << run(firstFit, holes, reqs) << '\n'
<< "best: " << run(bestFit, holes, reqs) << '\n'
<< "worst: " << run(worstFit, holes, reqs) << '\n';
}// First / best / worst fit -- the placement decision in isolation.
import java.util.*;
import java.util.function.BiFunction;
class Fits {
static int firstFit(int[] h, int size) {
for (int i = 0; i < h.length; i++)
if (h[i] >= size) return i; // stop at the first match
return -1;
}
static int bestFit(int[] h, int size) {
int bi = -1;
for (int i = 0; i < h.length; i++) // full scan required
if (h[i] >= size && (bi < 0 || h[i] < h[bi])) bi = i;
return bi; // smallest usable remainder
}
static int worstFit(int[] h, int size) {
int wi = -1;
for (int i = 0; i < h.length; i++)
if (h[i] >= size && (wi < 0 || h[i] > h[wi])) wi = i;
return wi; // consumes the big holes
}
static String run(BiFunction<int[],Integer,Integer> pick,
int[] holes, int[] reqs) {
int[] h = holes.clone();
for (int r : reqs) {
int i = pick.apply(h, r);
if (i < 0) return "FAILED on " + r;
h[i] -= r;
}
return "all placed";
}
}Step through it
Running on holes [100, 500, 200, 300, 600] KB requests 212, 417, 112, 426 KB
Read all 13 Steps
- the starting free list — five holes, 1700 KB total Five holes of 100, 500, 200, 300 and 600 KB. Total free memory is 1700 KB. Four requests are coming: 212, 417, 112 and 426 KB, totalling 1167 KB. There is plenty of memory in aggregate — the entire question is whether it stays in usefully-shaped pieces, and that is decided by which hole each request is placed in.
- request 212 KB — each strategy looks at a different hole First fit scans left and stops at hole 2 (500), the first that is big enough — it never even looks at holes 3, 4 and 5. Best fit scans everything and picks hole 4 (300), the tightest fit. Worst fit scans everything and picks hole 5 (600), the largest. Three strategies, three different holes, same request.
- 212 KB placed — look at the remainders, not the placements First fit leaves 288 KB in hole 2. Best fit leaves 88 KB in hole 4 — technically the least waste, and that is exactly the problem: 88 KB is too small for any of the remaining requests, so it is now dead memory. Worst fit leaves 388 KB, which is still useful but has consumed the biggest hole in the list.
- request 417 KB — the lists have already diverged First fit's remaining candidates are 288, 200, 300, 600 — only hole 5 (600) is large enough. Best fit still has its untouched 500, which is the tightest fit that works. Worst fit must use its 500 too, since its 600 is now 388.
- 417 KB placed — best fit is accumulating slivers First fit's 600 becomes 183. Best fit's 500 becomes 83 — a second dead sliver, so best fit now holds 88 and 83 KB of memory that nothing can use. Worst fit's 500 becomes 83 as well. Note that best fit has the most free memory by total, and the least usable free memory.
- request 112 KB — the small request all three can serve First fit takes hole 2 (288), the first big enough. Best fit's tightest fit among 100, 83, 200, 88, 600 is hole 3 (200). Worst fit takes its largest, hole 5 (388). This request is small enough that no strategy struggles — the divergence is in what it leaves behind.
- 112 KB placed — three very different free lists now First fit: 100, 176, 200, 300, 183. Best fit: 100, 83, 88, 88, 600 — four slivers and one big hole. Worst fit: 100, 83, 200, 300, 276. The totals are identical at 959 KB. What differs completely is the largest single hole: 300 for first fit, 600 for best fit, 300 for worst fit.
- request 426 KB — and worst fit fails First fit scans 100, 176, 200, 300, 183 and finds nothing ≥ 426. Worst fit scans 100, 83, 200, 300, 276 and also finds nothing. Best fit, ironically, succeeds — its untouched 600 KB hole is the only one large enough anywhere. Total free memory in every case is 959 KB, more than double the request.
- external fragmentation, precisely defined This is what external fragmentation means as a failure and not a definition: 959 KB free, a 426 KB request, and no single run long enough to hold it. Two of the three strategies fail. Nothing was leaked and nothing was lost — the memory is simply in the wrong shape.
- why best fit survived here, and why it still loses in general Best fit won this particular sequence by accident: it happened to leave one large hole untouched. Its structural behaviour is the four slivers of 83–88 KB it created, which are permanently unusable. Run a longer, more varied request stream and that sliver accumulation is what dominates — which is why simulation studies consistently rank best fit below first fit despite the name.
- what compaction would do Sliding every allocated block down merges all the holes into one contiguous run of 959 KB, and the 426 KB request succeeds under any strategy. The prerequisite is runtime address translation — a base register or a page table — because every relocated block's addresses must remain valid. Without that, compaction is impossible.
- what paging would do instead Paging avoids the problem rather than repairing it. Fix every block at 4 KB and any 107 free frames anywhere in memory satisfy a 426 KB request — there is no such thing as a hole too small when there is only one size of hole. The cost is internal fragmentation in the final page of each allocation, averaging 2 KB. That is the trade every modern OS took.
- the measured verdict Knuth's fifty-percent rule says that under first fit at equilibrium, for every 2N allocated blocks roughly N are lost to holes — about a third of memory unusable. Simulation studies repeatedly rank first fit and next fit ahead of best fit on both utilisation and speed, with worst fit last on both. First fit also wins on time, because it stops at the first match while the other two must scan the entire list. The strategy named 'best' is the one to avoid.