Memory Allocation Strategies: First Fit, Best Fit, Worst Fit
Memory allocation strategies explained — first fit, best fit, and worst fit trade-offs and fragmentation — OS interview questions.
Expected Interview Answer
Memory allocation strategies are the algorithms an OS uses to pick which free block of memory to give a new process from a list of available holes, the three classic ones being first fit (take the first hole big enough), best fit (take the smallest hole big enough), and worst fit (take the largest hole available).
First fit scans the free list from the beginning and allocates the first hole large enough to satisfy the request, which is fast because it can stop scanning early, but it tends to leave small unusable slivers near the start of memory over time. Best fit scans the entire free list to find the smallest hole that still fits the request, minimizing wasted space per allocation, but this actually tends to produce many tiny, practically useless leftover fragments and is slower since it must examine every hole to guarantee the smallest fit. Worst fit deliberately takes the largest available hole, on the theory that the leftover fragment after allocation will be large enough to still be useful for a future request, but in practice it quickly consumes the large holes that bigger future requests would need, and it is also slower like best fit. All three strategies suffer from external fragmentation to varying degrees, where free memory exists in total but is scattered into pieces too small individually to satisfy new requests, which is why real systems periodically compact memory or use non-contiguous allocation schemes like paging to sidestep the problem entirely.
- First fit: fastest to allocate, simple to implement
- Best fit: minimizes wasted space on any single allocation
- Worst fit: aims to leave a still-usable leftover fragment
- Understanding all three explains external fragmentation and motivates paging
AI Mentor Explanation
First fit is like a groundskeeper assigning the very first open net that is big enough for a squad’s practice session, without checking if a better-sized net exists further down the row. Best fit is like instead walking the entire row of nets to find the one closest in size to the squad, minimizing wasted space but leaving oddly-shaped tiny gaps between nets over the season. Worst fit is like deliberately assigning the biggest open net available, hoping the leftover space is still useful later, but this quickly uses up the large nets that a bigger squad will need next.
Step-by-Step Explanation
Step 1
Maintain free list
The OS tracks all free memory holes (blocks) not currently allocated to any process.
Step 2
Request arrives
A process requests a block of memory of a specific size.
Step 3
Strategy selects a hole
First fit picks the first sufficiently large hole scanned; best fit picks the smallest sufficient hole; worst fit picks the largest hole.
Step 4
Split and update free list
The chosen hole is split into an allocated portion and a leftover free portion (if any), and the free list is updated.
What Interviewer Expects
- Correct definitions of first fit, best fit, and worst fit
- Trade-offs: allocation speed vs fragmentation behavior for each
- Understanding that best fit tends to create many tiny unusable fragments
- Connection to external fragmentation and why paging avoids it
Common Mistakes
- Assuming best fit is always the best strategy because of its name
- Confusing external fragmentation (contiguous allocation) with internal fragmentation (fixed-size allocation)
- Thinking worst fit is a joke rather than an intentional strategy
- Not knowing paging sidesteps this whole class of problems
Best Answer (HR Friendly)
“These are strategies for picking which free chunk of memory to hand a new process: first fit grabs the first chunk big enough and is fast, best fit searches for the tightest-fitting chunk to waste the least space but ends up creating lots of tiny useless leftovers, and worst fit grabs the biggest chunk hoping the leftover stays useful, though it burns through large chunks quickly. All three deal with the same underlying problem of fragmented free memory, which is part of why modern systems use paging instead of contiguous allocation.”
Code Example
struct block { unsigned size; unsigned start; int free; struct block *next; };
struct block *first_fit(struct block *list, unsigned size) {
for (struct block *b = list; b; b = b->next)
if (b->free && b->size >= size) return b; /* stop at first match */
return NULL;
}
struct block *best_fit(struct block *list, unsigned size) {
struct block *best = NULL;
for (struct block *b = list; b; b = b->next)
if (b->free && b->size >= size)
if (!best || b->size < best->size) best = b; /* smallest sufficient */
return best;
}
struct block *worst_fit(struct block *list, unsigned size) {
struct block *worst = NULL;
for (struct block *b = list; b; b = b->next)
if (b->free && b->size >= size)
if (!worst || b->size > worst->size) worst = b; /* largest available */
return worst;
}Follow-up Questions
- Why does best fit tend to create more small unusable fragments than first fit?
- What is external fragmentation and how does compaction address it?
- How does paging avoid the need for these allocation strategies entirely?
- Which strategy would you pick for a system with mostly uniform request sizes, and why?
MCQ Practice
1. Which strategy scans the free list and stops at the first hole large enough?
First fit allocates the first hole encountered that is large enough, stopping the scan early for speed.
2. A downside of best fit is that it tends to?
Because best fit picks the tightest-fitting hole, the leftover remainder is often too small to be useful for future requests.
3. Worst fit allocates from the?
Worst fit deliberately chooses the largest hole, aiming to leave a leftover fragment large enough to still be useful.
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? — Allocates the smallest free hole that is still large enough, minimizing wasted space per allocation.
What does worst fit do? — Allocates the largest available free hole, hoping the leftover remains useful.
What problem do all three strategies share? — External fragmentation — free memory exists but is scattered into pieces too small individually to satisfy requests.