Memory Allocation: First-fit, Best-fit, and Worst-fit

When a program requests memory, and more than one free block is large enough to hold it, something has to decide which block to hand over. That decision is the placement strategy, and it directly shapes how much usable memory is left over afterward.

The setup: a free list

Take a free list with five blocks of sizes 100, 500, 200, 300, 600 (in some unit, say KB), and three requests arriving in order: 212, 417, 112.

The same starting free list and the same three requests are run through all three strategies below, one allocation at a time, so the point where their choices diverge is visible directly.

First-fit

FIRST_FIT(freeList, n)
 
1. PTR = freeList
2. While PTR != NULL
       If PTR->size >= n
           Return PTR
       PTR = PTR->next
3. Return NULL   (no block large enough)

First-fit scans from the start and stops at the first block big enough, without looking any further.

Step 1: request for 212. Scanning A → B → C → D → E in order: A (100) is too small, B (500) is big enough, so the scan stops right there, even though D (300), further down the list, would waste far less space:

B splits into a 212-block now in use and a 288-block still free:

Step 2: request for 417. Scanning again from the start: A (100, too small), B (free) (288, too small), C (200, too small), D (300, too small), E (600, big enough) → E is chosen:

E splits into a 417-block in use and a 183-block free:

Step 3: request for 112. Scanning from the start: A (100, too small), B (free) (288, big enough) → B (free) is chosen this time, since it's now the first eligible block, D (300) and E (free) (183) are never even reached:

Final state after all three requests:

Best-fit

BEST_FIT(freeList, n)
 
1. BEST = NULL
2. PTR = freeList
3. While PTR != NULL
       If PTR->size >= n and (BEST == NULL or PTR->size < BEST->size)
           BEST = PTR
       PTR = PTR->next
4. Return BEST

Best-fit scans the entire list and picks whichever eligible block leaves the smallest leftover space.

Step 1: request for 212. All five blocks are checked. Eligible: B (500), D (300), E (600). The smallest is D (300), leaving only 88 unused, the tightest fit available:

D splits into a 212-block in use and an 88-block free:

Step 2: request for 417. Eligible blocks now: B (500) and E (600); A, C, and D (free) (88) are all too small. The smallest eligible is B (500), leaving 83 unused:

B splits into a 417-block in use and an 83-block free:

Step 3: request for 112. Eligible blocks now: only E (600); D (free) (88) and B (free) (83) are both too small, and there is no smaller eligible block to prefer over E:

Final state after all three requests:

Best-fit has to check every remaining block on every request, it cannot stop early the way first-fit can, since a smaller (but still large enough) block might appear anywhere in the list. Best-fit is always O(n), the full list is scanned regardless of where a fit is found, in exchange for minimizing wasted space on each individual allocation, notice how the two tiny leftovers here (88 and 83) are now too small for almost anything.

Worst-fit

WORST_FIT(freeList, n)
 
1. WORST = NULL
2. PTR = freeList
3. While PTR != NULL
       If PTR->size >= n and (WORST == NULL or PTR->size > WORST->size)
           WORST = PTR
       PTR = PTR->next
4. Return WORST

Worst-fit does the opposite of best-fit: it picks the largest eligible block, on the theory that the leftover fragment will be big enough to still be useful for some future request, rather than shrinking down to a sliver.

Step 1: request for 212. Among the eligible blocks B (500), D (300), E (600), the largest is E (600):

E splits into a 212-block in use and a 388-block free, a much bigger leftover than first-fit or best-fit produced from this same request:

Step 2: request for 417. Eligible blocks now: B (500) only; D (300) and E (free) (388) are both too small for 417. B is chosen since it's the only option:

B splits into a 417-block in use and an 83-block free:

Step 3: request for 112. Eligible blocks now: D (300) and E (free) (388); B (free) (83) is too small. The largest is E (free) (388):

Final state after all three requests:

Like best-fit, worst-fit must check every block on every request, since the largest eligible block could be anywhere in the list. Worst-fit is also O(n), the same full-scan cost as best-fit, trading more wasted space per allocation for larger leftover fragments, D (300) here is still fully intact and usable, unlike the near-unusable 83/88-sized slivers best-fit left behind from the same requests.

Comparing the three

Same free list, same three requests (212, 417, 112), three different outcomes:

Quick recall

• All three strategies search a free list for a block of at least the requested size; they differ only in which eligible block they choose.
• First-fit stops at the first block large enough, so it can finish before scanning the whole list, but may leave more waste behind than necessary.
• Best-fit scans the whole list and picks the smallest sufficient block, minimizing waste on this allocation but often producing many small, less useful fragments over time.
• Worst-fit scans the whole list and picks the largest block, wasting more space now in exchange for a bigger, more reusable leftover fragment.
• If no block in the free list is large enough, all three return NULL (or an equivalent failure signal), the request cannot be satisfied yet.