Consider the following heap (figure) in which blank regions are not in use and…

Concept

A contiguous allocator keeps a free list of holes. First fit scans that list in order of increasing address and takes the first hole whose size is at least the requested size. Best fit examines every hole and takes the smallest hole whose size is at least the requested size. Under either rule the chosen hole is split: the block is placed at its start and the leftover stays free. Nothing is moved or merged between requests, so a request can be served only by one hole that is big enough on its own.

Best fit minimises the leftover at each individual step, but that locally greedy choice can consume a medium hole that a later request needs, and it scatters free space into slivers. Whether a whole request sequence completes therefore depends on the full trace, not on any single step.

Step 1 — read the heap

Blank means not in use, that is, available for allocation. So the allocator starts with a free list of exactly two holes, 150 and 350, totalling 500 units, while the four requests 300 + 25 + 125 + 50 also total 500 units.

Step 2 — trace first fit

1. Request 300 — the holes are 150 and 350; the first one big enough is 350. Place the block there; 50 is left over. Free list: 150, 50.

2. Request 25 — the first hole big enough is 150. Place the block there; 125 is left over. Free list: 125, 50.

3. Request 125 — the first hole big enough is 125, an exact fit. Free list: 50.

4. Request 50 — the remaining hole of 50 is an exact fit. Free list: empty.

All four blocks are placed and the heap ends with no free space left over.

Step 3 — trace best fit

1. Request 300 — only 350 is big enough, so it is also the smallest hole that qualifies. Place the block there; 50 is left over. Free list: 150, 50.

2. Request 25 — both 150 and 50 are big enough; the smaller is 50. Place the block there; 25 is left over. Free list: 150, 25.

3. Request 125 — now only 150 is big enough. Place the block there; 25 is left over. Free list: 25, 25.

4. Request 50 — 50 units of free space remain, but they sit in two separate holes of 25 at different addresses, and neither is big enough on its own. The block cannot be placed.

Best fit stops at the last request.

Cross-check

• Free space and requested space are both exactly 500 units, so a rule can finish only if it strands nothing; a single wasted unit is fatal.

• The two rules first diverge at the request for 25. Taking the 150 hole leaves 125, which exactly matches the next request; taking the 50 remainder instead leaves two slivers of 25 that no later request can use.

• Merging those two slivers of 25 would rescue the second trace, but they are not adjacent — an allocated 300 block and an allocated 25 block lie between them — so no coalescing is possible.

So on this heap the sequence 300, 25, 125, 50 goes through under first fit but not under best fit.