Memory Allocators

This is only a brief overview and is not intended to include all the details of each algorithm and the variations of each algorithm, nor all possible memory allocator algorithms.

Sequential fit

Sequential fit algorithms rely on a linked-list or "free list" and sequentially search this list to find the free areas of memory of specific size needed. As the name depicts, first-fit searches the list and finds the first free block, that is as big as the request or larger, and allocates this memory. If the block is larger than the requested memory the allocator splits off the remaining piece. This "splitting" is determined by the algorithm, for example, if the client requests 8 bytes and the allocator finds a block of 16 bytes, the other 8 bytes are put back on the free list. However, if the client requests 10 bytes, depending on the allocator and its implementation, it may not "split" and the remaining 6 bytes of memory is wasted, because it is considered allocated. Best-fit also searches the free list, but instead looks for the smallest available block of memory. In essence, looking for the "best" fit. Next-fit is similar, but uses a roving pointer. The pointer marks where the previous request was made and the next request is initiated at that point.

Sequential fit algorithms can have variations and optimizations to the above schemes. For example, the structures can be doubly linked lists or trees. Additionally, the question of how the allocator deals with the memory after it is freed is also an issue. One approach in first fit is to add the freed memory to the beginning of the list or to insert the block in address order.

Segregated free lists

Segregated free list algorithms provide an array of free lists. Where each array contains blocks of the same size or class size (i.e. power of two).

As with sequential fit algorithms there are variations and optimizations to these algorithms. These algorithms may use sequential fit algorithms to search for free blocks. Two types of segregated free list algorithms are segregated storage and segregated fit. There is an important difference between segregated storage and segregated fit. When segregated storage requests memory it searches for free blocks of the requested size. If there are no blocks of the requested size it simply says give me more memory and it creates an array of blocks that size. In comparison, segregated fit will also respond to the memory request and look for free blocks of the appropriate size; however, if none are found it does not request more memory, it simply finds an array of free lists that are larger and splits these blocks. Consequently, a larger block will be split to fill a smaller size request. Additionally, segregated storage does not merge or coalesce free blocks and segregated fit does do coalescing.

Buddy system

Buddy system algorithms are similar to segregated free list algorithms. The buddy algorithm maintains free lists of different sized blocks. When a request for memory is made these free lists are searched. If the appropriate size is not found a larger block is split (variations of this algorithm determine how the block is actually split, for example, in a binary buddy system the block is split by powers of two). It will continue this splitting, and the "buddy" or other half is added to the free list, until the requested size is found. When memory is freed it looks for its buddy, or the block it split from, to regain its original size. For example, if 10 bytes are requested the allocator searches the free list. Say the only available block is 32 bytes. This block splits into two blocks of 16 bytes. One block of 16 bytes is allocated and the other block is put on the free list. When it frees this memory it then looks to the free list for its buddy and coalescing takes place. Buddy systems variations include the binary buddy system, the Fibonacci buddy system and the weighted buddy system.

Sources I used and a more thorough discussion of memory allocation can be found at:

Dynamic Storage Allocation: A Survey and Critical Review
Dynamic Storage Allocation: A Survey and Critical Review Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles