15 213 The course that gives CMU its Zip L6 Malloc Lab Writing a Dynamic Storage Allocator October 30 2006 Topics Memory Allocator Heap L6 Malloc Lab Reminders L6 Malloc Lab Due Nov 10 2006 Section A Donnie H Kim recitation8 ppt some slides from lecture notes L6 Malloc Lab Things that matter in this lab Performance goal Maximizing throughput Maximizing memory utilization Implementation Issues Design Space Free Block Organization Placement Policy Splitting Coalescing 2 And some advice 15 213 F 06 Some sort of useful backgrounds 3 15 213 F 06 So what is memory allocation kernel virtual memory stack esp memory invisible to user code Memory mapped region for shared libraries Allocators request additional heap memory from the operating system using the sbrk function the brk ptr run time heap via malloc uninitialized data bss initialized data data program text text 4 0 15 213 F 06 Malloc Package include stdlib h void malloc size t size If successful Returns a pointer to a memory block of at least size bytes typically aligned to 8 byte boundary If size 0 returns NULL If unsuccessful returns NULL 0 and sets errno void free void p Returns the block pointed at by p to pool of available memory p must come from a previous call to malloc or realloc void realloc void p size t size 5 Changes size of block p and returns pointer to new block Contents of new block unchanged up to min of old and new size 15 213 F 06 Allocation Examples p1 malloc 4 p2 malloc 5 p3 malloc 6 free p2 p4 malloc 2 6 15 213 F 06 Performance goals Maximizing throughput Temporal Defined as the number of requests that it completes per unit time Maximizing Memory Utilization Spatial Defined as the ratio of the requested memory size and the actual memory size used There is a tension between maximizing throughput and utilization Find an appropriate balance between two goals Keep this in mind we will come back to these issues 7 15 213 F 06 Implementation Issues Free Block Organization How do we keep track of the free blocks How do we know how much memory to free just given a pointer Placement Policy How do we choose an appropriate free block Splitting What do we do with the extra space when allocating a structure that is smaller than the free block it is placed in Coalescing How do we reinsert freed block p0 free p0 8 p1 malloc 1 15 213 F 06 Implementation Issues 1 Free Block Organization Identifying which block is free or allocated Available design choices of how to manage free blocks Implicit List Explicit List Segregated List Header Footer organization storing information about the block size allocated freed 9 15 213 F 06 Keeping Track of Free Blocks Method 1 Implicit list using lengths links all blocks 5 4 6 2 Method 2 Explicit list among the free blocks using pointers within the free blocks 5 4 6 2 Method 3 Segregated free list Different free lists for different size classes Method 4 Blocks sorted by size 10 Can use a balanced tree e g Red Black tree with pointers within each free block and the length used as a key 15 213 F 06 Free Block Organization Free Block with header 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 11 15 213 F 06 Free Block Organization Free Block with Header and Footer Header Format of allocated and free blocks Boundary tag footer 12 size a payload and padding size a 1 allocated block a 0 free block size total block size a payload application data allocated blocks only 15 213 F 06 Implementation Issues 2 Placement Policy Placement Policy choices First Fit Search free list from the beginning and chose the first free block Next Fit Starts search where the previous search has left of Best Fit Examine every free block to find the best free block 13 15 213 F 06 Implementation Issues 3 Splitting Splitting Design choices Using the entire free block Simple fast Introduces internal fragmentation good placement policy might reduce this Splitting Split free block into two parts when second part can be used for other requests reduces internal fragmentation 14 p1 malloc 1 15 213 F 06 Implementation Issues 4 False Fragmentations Coalescing Free block chopped into small unusable free blocks Coalesce adjacent free blocks to get bigger free block Coalescing Policy decision of when to perform coalescing Immediate coalescing Merging any adjacent blocks each time a block is freed Deferred coalescing Merging free blocks some time later Ex when allocation request fails 15 Trying Bidirectional Immediate Coalescing proposed by Donald Knuth would be good enough for this lab 15 213 F 06 Performance goals Maximizing throughput Temporal Defined as the number of requests that it completes per unit time Maximizing Memory Utilization Spatial Defined as the ratio of the requested memory size and the actual memory size used There is a tension between maximizing throughput and utilization Find an appropriate balance between two goals 16 15 213 F 06 Performance goal 1 Throughput Throughput is mostly determined by time consumed to search free block How you keep track of your free block afects search time Na ve allocator Never frees block just extend the heap when you need a new block throughput is extremely fast but Implicit Free List The allocator can indirectly traverse the entire set of free blocks by traversing all of the blocks in the heap definitely slow Explicit Free List The allocator can directly traverse entire set of free blocks by traversing all of the free blocks in the heap Segregated Free List The allocator can directly traverse a particular free list to find an appropriate free block 17 15 213 F 06 Performance goal 2 Memory Utilization Poor memory utilization caused by fragmentation Comes in two forms internal and external fragmentation Internal Fragmentation Based on previous requests Causes Allocator impose minimal size of block depending on allocator s choice of block format Satisfying alignment requirements External Fragmenatation Based on future requests Aggregate free memory is enough but no single free block is large enough to handle the request 18 15 213 F 06 Internal Fragmentation Internal fragmentation For some block internal fragmentation is the diference between the block size and the payload size block Internal fragmentation 19 payload Internal fragmentation Caused by overhead of maintaining heap data structures padding for alignment purposes or explicit policy decisions e g not to
View Full Document
Unlocking...