inst eecs berkeley edu cs61c su05 CS61C Machine Structures Lecture 5 Memory Management CS 61C L05 Memory Management 1 2005 06 27 Andy Carle A Carle Summer 2005 UCB Memory Management 1 2 Variable declaration allocates memory outside a procedure static storage inside procedure stack freed when procedure returns Malloc request Pointer static or stack Content on heap CS 61C L05 Memory Management 2 int myGlobal main int myTemp int f malloc 16 A Carle Summer 2005 UCB Memory Management FFFF FFFF 2 2 A program s address space contains 4 regions hex stack stack local variables grows downward heap space requested for pointers via malloc resizes dynamically grows upward heap static data variables declared outside main does not grow or shrink code 0hex code loaded when program starts does not change CS 61C L05 Memory Management 3 static data For now OS somehow prevents accesses between stack and heap gray hash lines Wait for virtual memory A Carle Summer 2005 UCB The Stack 1 4 Terminology Stack is composed of frames A frame corresponds to one procedure invocation Stack frame includes frame Return address of caller Space for other local variables frame When procedure ends stack frame is tossed off the stack frees memory for future stack frames SP CS 61C L05 Memory Management 4 frame frame A Carle Summer 2005 UCB The Stack 2 4 Implementation By convention stack grows down in memory Stack pointer SP points to next available address PUSH On invocation callee moves SP down to create new frame to hold callee s local variables and RA old SP new SP size of frame POP On return callee moves SP back to original returns to caller SP CS 61C L05 Memory Management 5 frame frame frame frame A Carle Summer 2005 UCB The Stack 3 4 Last In First Out LIFO memory usage stack main a 0 void a int m b 1 void b int n c 2 void c int o d 3 void d int p CS 61C L05 Memory Management 6 Stack Pointer Stack Pointer Stack Pointer Stack Pointer Stack Pointer A Carle Summer 2005 UCB The Stack 4 4 Dangling Pointers Pointers in C allow access to deallocated memory leading to hard to find bugs int ptr main main main SP int y y 3 printf ptr return y y y 3 SP SP main int stackAddr stackAddr ptr printf d stackAddr 3 printf d stackAddr XXX CS 61C L05 Memory Management 7 A Carle Summer 2005 UCB Static and Code Segments Code Text Segment Holds instructions to be executed Constant size Static Segment Holds global variables whose addresses are known at compile time Compare to the heap malloc calls where address isn t known CS 61C L05 Memory Management 8 A Carle Summer 2005 UCB The Heap Dynamic memory Large pool of memory not allocated in contiguous order back to back requests for heap memory could return blocks very far apart where Java new command allocates memory In C specify number of bytes of memory explicitly to allocate item int ptr ptr int malloc 4 malloc returns type void so need to cast to right type malloc Allocates raw uninitialized memory from heap CS 61C L05 Memory Management 9 A Carle Summer 2005 UCB Memory Management How do we manage memory Code Static storage are easy they never grow or shrink Stack space is also easy stack frames are created and destroyed in last in first out LIFO order Managing the heap is tricky memory can be allocated deallocated at any time CS 61C L05 Memory Management 10 A Carle Summer 2005 UCB Heap Management Requirements Want malloc and free to run quickly Want minimal memory overhead Want to avoid fragmentation when most of our free memory is in many small chunks In this case we might have many free bytes but not be able to satisfy a large request since the free bytes are not contiguous in memory CS 61C L05 Memory Management 11 A Carle Summer 2005 UCB Heap Management An example Request R1 for 100 bytes Request R2 for 1 byte Memory from R1 is freed R1 100 bytes R2 1 byte Request R3 for 50 bytes CS 61C L05 Memory Management 12 A Carle Summer 2005 UCB Heap Management An example R3 Request R1 for 100 bytes Request R2 for 1 byte Memory from R1 is freed Request R3 for 50 bytes CS 61C L05 Memory Management 13 R2 1 byte R3 A Carle Summer 2005 UCB K R Malloc Free Implementation From Section 8 7 of K R Code in the book uses some C language features we haven t discussed and is written in a very terse style don t worry if you can t decipher the code Each block of memory is preceded by a header that has two fields size of the block and a pointer to the next block All free blocks are kept in a linked list the pointer field is unused in an allocated block CS 61C L05 Memory Management 14 A Carle Summer 2005 UCB K R Implementation malloc searches the free list for a block that is big enough If none is found more memory is requested from the operating system free checks if the blocks adjacent to the freed block are also free If so adjacent free blocks are merged coalesced into a single larger free block Otherwise the freed block is just added to the free list CS 61C L05 Memory Management 15 A Carle Summer 2005 UCB Choosing a block in malloc If there are multiple free blocks of memory that are big enough for some request how do we choose which one to use best fit choose the smallest block that is big enough for the request first fit choose the first block we see that is big enough next fit like first fit but remember where we finished searching and resume searching from there CS 61C L05 Memory Management 16 A Carle Summer 2005 UCB PRS Round 1 A con of first fit is that it results in many small blocks at the beginning of the free list A con of next fit is it is slower than first fit since it takes longer in steady state to find a match A con of best fit is that it leaves lots of tiny blocks CS 61C L05 Memory Management 17 A Carle Summer 2005 UCB Tradeoffs of allocation policies Best fit Tries to limit fragmentation but at the cost of time must examine all free blocks for each malloc Leaves lots of small blocks why First fit Quicker than best fit why but potentially more fragmentation Tends to concentrate small blocks at the beginning of the free list why Next fit Does not concentrate small blocks at front like first fit should be faster as a result CS 61C L05 Memory Management 18 A Carle Summer 2005 UCB Administrivia HW2 Due Wednesday HW3 Out Today Due Sunday Proj1 Coming Soon If you still aren t enrolled in the course you may need to talk to Barbara Hightower to get things straightened out You will almost certainly need to move to section …
View Full Document
Unlocking...