Best Fit Memory Allocation in OS
Examine every hole and choose the one that wastes least. It sounds optimal, and in practice it is the strategy that fragments memory fastest.
What Best Fit in OS Means
Best fit in OS allocates from the smallest hole that is still large enough for the request. The allocator scans the entire free list, tracks the tightest candidate seen, and splits that one.
The objective is to waste as little as possible on this particular request — minimise the leftover.
There is no early exit. Even if the first hole is a perfect match, best fit cannot know that without checking every other hole, so each allocation costs a full O(n) scan.
- Search cost: O(n) always, never less
- Leftover: the smallest possible for this request
- Consequence: that leftover is usually unusable
Best Fit in OS — Worked Example
Take holes of 100, 500, 200, 300 and 600 KB and a 212 KB request.
Every hole is examined. 100 is too small. 500 fits, spare 288. 200 is too small. 300 fits, spare 88 — tighter than 288, so it becomes the new best. 600 fits, spare 388 — worse, so it is rejected.
The winner is hole 4 (300 KB), leaving 300 − 212 = 88 KB. Five comparisons were made, against first fit's two.
The final free list is 100, 500, 200, 88, 600 KB. That 88 KB is the smallest possible waste for this request — and that is precisely the problem, because 88 KB will satisfy almost nothing that arrives later.
- Chosen hole: 4 (300 KB)
- Leftover: 88 KB — a sliver
- Comparisons: all 5 holes
Why the Tightest Hole Is the Wrong Target
Minimising waste per request sounds like the right objective. It is the wrong one, because it optimises a single step rather than the sequence of allocations.
An 88 KB sliver satisfies almost no later request. It sits on the free list, is walked over by every subsequent search, and counts toward total free memory while being useless in practice — that is the definition of external fragmentation.
So best fit manufactures fragmentation faster than any other strategy while also paying the highest search cost. The name describes the step it takes, not the outcome it produces.
- Optimises one allocation, not the whole sequence
- Produces the most unusable fragments of the four
- Slowest search, with no memory advantage to show
Best fit in OS — every hole is examined, and the prize is a sliver
"""Best fit: scan every hole and allocate from the tightest that fits."""
def best_fit(holes, size):
"""Return the index of the smallest hole that fits, or -1 if none does."""
best_index = -1
for i, hole in enumerate(holes):
if hole < size:
continue # not a candidate
if best_index < 0 or hole < holes[best_index]:
best_index = i # tighter than anything seen so far
return best_index # no early exit: the whole list is always scanned
def main():
holes = [100, 500, 200, 300, 600]
request = 212
index = best_fit(holes, request)
if index < 0:
print(f"{request} KB -> no hole large enough")
return
holes[index] -= request
print(f"{request} KB -> hole {index + 1}, leaves {holes[index]} KB")
print(f"final free list: {holes}")
if __name__ == "__main__":
main()
// Best fit: scan every hole and allocate from the tightest that fits.
#include <iostream>
#include <vector>
// Returns the index of the smallest hole that fits, or -1 if none does.
int bestFit(const std::vector<int>& holes, int size) {
int bestIndex = -1;
for (std::size_t i = 0; i < holes.size(); ++i) {
if (holes[i] < size) {
continue; // not a candidate
}
if (bestIndex < 0 || holes[i] < holes[bestIndex]) {
bestIndex = static_cast<int>(i);
}
}
return bestIndex; // no early exit: the whole list is always scanned
}
int main() {
std::vector<int> holes {
100, 500, 200, 300, 600
};
const int request = 212;
const int index = bestFit(holes, request);
if (index < 0) {
std::cout << request << " KB -> no hole large enough\n";
return 0;
}
holes[index] -= request;
std::cout << request << " KB -> hole " << index + 1
<< ", leaves " << holes[index] << " KB\n";
}// Best fit: scan every hole and allocate from the tightest that fits.
import java.util.Arrays;
public class BestFit {
/** Returns the index of the smallest hole that fits, or -1 if none does. */
static int bestFit(int[] holes, int size) {
int bestIndex = -1;
for (int i = 0; i < holes.length; i++) {
if (holes[i] < size) {
continue; // not a candidate
}
if (bestIndex < 0 || holes[i] < holes[bestIndex]) {
bestIndex = i;
}
}
return bestIndex; // no early exit: the whole list is always scanned
}
public static void main(String[] args) {
int[] holes = {100, 500, 200, 300, 600};
int request = 212;
int index = bestFit(holes, request);
if (index < 0) {
System.out.println(request + " KB -> no hole large enough");
return;
}
holes[index] -= request;
System.out.println(request + " KB -> hole " + (index + 1)
+ ", leaves " + holes[index] + " KB");
System.out.println("final free list: " + Arrays.toString(holes));
}
}Step through it
Running on free list [100, 500, 200, 300, 600] KB request 212 KB
Read all 8 Steps
- the free list before anything is allocated The same five holes. Best fit must examine every one before deciding, because it cannot know which is tightest until it has seen them all.
- hole 1 — 100 KB, too small 100 < 212 — not a candidate at all.
- hole 2 — 500 KB fits, spare 288 500 fits, sparing 288. Recorded as best so far, but not taken: a tighter hole may still be ahead.
- hole 3 — 200 KB, too small 200 < 212. Twelve short. The best is still hole 2.
- hole 4 — 300 KB fits, spare 88 — new best 300 fits, sparing only 88 — tighter than 288, so this becomes the new best.
- hole 5 — 600 KB fits, spare 388 — worse 600 fits but spares 388, far looser. Rejected. Five holes examined, against first fit's two.
- allocate hole 4 and split it Hole 4 wins: 212 allocated, 88 KB left. The smallest possible waste for this request.
- why that 88 KB is the problem And that 88 KB is the problem — too small for almost anything later, so it sits on the list forever. This is how best fit manufactures fragmentation.