6

I'm reading Modern Operating Systems by Andrew Tanenbaum, and he writes that best fit is a widely used memory allocation algorithm. He also writes that it's slower than first fit/next fit since it have to search the entire list of allocated memory. And that it tends to waste more memory since it leaves behind a lot of small useless gaps in memory.

Why is it then widely used? Is it some obvious advantage i have overlooked?

4 Answers 4

6

First, it's is not that widely used (like all sequential fits), except, perhaps, in homeworks ;). In my opinion, the widely used strategy is segregated fits (which can very closely approximate best fit).

Second, best fit strategy can be implemented by using a tree of free lists of various sizes

Third, it's considered one of the best policies with regard to memory fragmentation

See

Dynamic Storage Allocation: A Survey and Critical Review

The Memory Fragmentation Problem: Solved?

for information about memory management, not Tannenbaum.

1

I think it's a mischaracterisation to say that it wastes more memory than first fit. Best fit maximizes available space compared to first fit, particularly when it comes to conserving space available for large allocations. This blog post gives a good example.

1

Space efficiency and versatility is really the answer. Large blocks can fit unknown future needs better than small blocks, so a best-fit algorithm tries to use the smallest blocks first.

First-fit and next-fit algorithms (that can also cut up blocks) may end up using pieces of the larger block first, which increases the risk that a large malloc() will fail. This is essentially harm from large blocks of external fragmentation.

A best-fit algorithm will often find fits that are only a few bytes larger, leading to fragmentation that is only a few bytes, while also saving the large blocks for when they're needed. Also, leaving the large blocks untouched as long as possible helps cache locality and minimizes the load on the MMU, minimizing costly page faults and and saving memory pages for other programs.

A good best-fit algorithm will properly maintain its speed even when it's managing a large number of small fragments, by increasing internal fragmentation (which is hard to reclaim) and/or by using good lookup tables and search trees.

First-fit and next-fit still also face their own searching problems. Without good size indexing in these algorithms, they still have to spend time searching through blocks for one that fits. Since their "standards are lower," they may find a fit faster using a straightforward search, but as soon as you add intelligent indexing, the speeds between all algorithms becomes much closer.

The one I've been using and tweaking for the last 6 years can find the best fit block in O(1) time for >90% of all allocs. It utilizes a handful of strategies to jump straight to the right block, or start very close so searching is minimized. It has, on more than one occasion, replaced existing block-pool or first-fit algorithms due to it's performance and ability to pack allocations more efficiently.

2
  • Anywhere I could check out your algorithm? Curious to learn more. Jul 31, 2021 at 21:42
  • @JosephGarvin No, it is owned by my employer. There is a table pointing to blocks of the most common alloc sizes (ie. every 4b up to 256b, and every power of 2 after that), and blocks are a singly linked list sorted by size. So use the table to jump to a close size, then walk the list to get the best size. Excess bytes are trimmed and reinserted. Upon free, adjacent free blocks are coalesced.
    – Kenzi
    Aug 2, 2021 at 13:53
0

Best fit is not the best allocation strategy, but it is better than first fit and next fit. The reason is because it suffers from less fragmentation problems than the latter two.

Consider a micro heap of 64 bytes. First we fill it by allocating one 32 and two 16 byte blocks in that order. Then we free all blocks. There are now three free blocks in the heap, one 32 byte and two 16 byte ones.

Using first fit, we allocate one 16 byte block. We do it using the 32 byte block (because it is first in the heap!) and the remainder 16 bytes of that block is split into a new free block. So there are one 16 byte allocated block at the beginning of the heap and then three free 16 bytes block.

What happens if we now wants to allocate a 32 byte block? We can't! There are still 48 bytes free in the heap, but fragmentation has screwed us over.

What would have happened if we had used best fit? When we were searching for a free block to use for our 16 byte allocation, we would have skipped over the 32 byte block at the beginning of the heap and instead picked the 16 byte block after it. That would have preserved the 32 byte block for larger allocations.

I suggest you draw it on paper, that makes it very easy to see what goes on with the heap during allocation and freeing.

4
  • Your analysis does not take block coalescing into account !
    – Arnaud
    Oct 13, 2019 at 9:27
  • @Arnaud Block coalescing requires blocks to be adjacent in memory which can't be assumed. Consider the situation when the three blocks are noncontiguous. Oct 13, 2019 at 11:40
  • Do you mean your micro heap of 64 bytes is not made of contiguous memory ? If it is then you will be able to coalesce your three chunks into one.
    – Arnaud
    Oct 14, 2019 at 18:55
  • @Arnaud correct and that would make coalescing impossible. But coalescing isn't the point of the example. You might as well consider a large contiguous heap with only 64 bytes free in three noncontiguous blocks. You get the same situation. Oct 15, 2019 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.