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