First fit memory allocation, explained

When a program asks for memory, the system looks through the free gaps and must choose one. First fit makes the quickest choice: it scans from the lowest address and takes the first gap that is big enough.

It stops as soon as it finds one, so it does not spend time comparing the other gaps.

How it works

• Start at the lowest address and look at each free gap in turn.
• Take the first gap that is at least as big as the request.
• Place the block at the start of that gap. Any leftover space stays free as a smaller gap.
• If no gap is big enough, the request fails.

A small example

Free gaps (KB), in address order:  100  500  200  300  600
Requests (KB), one after another: 212  417  112  426

With first fit: 212 goes into the 500 gap, 417 goes into 600, 112 goes into what is left of the 500 gap, and 426 has no gap big enough. Result:

3 requests placed, 1 request fails (426 KB)

The total free memory was enough, but no single gap could hold 426 KB. This is external fragmentation.

What to know about its cost

• It is fast, because the search stops at the first match.
• It tends to use up the low-address end of memory first.
• Freed neighbouring gaps are merged to keep free space in as few pieces as possible.

Where it works well

• Quick to run.
• Simple to build and to understand.

Where it struggles

• Small gaps build up near the start of memory.
• It can fail even when there is enough free memory in total.

Try it yourself

Open the Memory Allocation experiment, build a memory like the one in this post, choose First Fit and allocate the blocks one at a time. Then run the same list with the other strategies and compare.

Open the Memory Allocation experiment