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.

mediumQ164 of 224 in Operating Systems Est. time: 6 minsLast updated: July 2026

Open Code Lab

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

First fit, best fit, and worst fit over a free-block list

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?

2. A downside of best fit is that it tends to?

3. Worst fit allocates from the?

Flash Cards

1 / 4

Memory Allocation Strategies: First Fit, Best Fit, Worst Fit

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Maintain free list

Request arrives

Strategy selects a hole

Split and update free list