Malloc Allocation Schemes

Question

Yes, I am taking a Computer systems course. I had a few questions about the various allocation schemes to implement malloc. For explicit lists, if I implement malloc using a LIFO-like stack, what exactly is the purpose of having pointers to previous freed memory? Like why do you need doubly-linked lists? Wouldn't singly linked lists work just as well?

Malloc lecture. I found this link online, you can look at slide 7 to see what I'm talking about.

When looking at a segregated list allocation scheme, these lists are uni-directional right? And also, what exactly is the coalescing mechanism? Like for example, if 4 words are freed, would you first try and join it when the free space around you before inserting it back into the respective segregated linked list? Or would you simply insert the 4 word block in the '4 word' section of the respective segregated linked list?

Thank you.

Answer 1

Since a freed block always has room for two pointers, why not doubly-link the list? It simplifies the coalescing code so it doesn't have to maintain a trailing pointer while traversing the list. It also allows traversing the list in either direction in case there is a hint for which end of the list might be closer to begin the search. One obscure system I once looked at kept a pointer in the "middle", where the last activity occurred.

When freeing a block. There are only four possible cases:

• The free block is adjacent after a free block.
• The free block is adjacent before a free block.
• The free block is between and adjacent to both free blocks before and after it.
• The free block is not adjacent to any free block.

The purposes of coalescing adjacent free blocks are:

• to reduce the length of the linked list
• to accurately reflect the size of a free block without burdening the allocator to look ahead to see if two blocks are adjacent

Sorting a free block into a specific-length freelist often has benefits, but in most practical implementations, coalescing is a priority so that an alloc() request for a different size block isn't inappropriately denied when there are many differently-sized free blocks.