程序代写代做代考 Memory Allocation II CSE 351 Autumn 2016

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