First Fit vs Best Fit vs Worst Fit Memory Allocation
Compare first fit, best fit, and worst fit memory allocation — speed, fragmentation, and trade-offs — with an OS interview question answered.
Expected Interview Answer
First fit, best fit, and worst fit are contiguous-memory allocation strategies that scan a free-block list differently: first fit picks the first hole large enough, best fit picks the smallest hole that still fits, and worst fit picks the largest hole available, each trading allocation speed against how quickly usable free space fragments.
When a process requests memory, the allocator walks a list of free holes left by previously freed blocks. First fit stops at the very first hole big enough to satisfy the request, which is fast because it does minimal scanning, but it tends to fragment the front of memory with small unusable slivers over time. Best fit scans the entire free list to find the smallest hole that still satisfies the request, minimizing wasted space per allocation, but this leaves behind tiny leftover fragments that are rarely large enough to be reused, and the full scan makes it the slowest option. Worst fit deliberately picks the largest available hole, reasoning that the leftover remainder will be large enough to still be useful for a future allocation, but in practice it quickly consumes the biggest blocks and leaves the system without large contiguous holes when they are later needed. None of the three eliminate external fragmentation outright; they only change how quickly it appears and how badly it clusters.
- Explains the core allocation-speed vs fragmentation trade-off
- First fit: fastest, moderate fragmentation at the low end of memory
- Best fit: least wasted space per hole, but many unusable slivers
- Worst fit: keeps leftover chunks large, but exhausts big holes fast
AI Mentor Explanation
Allocating a seat block to a touring fan group is like these three strategies: first fit assigns the very first stand section with enough empty seats, without checking if a tighter section exists elsewhere. Best fit instead checks every stand and picks the section whose empty-seat count is closest to the group size, leaving the smallest possible gap. Worst fit deliberately assigns the largest open stand, betting the big leftover gap will seat another group later, but that quickly uses up all the spacious stands.
Step-by-Step Explanation
Step 1
Maintain free list
The allocator tracks a list of free memory holes with their start address and size.
Step 2
First fit
Scan from the start of the list and allocate the first hole that is large enough; stop immediately.
Step 3
Best fit
Scan the entire list, tracking the smallest hole that still satisfies the request, and allocate that one.
Step 4
Worst fit
Scan the entire list, tracking the largest hole, and allocate that one, leaving the biggest possible remainder.
What Interviewer Expects
- A correct definition of all three allocation strategies
- The speed vs fragmentation trade-off between them
- Recognition that all three still suffer external fragmentation
- Awareness that best fit is not always the best real-world choice
Common Mistakes
- Assuming best fit always minimizes overall fragmentation
- Confusing external fragmentation with internal fragmentation
- Thinking worst fit is strictly worse in every metric
- Forgetting that first fit requires no full-list scan, unlike the other two
Best Answer (HR Friendly)
“These are three ways an operating system decides where to place a new chunk of memory among a list of free holes. First fit just grabs the first hole big enough, best fit hunts for the tightest possible fit to waste less space, and worst fit deliberately grabs the biggest hole so the leftover stays usable. Each has a different trade-off between how fast the decision is made and how quickly memory ends up fragmented.”
Code Example
struct hole {
int start;
int size;
};
int first_fit(struct hole *holes, int n, int req) {
for (int i = 0; i < n; i++)
if (holes[i].size >= req) return i;
return -1;
}
int best_fit(struct hole *holes, int n, int req) {
int best = -1;
for (int i = 0; i < n; i++) {
if (holes[i].size < req) continue;
if (best == -1 || holes[i].size < holes[best].size) best = i;
}
return best;
}
int worst_fit(struct hole *holes, int n, int req) {
int worst = -1;
for (int i = 0; i < n; i++) {
if (holes[i].size < req) continue;
if (worst == -1 || holes[i].size > holes[worst].size) worst = i;
}
return worst;
}Follow-up Questions
- Which of the three strategies is fastest to compute and why?
- Why does best fit tend to leave many tiny unusable holes?
- How does compaction relate to fixing fragmentation from these strategies?
- How do paging and segmentation avoid the fragmentation these strategies cause?
MCQ Practice
1. Which allocation strategy stops at the very first hole large enough for the request?
First fit scans from the start of the free list and immediately allocates the first hole that satisfies the request.
2. Which strategy requires scanning the entire free list before allocating, in general?
Both best fit and worst fit must examine every hole to find the smallest or largest one respectively, unless the list is sorted.
3. A key downside of best fit in practice is?
Best fit minimizes leftover space per allocation, which paradoxically produces many slivers too small to satisfy future requests, and its full scan is costly.
Flash Cards
What does first fit do? — Allocates the first free hole encountered that is large enough for the request.
What does best fit do? — Scans all holes and allocates the smallest one that still satisfies the request.
What does worst fit do? — Scans all holes and allocates the largest one available.
Do all three avoid external fragmentation? — No — all three still suffer external fragmentation over time, just at different rates and patterns.