Memory Allocation II CSE 351 Autumn 2016
Memory Allocation II
http://xkcd.com/1909/
CMPT 295
L23: Memory Allocation II
Implicit Free List Example
16-byte alignment for payload
May require initial padding (internal fragmentation)
Note size: padding is considered part of previous block
Special one-word marker (0|1) marks end of list
Zero size is distinguishable from all other blocks
2
16|0
32|1
64|0
32|1
0|1
Free word
Allocated word
Allocated word
unused
Start of heap
16 bytes = 2 word alignment
Each block begins with header (size in bytes and allocated bit)
Sequence of blocks in heap (size|allocated):
16|0, 32|1, 64|0, 32|1
CMPT 295
L23: Memory Allocation II
2
Implicit List: Finding a Free Block
First fit
Search list from beginning, choose first free block that fits:
Can take time linear in total number of blocks
In practice can cause “splinters” at beginning of list
3
p = heap_start;
while ((p < end) && // not past end
((*p & 1) || // already allocated
(*p <= len))) { // too small
p = p + (*p & -2); // go to next block (UNSCALED +)
} // p points to selected block or end
(*p) gets the block header
(*p & 1) extracts the allocated bit
(*p & -2) extracts the size
16|0
32|1
64|0
32|1
0|1
Free word
Allocated word
Allocated word
unused
p = heap_start
CMPT 295
L23: Memory Allocation II
Why doesn’t “*p <= len” mask off the allocated bit too? Because this is the second condition in the || test, which means that the first condition (*p & 1) must have already been false, so we know that the allocated bit can’t be set and we don’t have to bother masking it off.
Tends to concentrate small blocks at front of heap.
Implicit List: Finding a Free Block
Next fit
Like first-fit, but search list starting where previous search finished
Should often be faster than first-fit: avoids re-scanning unhelpful blocks
Some research suggests that fragmentation is worse
Best fit
Search the list, choose the best free block: large enough AND with fewest bytes left over
Keeps fragments small—usually helps fragmentation
Usually worse throughput
4
CMPT 295
L23: Memory Allocation II
Polling Question
Which allocation strategy and requests
remove external fragmentation in this
Heap? B3 was the last fulfilled request.
5
Best-fit:
malloc(50), malloc(50)
(A)
First-fit:
malloc(50), malloc(30)
(B)
Next-fit:
malloc(30), malloc(50)
(C)
Next-fit:
malloc(50), malloc(30)
(D)
B1
B3
B2
10
10
50
50
50
30
Start of heap
payload
size
CMPT 295
L23: Memory Allocation II
5
Implicit List: Allocating in a Free Block
Allocating in a free block: splitting
Since allocated space might be smaller than free space, we might want to split the block
6
void split(ptr b, int bytes) { // bytes = desired block size
int newsize = ((bytes+15) >> 4) << 4; // round up to multiple of 16
int oldsize = *b; // why not mask out low bit?
*b = newsize; // initially unallocated
if (newsize < oldsize)
*(b+newsize) = oldsize - newsize; // set length in remaining
} // part of block (UNSCALED +)
Assume ptr points to a free block and has unscaled pointer arithmetic
malloc(24):
ptr b = find(24+8)
split(b, 24+8)
allocate(b)
Free word
Allocated word
Newly-allocated
word
16|1
16|1
48|0
b
16|0
16|1
16|1
32|1
CMPT 295
L23: Memory Allocation II
Note that we add 4 to the malloc request size to account for the header
Why not mask out? Bit must be 0, otherwise it's not a free block!
Implicit List: Freeing a Block
Simplest implementation just clears “allocated” flag
void free(ptr p) {*(p-WORD) &= -2;}
But can lead to “false fragmentation”
7
p
Oops! There is enough free space, but the allocator won’t be able to find it
16|0
16|1
16|1
32|1
Free word
Allocated word
Block of interest
16|0
16|1
16|1
32|0
malloc(40)
free(p)
CMPT 295
L23: Memory Allocation II
Implicit List: Coalescing with Next
Join (coalesce) with next block if also free
How do we coalesce with the previous block?
8
void free(ptr p) { // p points to payload
ptr b = p – WORD; // b points to block header
*b &= -2; // clear allocated bit
ptr next = b + *b; // find next block (UNSCALED +)
if ((*next & 1) == 0) // if next block is not allocated,
*b += *next; // add its size to this block
}
logically gone
16|0
16|1
16|1
32|1
16|0
16|1
16|1
48|0
free(p)
p
Free word
Allocated word
Block of interest
CMPT 295
L23: Memory Allocation II
Implicit List: Bidirectional Coalescing
Boundary tags [Knuth73]
Replicate header at “bottom” (end) of free blocks
Allows us to traverse backwards, but requires extra space
Important and general technique!
9
Footer
32/0
32/0
32/1
32/1
48/0
32/1
48/0
32/1
Header
size
payload and
padding
a
size
a
Format of
allocated and
free blocks:
a = 1: allocated block
a = 0: free block
size: block size (in bytes)
payload: application data
(allocated blocks only)
Boundary tags
CMPT 295
L23: Memory Allocation II
Constant Time Coalescing
10
Allocated
Allocated
Allocated
Free
Free
Allocated
Free
Free
Block being freed
Case 1
Case 2
Case 3
Case 4
CMPT 295
L23: Memory Allocation II
Constant Time Coalescing
m1 1
m1 1
n 1
n 1
m2 1
m2 1
m1 1
m1 1
n 0
n 0
m2 1
m2 1
Case 1
m1 1
m1 1
n 1
n 1
m2 0
m2 0
m1 1
m1 1
n+m2 0
n+m2 0
Case 2
m1 0
m1 0
n 1
n 1
m2 1
m2 1
n+m1 0
n+m1 0
m2 1
m2 1
Case 3
m1 0
m1 0
n 1
n 1
m2 0
m2 0
n+m1+m2 0
n+m1+m2 0
Case 4
CMPT 295
L23: Memory Allocation II
11
Implicit Free List Review Questions
What is the block header? What do we store and how?
What are boundary tags and why do we need them?
When we coalesce free blocks, how many neighboring blocks do we need to check on either side? Why is this?
If I want to check the size of the -th block forward from the current block, how many memory accesses do I make?
12
32/0
32/0
32/1
32/1
48/0
32/1
48/0
32/1
CMPT 295
L23: Memory Allocation II
Keeping Track of Free Blocks
Implicit free list using length – links all blocks using math
No actual pointers, and must check each block if allocated or free
Explicit free list among only the free blocks, using pointers
Segregated free list
Different free lists for different size “classes”
Blocks sorted by size
Can use a balanced binary tree (e.g. red-black tree) with pointers within each free block, and the length used as a key
13
40
32
16
48
40
32
16
48
= 8-byte word (free)
= 8-byte word (allocated)
CMPT 295
L23: Memory Allocation II
13
Explicit Free Lists
Use list(s) of free blocks, rather than implicit list of all blocks
The “next” free block could be anywhere in the heap
So we need to store next/previous pointers, not just sizes
Since we only track free blocks, so we can use “payload” for pointers
Still need boundary tags (header/footer) for coalescing
14
size
a
size
a
next
prev
Free block:
size
payload and
padding
a
size
a
Allocated block:
(same as implicit free list)
CMPT 295
L23: Memory Allocation II
Storing pointers in the “payload” section of a free block could require a larger minimum block size, possibly increasing internal fragmentation.
Doubly-Linked Lists
Linear
Needs head/root pointer
First node prev pointer is NULL
Last node next pointer is NULL
Good for first-fit, best-fit
Circular
Still have pointer to tell you which node to start with
No NULL pointers (term condition is back at starting point)
Good for next-fit, best-fit
15
Root
⋅⋅⋅
Start
⋅⋅⋅
CMPT 295
L23: Memory Allocation II
Explicit Free Lists
Logically: doubly-linked list
Physically: blocks can be in any order
16
A
B
C
32
32
32
32
48
48
32
32
32
32
Forward (next) links
Back (prev) links
A
B
C
CMPT 295
L23: Memory Allocation II
Allocating From Explicit Free Lists
Note: These diagrams are not very specific about where inside a block a pointer points. In reality we would always point to one place (e.g. start/header of a block).
17
Before
After
(with splitting)
= malloc(…)
CMPT 295
L23: Memory Allocation II
4 pointers updated, same number of list nodes.
Don’t forget to update boundary tags for both the allocated and new free blocks!
17
Allocating From Explicit Free Lists
Note: These diagrams are not very specific about where inside a block a pointer points. In reality we would always point to one place (e.g. start/header of a block).
18
Before
After
(fully allocated)
= malloc(…)
CMPT 295
L23: Memory Allocation II
2 pointers updated, one fewer list node.
Don’t forget to create the boundary tags for the allocated block!
18
Freeing With Explicit Free Lists
Insertion policy: Where in the free list do you put the newly freed block?
LIFO (last-in-first-out) policy
Insert freed block at the beginning (head) of the free list
Pro: simple and constant time
Con: studies suggest fragmentation is worse than the alternative
Address-ordered policy
Insert freed blocks so that free list blocks are always in address order:
address(previous) < address(current) < address(next)
Con: requires linear-time search
Pro: studies suggest fragmentation is better than the alternative
19
CMPT 295
L23: Memory Allocation II
Coalescing in Explicit Free Lists
Neighboring free blocks are already part of the free list
Remove old block from free list
Create new, larger coalesced block
Add new block to free list (insertion policy)
How do we tell if a neighboring block if free?
20
Block being freed
Allocated
Allocated
Case 1
Allocated
Free
Case 2
Free
Allocated
Case 3
Free
Free
Case 4
CMPT 295
L23: Memory Allocation II
20
Freeing with LIFO Policy (Case 1)
Insert the freed block at the root of the list
21
Before
After
Root
Boundary tags not shown, but don’t forget about them!
free( )
Root
CMPT 295
L23: Memory Allocation II
Note: all blue “next” pointers and red “previous” pointers should probably point to either the header or footer of the next/previous block – it shouldn’t matter which (I think), as long as it’s done consistently. The diagrams on this slide and on the next few do not always show pointers to the exact word for the block header/footer.
21
Freeing with LIFO Policy (Case 2)
Splice successor block out of list, coalesce both memory blocks, and insert the new block at the root of the list
22
Boundary tags not shown, but don’t forget about them!
Before
Root
free( )
After
Root
CMPT 295
L23: Memory Allocation II
Note: all blue “next” pointers and red “previous” pointers should probably point to either the header or footer of the next/previous block – it shouldn’t matter which (I think), as long as it’s done consistently. The diagrams on this slide and on the next few do not always show pointers to the exact word for the block header/footer.
22
Freeing with LIFO Policy (Case 3)
Splice predecessor block out of list, coalesce both memory blocks, and insert the new block at the root of the list
23
Boundary tags not shown, but don’t forget about them!
Before
Root
free( )
After
Root
CMPT 295
L23: Memory Allocation II
Note: all blue “next” pointers and red “previous” pointers should probably point to either the header or footer of the next/previous block – it shouldn’t matter which (I think), as long as it’s done consistently. The diagrams on this slide and on the next few do not always show pointers to the exact word for the block header/footer.
23
Freeing with LIFO Policy (Case 4)
Splice predecessor and successor blocks out of list, coalesce all 3 memory blocks, and insert the new block at the root of the list
24
Boundary tags not shown, but don’t forget about them!
Before
Root
free( )
After
Root
CMPT 295
L23: Memory Allocation II
Do we always need the boundary tags?
Lab 5 suggests no…
25
size
a
size
a
next
prev
Free block:
size
payload and
padding
a
size
a
Allocated block:
(same as implicit free list)
CMPT 295
L23: Memory Allocation II
Explicit List Summary
Comparison with implicit list:
Block allocation 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 we need to splice blocks in and out of the list
Some extra space for the links (2 extra pointers needed for each free block)
Increases minimum block size, leading to more internal fragmentation
Most common use of explicit lists is in conjunction with segregated free lists
Keep multiple linked lists of different size classes, or possibly for different types of objects
26
CMPT 295
L23: Memory Allocation II
The following slides are about the SegList Allocator, for those curious. You will NOT be expected to know this material.
27
BONUS SLIDES
CMPT 295
L23: Memory Allocation II
CSE 351 Lecture 6
Keeping Track of Free Blocks
Implicit free list using length – links all blocks using math
No actual pointers, and must check each block if allocated or free
Explicit free list among only the free blocks, using pointers
Segregated free list
Different free lists for different size “classes”
Blocks sorted by size
Can use a balanced binary tree (e.g. red-black tree) with pointers within each free block, and the length used as a key
28
40
32
16
48
40
32
16
48
= 8-byte box (free)
= 8-byte box (allocated)
CMPT 295
L23: Memory Allocation II
28
Segregated List (SegList) Allocators
Each size class of blocks has its own free list
Organized as an array of free lists
Often have separate classes for each small size
For larger sizes: One class for each two-power size
29
32
48-64
80-inf
16
Size class
(in bytes)
CMPT 295
L23: Memory Allocation II
SegList Allocator
Have an array of free lists for various size classes
To allocate a block of size :
Search appropriate free list for block of size
If an appropriate block is found:
[Optional] Split block and place free fragment on appropriate list
If no block is found, try the next larger class
Repeat until block is found
If no block is found:
Request additional heap memory from OS (using sbrk)
Place remainder of additional heap memory as a single free block in appropriate size class
30
CMPT 295
L23: Memory Allocation II
SegList Allocator
Have an array of free lists for various size classes
To free a block:
Mark block as free
Coalesce (if needed)
Place on appropriate class list
31
CMPT 295
L23: Memory Allocation II
SegList Advantages
Higher throughput
Search is log time for power-of-two size classes
Better memory utilization
First-fit search of seglist approximates a best-fit search of entire heap
Extreme case: Giving every block its own size class is no worse than best-fit search of an explicit list
Don’t need to use space for block size for the fixed-size classes
32
CMPT 295
L23: Memory Allocation II
/docProps/thumbnail.jpeg