This chapter discuss the management of free spaces. In particular, the algorithms to allocate spaces.
There’s a data structure called free list to track all the free spaces which contains references to all of the free chunks of space in the managed region of memory.
Best Fit The best fit: 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; By returning a block that is close to what the user asks, 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 best fit; find the largest chunk and return the requested amount; keep the remaining (large) chunk on the free list. 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.
Basic Idea: if a particular application has one (or a few) popular-sized request that it makes, keep a separate list just to manage object of that size. All other requests are forwarded to a more general memory allocator.
The binary buddy allocator is good for coalescing.
In such system, free memory is thought of as one big space of size $2^N$. When a request for memory is made, the search for free space recursively divides free space by two until a block that is big enough to accommodate the request is found.
When a block is freed, the the allocator checks whether the “buddy”(the block of the same size) of the block is free. If so, it coalesces those two blocks. And if the newly-coalesced block’s buddy is free, it will coalesce again. This recursive coalescing process continues up the tree, either restoring the entire free space or stopping when a buddy is found to be in use.