Worst Fit Memory Allocation in OS
Deliberately take the biggest hole, so what is left over is large enough to use. A reasonable theory that measurement does not support.
What Worst Fit in OS Means
Worst fit in OS is best fit inverted: scan the whole free list and allocate from the largest hole available.
The reasoning is deliberate, not perverse. A large hole minus a small request still leaves a large remainder — something genuinely worth having, unlike best fit's slivers.
Like best fit, worst fit has no early exit and costs a full O(n) scan per allocation.
- Search cost: O(n) always
- Leftover: the largest possible
- Casualty: the biggest hole is consumed
Worst Fit in OS — Worked Example
Take holes of 100, 500, 200, 300 and 600 KB and a 212 KB request.
All five holes are examined and the largest that fits is hole 5 (600 KB). It is split, leaving 600 − 212 = 388 KB — comfortably the most usable remainder any of the three strategies produced.
On this single allocation the logic is vindicated. The free list becomes 100, 500, 200, 300, 388 KB.
Now send a 420 KB request. Under first fit the 600 KB hole would still be intact and would serve it. Under worst fit the largest remaining hole is 500 KB — which still fits — but after a few more allocations the large holes are gone entirely, and a large request fails while hundreds of kilobytes sit free in medium-sized pieces.
- Chosen hole: 5 (600 KB)
- Leftover: 388 KB — the most usable of the three
- Hidden cost: the largest hole no longer exists
Why Worst Fit Still Loses
The flaw only shows up across a sequence. Worst fit spends the largest hole on every request, including tiny ones, so the big contiguous runs disappear first.
When a genuinely large request arrives later, the holes that could have served it have already been chipped away. The allocator ends up holding many medium holes and no large one — and the large request fails despite ample total free memory.
Worst fit therefore trades a guaranteed future capability for a marginal present gain, and pays best fit's full-scan cost to do it. In the standard simulations it finishes last on both utilisation and speed, and it is taught mainly as the counterexample that shows locally sensible reasoning failing globally.
- Large requests starve because large holes were spent early
- Full O(n) scan with the poorest measured outcome
- Taught as a counterexample, not used as a policy
Worst fit in OS — a good remainder now, no large hole later
"""Worst fit: allocate from the largest hole, keeping remainders usable."""
def worst_fit(holes, size):
"""Return the index of the largest hole that fits, or -1 if none does."""
worst_index = -1
for i, hole in enumerate(holes):
if hole < size:
continue # not a candidate
if worst_index < 0 or hole > holes[worst_index]:
worst_index = i # larger than anything seen so far
return worst_index
def main():
holes = [100, 500, 200, 300, 600]
for request in (212, 180, 150):
index = worst_fit(holes, request)
holes[index] -= request
print(f"{request} KB -> hole {index + 1}, leaves {holes[index]} KB")
print(f"free list: {holes}, total free {sum(holes)} KB")
big = 420
if worst_fit(holes, big) < 0:
print(f"{big} KB -> FAILS, largest run is only {max(holes)} KB")
if __name__ == "__main__":
main()
// Worst fit: allocate from the largest hole, keeping remainders usable.
#include <algorithm>
#include <iostream>
#include <vector>
// Returns the index of the largest hole that fits, or -1 if none does.
int worstFit(const std::vector<int>& holes, int size) {
int worstIndex = -1;
for (std::size_t i = 0; i < holes.size(); ++i) {
if (holes[i] < size) {
continue; // not a candidate
}
if (worstIndex < 0 || holes[i] > holes[worstIndex]) {
worstIndex = static_cast<int>(i);
}
}
return worstIndex;
}
int main() {
std::vector<int> holes {
100, 500, 200, 300, 600
};
for (int request : {212, 180, 150}) {
const int index = worstFit(holes, request);
holes[index] -= request;
std::cout << request << " KB -> hole " << index + 1
<< ", leaves " << holes[index] << " KB\n";
}
const int big = 420;
if (worstFit(holes, big) < 0) {
std::cout << big << " KB -> FAILS, largest run is only "
<< *std::max_element(holes.begin(), holes.end()) << " KB\n";
}
}// Worst fit: allocate from the largest hole, keeping remainders usable.
import java.util.Arrays;
public class WorstFit {
/** Returns the index of the largest hole that fits, or -1 if none does. */
static int worstFit(int[] holes, int size) {
int worstIndex = -1;
for (int i = 0; i < holes.length; i++) {
if (holes[i] < size) {
continue; // not a candidate
}
if (worstIndex < 0 || holes[i] > holes[worstIndex]) {
worstIndex = i;
}
}
return worstIndex;
}
public static void main(String[] args) {
int[] holes = {100, 500, 200, 300, 600};
for (int request : new int[]{212, 180, 150}) {
int index = worstFit(holes, request);
holes[index] -= request;
System.out.println(request + " KB -> hole " + (index + 1)
+ ", leaves " + holes[index] + " KB");
}
System.out.println("free list: " + Arrays.toString(holes));
int big = 420;
if (worstFit(holes, big) < 0) {
System.out.println(big + " KB -> FAILS, largest run is only "
+ Arrays.stream(holes).max().getAsInt() + " KB");
}
}
}Step through it
Running on free list [100, 500, 200, 300, 600] KB requests 212, 180, 150 KB then 420 KB
Read all 8 Steps
- the free list before anything is allocated The same five holes. Worst fit deliberately takes the largest one each time, so the leftover stays usable.
- request 212 KB — scan for the largest hole All five examined. 600 KB is the largest that fits, so that is the choice.
- allocate hole 5 — a genuinely good remainder 600 - 212 = 388 KB left — the best remainder of any strategy. On this one allocation the reasoning holds.
- request 180 KB — the largest is now hole 2 Next request, 180 KB. The 600 KB hole is gone, so the largest is now 500 KB.
- allocate hole 2, leaving 320 KB 500 - 180 = 320 KB. Two large holes have now been chipped down.
- request 150 KB — the largest is hole 5 at 388 150 KB takes hole 5 again, leaving 238 KB. Total free is still 1158 KB — barely less than we started with.
- now a 420 KB request arrives — and fails Now 420 KB arrives. 1158 KB is free, but the largest run is 320 KB. The request fails.
- the lesson worst fit teaches Every hole that could have served it was spent earlier on requests that would have fitted anywhere.