inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 7 C Memory Management 2010 02 03 Lecturer SOE Dan Garcia www cs berkeley edu ddgarcia Flexible plastic displays Phicot has come up with a way to print silicon electronics onto plastic as they are fed through rollers The secret was depositing silicon at low enough temperatures that won t melt the plastic www technologyreview com computing 24433 CS61C L07 More Memory Management 1 Garcia Spring 2010 UCB Review C has 3 pools of memory What programs use what areas Static storage global variable storage basically permanent entire program run The Stack local variable storage parameters return address The Heap dynamic storage malloc grabs space from here free returns it malloc handles free space with freelist Three different ways to find free space when given a request First fit find first one that s free Next fit same as first but remembers where left off Best fit finds most snug free space CS61C L07 More Memory Management 2 Garcia Spring 2010 UCB Slab Allocator A different approach to memory management used in GNU libc Divide blocks in to large and small by picking an arbitrary threshold size Blocks larger than this threshold are managed with a freelist as before For small blocks allocate blocks in sizes that are powers of 2 e g if program wants to allocate 20 bytes actually give it 32 bytes CS61C L07 More Memory Management 3 Garcia Spring 2010 UCB Slab Allocator Bookkeeping for small blocks is relatively easy just use a bitmap for each range of blocks of the same size Allocating is easy and fast compute the size of the block to allocate and find a free bit in the corresponding bitmap Freeing is also easy and fast figure out which slab the address belongs to and clear the corresponding bit CS61C L07 More Memory Management 4 Garcia Spring 2010 UCB Slab Allocator 16 byte blocks 32 byte blocks 64 byte blocks 16 byte block bitmap 11011000 32 byte block bitmap 0111 64 byte block bitmap 00 CS61C L07 More Memory Management 5 Garcia Spring 2010 UCB Slab Allocator Tradeoffs Extremely fast for small blocks Slower for large blocks But presumably the program will take more time to do something with a large block so the overhead is not as critical Minimal space overhead No fragmentation as we defined it before for small blocks but still have wasted space CS61C L07 More Memory Management 6 Garcia Spring 2010 UCB Internal vs External Fragmentation With the slab allocator difference between requested size and next power of 2 is wasted e g if program wants to allocate 20 bytes and we give it a 32 byte block 12 bytes are unused We also refer to this as fragmentation but call it internal fragmentation since the wasted space is actually within an allocated block External fragmentation wasted space between allocated blocks CS61C L07 More Memory Management 7 Garcia Spring 2010 UCB Buddy System Yet another memory management technique used in Linux kernel Like GNU s slab allocator but only allocate blocks in sizes that are powers of 2 internal fragmentation is possible Keep separate free lists for each size e g separate free lists for 16 byte 32 byte 64 byte blocks etc CS61C L07 More Memory Management 8 Garcia Spring 2010 UCB Buddy System If no free block of size n is available find a block of size 2n and split it in to two blocks of size n When a block of size n is freed if its neighbor of size n is also free combine the blocks in to a single block of size 2n is block in other half larger block Buddy buddies NOT buddies Same speed advantages as slab allocator CS61C L07 More Memory Management 9 Garcia Spring 2010 UCB Allocation Schemes So which memory management scheme K R slab buddy is best There is no single best approach for every application Different applications have different allocation deallocation patterns A scheme that works well for one application may work poorly for another application CS61C L07 More Memory Management 10 Garcia Spring 2010 UCB Automatic Memory Management Dynamically allocated memory is difficult to track why not track it automatically If we can keep track of what memory is in use we can reclaim everything else Unreachable memory is called garbage the process of reclaiming it is called garbage collection So how do we track what is in use CS61C L07 More Memory Management 13 Garcia Spring 2010 UCB Tracking Memory Usage Techniques depend heavily on the programming language and rely on help from the compiler Start with all pointers in global variables and local variables root set Recursively examine dynamically allocated objects we see a pointer to We can do this in constant space by reversing the pointers on the way down How do we recursively find pointers in dynamically allocated memory CS61C L07 More Memory Management 14 Garcia Spring 2010 UCB Tracking Memory Usage Again it depends heavily on the programming language and compiler Could have only a single type of dynamically allocated object in memory E g simple Lisp Scheme system with only cons cells 61A s Scheme not simple Could use a strongly typed language e g Java Don t allow conversion casting between arbitrary types C C are not strongly typed Here are 3 schemes to collect garbage CS61C L07 More Memory Management 15 Garcia Spring 2010 UCB Scheme 1 Reference Counting For every chunk of dynamically allocated memory keep a count of number of pointers that point to it When the count reaches 0 reclaim Simple assignment statements can result in a lot of work since may update reference counts of many items CS61C L07 More Memory Management 16 Garcia Spring 2010 UCB Reference Counting Example For every chunk of dynamically allocated memory keep a count of number of pointers that point to it When the count reaches 0 reclaim int p1 p2 p1 p1 malloc sizeof int p2 p2 malloc sizeof int p1 10 p2 20 Reference count 1 CS61C L07 More Memory Management 17 20 Reference count 1 10 Garcia Spring 2010 UCB Reference Counting Example For every chunk of dynamically allocated memory keep a count of number of pointers that point to it When the count reaches 0 reclaim int p1 p2 p1 p1 malloc sizeof int p2 p2 malloc sizeof int p1 10 p2 20 p1 p2 Reference count 2 CS61C L07 More Memory Management 18 20 Reference count 0 10 Garcia Spring 2010 UCB Reference Counting p1 p2 are pointers p1 p2 Increment reference count for p2 If p1 held a valid value decrement its reference count If the reference count for p1 is now 0 reclaim the storage it points to If the storage pointed to by p1 held other pointers
View Full Document
Unlocking...