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
5
4
6
2
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
1
Carnegie Mellon
Segregated List (Seglist) Allocators Each size class of blocks has its own free list
1-2 3 4
5-8 9-inf
Often have separate classes for each small size
For larger sizes: One class for each two-power size
2
Carnegie Mellon
Seglist Allocator
Given an array of free lists, each one for some size class
To allocate a block of size n:
Search appropriate free list for block of size m > n If an appropriate block is found:
Split block and place fragment on appropriate list (optional) If no block is found, try next larger class
Repeat until block is found
If no block is found:
Request additional heap memory from OS (using sbrk()) Allocate block of n bytes from this new memory
Place remainder as a single free block in largest size class.
3
Carnegie Mellon
Seglist Allocator (cont.) To free a block:
Coalesce and place on appropriate list (optional)
Advantages of seglist allocators Higher throughput
log time for power-of-two size classes Better memory utilization
First-fit search of segregated free list approximates a best-fit search of entire heap.
Extreme case: Giving each block its own size class is equivalent to best-fit.
4