Best fit memory allocation, explained

Best fit looks at every free gap that is big enough and takes the smallest one. The goal is to leave as little unused space as possible after each allocation, so bigger gaps stay available for bigger requests.

The price is a longer search, because it must check all the gaps before deciding.

How it works

• Look at every free gap.
• Among the gaps that are big enough, take the smallest. Ties go to the lower address.
• Place the block at the start of that gap. The leftover stays free.
• 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 best fit: 212 goes into 300, 417 goes into 500, 112 goes into 200, and 426 goes into 600. Result:

All 4 requests placed

On the same list, first fit failed to place the last request.

What to know about its cost

• It searches every gap, so each allocation takes longer.
• It leaves the smallest possible leftover for each request.
• Over time it can leave many tiny gaps that are too small to use.

Where it works well

• Wastes the least space on each request.
• Keeps large gaps for large requests.

Where it struggles

• Slower, since it checks every gap.
• Tends to create very small leftover pieces.

Try it yourself

Open the Memory Allocation experiment, build a memory like the one in this post, choose Best 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