Carnegie Mellon
Implementation Issues
How do we know how much memory to free given just a pointer?
How do we keep track of the free blocks?
What do we do with the extra space when allocating a
structure that is smaller than the free block it is placed in?
How do we pick a block to use for allocation — many might fit?
How do we reinsert freed block?
1
Carnegie Mellon
Knowing How Much to Free
Standard method
Keep the length of a block in the word preceding the block.
This word is often called the header field or header Requires an extra word for every allocated block
p0 = malloc(4)
free(p0)
p0
block size data
5
2
Carnegie Mellon
Keeping Track of Free Blocks
Method 1: Implicit list using length—links all blocks
5
4
6
2
Method 2: Explicit list among the free blocks using pointers
Method 3: Segregated free list
Different free lists for different size classes
Method 4: Blocks sorted by size
Can use a balanced tree (e.g. Red-Black tree) with pointers within each free block, and the length used as a key
5
4
6
2
3