Now that we have some machinery under our belt, let’s go over some basic strategies for managing free space. These approaches are mostly based on pretty simple policies that you could think up yourself; try it before reading and see if you come up with all of the alternatives (or maybe some new ones!).
The ideal allocator is both fast and minimizes fragmentation. Unfortunately, because the stream of allocation and free requests can be arbitrary (after all, they are determined by the programmer), any particular strategy can do quite badly given the wrong set of inputs. Thus, we will not describe a “best” approach, but rather talk about some basics and discuss their pros and cons.
Best fit
The best fit strategy is quite simple: first, search through the free list and find chunks of free memory that are as big or bigger than the requested size. Then, return the one that is the smallest in that group of candidates; this is the so-called best-fit chunk (it could be called the smallest fit too). One pass through the free list is enough to find the correct block to return.
The intuition behind the best fit is simple: by returning a block that is close to what the user asks, the best fit tries to reduce wasted space. However, there is a cost. Naive implementations pay a heavy performance penalty when performing an exhaustive search for the correct free block.
Worst fit
The worst fit approach is the opposite of the best fit. Find the largest chunk and return the requested amount, and keep the remaining (large) chunk on the free list. Worst fit tries to thus leave big chunks free instead of lots of small chunks that can arise from a best-fit approach. Once again, however, a full search of free space is required, and thus this approach can be costly. Worse, most studies show that it performs badly, leading to excess fragmentation while still having high overheads.
First fit
The first fit method simply finds the first block that is big enough and returns the requested amount to the user. As before, the remaining free space is kept free for subsequent requests.
First fit has the advantage of speed — no exhaustive search of all the free spaces are necessary — but sometimes pollutes the beginning of the free list with small objects. Thus, how the allocator manages the free list’s order becomes an issue. One approach is to use address-based ordering; by keeping the list ordered by the address of the free space, coalescing becomes easier, and fragmentation tends to be reduced.
Next fit
Instead of always beginning the first-fit search at the beginning of the list, the next fit algorithm keeps an extra pointer to the location within the list where one was looking last. The idea is to spread the searches for free space throughout the list more uniformly, thus avoiding splintering of the beginning of the list. The performance of such an approach is quite similar to the first fit, as an exhaustive search is once again avoided.
Examples
Here are a few examples of the above strategies. Envision a free list with three elements on it, of sizes 10, 30, and 20 (we’ll ignore headers and other details here, instead just focusing on how strategies operate):
Assume an allocation request of size 15. A best-fit approach would search the entire list and find that 20 was the best fit, as it is the smallest free space that can accommodate the request. The resulting free list:
As happens in this example, and often happens with a best-fit approach, a small free chunk is now leftover. A worst-fit approach is similar but instead finds the largest chunk, in this example 30. The resulting list:
The first-fit strategy, in this example, does the same thing as worst-fit, also finding the first free block that can satisfy the request. The difference is in the search cost; both best-fit and worst-fit look through the entire list; first-fit only examines free chunks until it finds one that fits, thus reducing search cost.
These examples just scratch the surface of allocation policies. More detailed analysis with real workloads and more complex allocator behaviors (e.g., coalescing) are required for a deeper understanding. Perhaps something for an exercise section, you say?
Get hands-on with 1400+ tech skills courses.