[SOLVED] CS Carnegie Mellon

Carnegie Mellon
Keeping Track of Free Blocks
Method 1: Implicit free list using lengthlinks 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