[SOLVED] CS代考计算机代写 Carnegie Mellon

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