Worst fit memory allocation, explained

Worst fit does the opposite of best fit. It checks every free gap and takes the largest one. The idea is that cutting a request out of a big gap leaves a big leftover, which is more likely to be useful than a tiny sliver.

In practice this idea does not always work out, which makes it a good example to compare against the others.

How it works

• Look at every free gap.
• Take the largest one. Ties go to the lower address.
• Place the block at the start of that gap. The leftover stays free.
• If even the largest gap is too small, 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 worst fit: 212 goes into 600, 417 goes into 500, 112 goes into what is left of the 600 gap, and 426 has no gap big enough. Result:

3 requests placed, 1 request fails (426 KB)

The big gaps were used up early, so there was nothing large enough left for the last request.

What to know about its cost

• It checks every gap, like best fit.
• It quickly uses up the largest gaps.
• It rarely performs better than first fit or best fit.

Where it works well

• Leftover pieces tend to be large.
• Useful for comparing strategies.

Where it struggles

• Large gaps disappear quickly.
• Large requests are more likely to fail later.

Try it yourself

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