class14 ppt Explicit memory allocation Data structures Mechanisms Topics Memory Management I Dynamic Storage Allocation March 2 2000 The course that gives CMU its Zip 15 213 class14 ppt 2 CS 213 S 00 Cache and virtual memory effects can greatly affect program performance Adapting program to characteristics of memory system can lead to major speed improvements Memory performance is not uniform Effects are distant in both time and space Memory referencing bugs especially pernicious It must be allocated and managed Many applications are memory dominated Especially those based on complex graph algorithms Memory is not unbounded Memory Matters Harsh Reality 3 class14 ppt 3 CS 213 S 00 Will discuss explicit storage allocation today In both cases the storage allocator provides an abstraction of memory as a set of blocks Doles out free memory blocks to application Allocation Explicit application allocates and frees space E g malloc and free in C Implicit application allocates but does not free space E g garbage collection in Java ML or Lisp Explicit vs Implicit Storage Allocator Heap Memory Dynamic Storage Allocator Application Dynamic Storage Allocation class14 ppt esp 0 4 program text text initialized data data uninitialized data bss run time heap via malloc Memory mapped region for shared libraries stack kernel virtual memory CS 213 S 00 the brk ptr memory invisible to user code Process memory image class14 ppt Allocated block 4 words 5 Free block 3 words CS 213 S 00 Allocated word Free word memory is word addressed each word can hold a pointer Assumptions made in this lecture p must come from a previous call to malloc returns the block pointed at by p to pool of available memory void free void p if unsuccessful returns NULL if size 0 returns NULL returns a pointer to a memory block of at least size bytes if successful void malloc int size Malloc package class14 ppt p4 malloc 2 free p2 p3 malloc 6 p2 malloc 5 p1 malloc 4 6 Allocation example CS 213 S 00 class14 ppt 7 CS 213 S 00 Can t control number or size of allocated blocks Must respond immediately to all allocation requests i e can t reorder or buffer requests Must allocate blocks from free memory i e can only place allocated blocks in free memory Must align blocks so they satisfy all alignment requirements usually 8 byte alignment Can only manipulate and modify free memory Can t move the allocated blocks once they are allocated i e compaction is not allowed Allocators Can issue arbitrary sequence of allocation and free requests Free requests must correspond to an allocated block Applications Constraints class14 ppt 8 CS 213 S 00 Good locality properties structures allocated close in time should be close in space similar objects should be allocated close in space Robust can check that free p1 is on a valid allocated object p1 can check that memory references are to allocated space Some other goals Good time performance for malloc and free Ideally should take constant time not always possible Should certainly not take linear time in the number of blocks Good space usage User allocated structures should be large fraction of operating system allocated pages Need to avoid fragmentation Primary goals Goals of good malloc free class14 ppt 9 No general solution assuming we cannot move blocks We will consider several heuristics p4 malloc 6 oops free p2 p3 malloc 6 p2 malloc 5 CS 213 S 00 Tendency for free blocks to become smaller over time leading to wasted space p1 malloc 4 Fragmentation class14 ppt p1 malloc 1 free p0 10 p0 CS 213 S 00 How do we know how much memory to free just given a pointer How do we keep track of the free blocks What do we do with the extra space when allocating a structure that is smaller than the free block it is placed in How do we pick a block to use for allocation many might fit How do we reinsert freed block Implementation issues class14 ppt free p0 p0 malloc 4 data 11 Block size 5 p0 CS 213 S 00 keep the length of a structure in the word preceeding the structure This word is often called the header field requires an extra word for every allocated structure Standard method Knowing how much to free 4 6 2 4 6 2 class14 ppt 12 CS 213 S 00 Can use a balanced tree e g Red Black tree with pointers within each free block and the length used as a key Method 4 blocks sorted by size Different free lists for different size classes Method 3 segregated free lists 5 Method 2 explicit list among the free blocks using pointers within the free blocks 5 Method 1 implicit list using lengths links all blocks Keeping track of free blocks class14 ppt Format of allocated and free blocks data size 1 word a 13 CS 213 S 00 data application data allocated blocks only size block size a 1 allocated block a 0 free block Can use extra bit Bit can be put in the same word as the size if block sizes are always multiples of two mask out low order bit when reading size Need to identify whether each block is free or allocated Method 1 implicit list not passed end already allocated too small class14 ppt 14 CS 213 S 00 Search the list choose the free block with the closest size that fits Keeps fragments small usually helps fragmentation Will typically run slower than first fit Best fit Like first fit but search list from location of end of previous search Does a better job of spreading out the free blocks Next fit Can take linear time in total number of blocks allocated and free In practice it can cause splinters at beginning of list p start while p end p 1 p len Search list from beginning choose first free block that fits First fit Implicit list finding a free block 4 p 6 class14 ppt 4 addblock p 2 4 15 4 void addblock ptr p int l int newsize l 1 1 1 int oldsize p 2 p newsize 1 if newsize oldsize p newsize oldsize newsize 4 2 2 CS 213 S 00 set length in remaining part of block add 1 and round up mask out low bit set new length 2 Since allocated space might be smaller than free space we need to split the block Allocating in a free block splitting Implicit list allocating in a free block Oops 4 4 4 4 p 4 2 2 2 2 class14 ppt 16 CS 213 S 00 There is enough free space but the allocator won t be able to find it malloc 5 free p 4 But can lead to false fragmentation void free block ptr p p p 2 Only need to clear allocated flag Simplest implementation Implicit list freeing a block 4 4 4 6 p 4 2 class14 ppt 17 But how do we coalesce with previous block free p 4 2 2 CS 213 S 00 void free block ptr p p p 2 clear …
View Full Document
Unlocking...