Carnegie Mellon Introduction to Computer Systems 15 213 fall 2009 19th Lecture Nov 2nd Instructors Majd Sakr and Khaled Harras Carnegie Mellon Last Time Dynamic Memory Allocation p1 malloc 4 p2 malloc 5 p3 malloc 6 free p2 p4 malloc 2 Carnegie Mellon Last Time Fragmentation Internal Internal fragmentation block payload Internal fragmentation External p4 malloc 6 Oops what would happen now Carnegie Mellon Today Dynamic memory allocation Implicit free lists Explicit free lists Segregated free lists Garbage collection Carnegie Mellon Keeping Track of Free Blocks Method 1 Implicit free list using length links all blocks 5 6 2 Method 2 Explicit free list among the free blocks using pointers 5 4 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 Carnegie Mellon Implicit List For each block we need length is allocated Could store this information in two words wasteful Standard trick If blocks are aligned some low order address bits are always 0 Instead of storing an always 0 bit use it as a allocated free flag When reading size word must mask out this bit 1 word size Format of allocated and free blocks payload a a 1 allocated block a 0 free block size block size payload application data allocated blocks only optional padding Carnegie Mellon Example Blackboard Assumptions word addressed memory 2 word alignment Start of heap Free word 2 0 4 1 8 0 4 1 0 1 Allocated word Allocated word unused 8 bytes 2 word alignment 8 byte alignment May require initial unused word Causes some internal fragmentation One word 0 1 to mark end of list Here block size in words for simplicity Carnegie Mellon Implicit List Finding a Free Block First fit Search list from beginning choose first free block that fits Cost p start while p end p 1 p len p p p 2 not passed end already allocated too Blackboard small will disappear goto next block word addressed Carnegie Mellon Implicit List Finding a Free Block First fit Search list from beginning choose first free block that fits Cost p start while p end p 1 p len p p p 2 not passed end already allocated too small goto next block word addressed Can take linear time in total number of blocks allocated and free In practice it can cause splinters at beginning of list 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 fits with fewest bytes left over Keeps fragments small usually helps fragmentation Will typically run slower than first fit Carnegie Mellon Implicit List Allocating in Free Block Allocating in a free block splitting Since allocated space might be smaller than free space we might want to split the block 4 4 6 2 p addblock p 4 4 4 4 void addblock ptr p int len int newsize len 1 1 1 int oldsize p 2 p newsize 1 if newsize oldsize p newsize oldsize newsize 2 2 round up to even mask Blackboard out low bit set new length will disappear set length in remaining part of block Carnegie Mellon Implicit List Allocating in Free Block Allocating in a free block splitting Since allocated space might be smaller than free space we might want to split the block 4 4 6 2 p addblock p 4 4 4 4 void addblock ptr p int len int newsize len 1 1 1 int oldsize p 2 p newsize 1 if newsize oldsize p newsize oldsize newsize 2 2 round up to even mask out low bit set new length set length in remaining part of block Carnegie Mellon Implicit List Freeing a Block Simplest implementation Need only clear the allocated flag void free block ptr p p p 2 But can lead to false fragmentation 4 4 2 2 2 2 p free p 4 malloc 5 4 4 4 Oops There is enough free space but the allocator won t be able to find it Carnegie Mellon Implicit List Coalescing Join coalesce with next previous blocks if they are free Coalescing with next block 4 4 4 2 2 2 2 p free p 4 4 void free block ptr p p p 2 next p p if next 1 0 p p next 6 clear allocated flag find next block add to this block if not allocated But how do we coalesce with previous block logically gone Carnegie Mellon Implicit List Bidirectional Coalescing Boundary tags Knuth73 Replicate size allocated word at bottom end of free blocks Allows us to traverse the list backwards but requires extra space Important and general technique 4 4 4 Header Format of allocated and free blocks Boundary tag footer 4 6 size 6 4 a payload and padding size 4 a 1 allocated block a 0 free block size total block size a payload application data allocated blocks only Carnegie Mellon Constant Time Coalescing block being freed Case 1 Case 2 Case 3 Case 4 allocated allocated free free allocated free allocated free Carnegie Mellon Constant Time Coalescing Case 1 m1 1 m1 1 m1 n 1 1 m1 n 1 0 n m2 1 1 n m2 0 1 m2 1 m2 1 Carnegie Mellon Constant Time Coalescing Case 2 m1 1 m1 1 m1 n 1 1 m1 n m2 1 0 n m2 1 0 m2 0 n m2 0 Carnegie Mellon Constant Time Coalescing Case 3 m1 0 n m1 0 m1 n 0 1 n m2 1 1 n m1 m2 0 1 m2 1 m2 1 Carnegie Mellon Constant Time Coalescing Case 4 m1 0 m1 n 0 1 n m2 1 0 m2 0 n m1 m2 0 n m1 m2 0 Carnegie Mellon Disadvantages of Boundary Tags Internal fragmentation Can it be optimized When does the previous block need the footer tag How to take advantage of that Carnegie Mellon Summary of Key Allocator Policies Placement policy First fit next fit best fit etc Trades off lower throughput for less fragmentation Interesting observation segregated free lists next lecture approximate a best fit placement policy without having to search entire free list Splitting policy When do we go ahead and split free blocks How much internal fragmentation are we willing to tolerate Coalescing policy Immediate coalescing coalesce each time free is called Deferred coalescing try to improve performance of free by deferring coalescing until needed Examples Coalesce as you scan the free list for malloc Coalesce when the amount of external fragmentation reaches some threshold Carnegie Mellon Implicit Lists Summary Implementation very simple Allocate cost linear time worst case Free cost constant time worst case even with coalescing Memory usage will depend on placement policy First fit next fit or best fit Not used in practice for malloc free because of linear time allocation used in many special purpose applications …
View Full Document
Unlocking...