[SOLVED] CS Carnegie Mellon

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 lengthlinks 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