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

Carnegie Mellon
Keeping Track of Free Blocks
 Method 1: Implicit free list using length—links all blocks
5
4
6
2
 Method 2: Explicit free 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
Explicit Free Lists
Allocated (as before) Free
Size
a
Payload and padding
Size
a
Size
a
Next
Prev
Size
a
 Maintain list(s) of free blocks, not all blocks  The “next” free block could be anywhere
 So we need to store forward/back pointers, not just sizes  Still need boundary tags for coalescing
 Luckily we track only free blocks, so we can use payload area
2

Carnegie Mellon
Explicit Free Lists  Logically:
A
B
C
 Physically: blocks can be in any order
Forward (next) links
AB
4
4
4
4
6
6
4
4
4
4
C
Back (prev) links
3

Carnegie Mellon
Allocating From Explicit Free Lists
conceptual graphic
Before
After
(with splitting)
= malloc(…)
4

Carnegie Mellon
Freeing With Explicit Free Lists
 Insertion policy: Where in the free list do you put a newly freed block?
 LIFO (last-in-first-out) policy
 Insert freed block at the beginning of the free list
 Pro: simple and constant time
 Con: studies suggest fragmentation is worse than address ordered
 Address-ordered policy

 
Insert freed blocks so that free list blocks are always in address
order:
addr(prev) < addr(curr) < addr(next)Con: requires searchPro: studies suggest fragmentation is lower than LIFO5 Carnegie MellonExplicit List Summary Comparison to implicit list: Allocate is linear time in number of free blocks instead of all blocks Much faster when most of the memory is full Slightly more complicated allocate and free since needs to splice blocksin and out of the list Some extra space for the links (2 extra words needed for each block) Does this increase internal fragmentation? Most common use of linked lists is in conjunction withsegregated free lists Keep multiple linked lists of different size classes, or possibly for different types of objects6