PowerPoint PresentationReviewDon’t forget the globals!C Memory ManagementNormal C Memory ManagementWhere are variables allocated?The StackStackWho cares about stack management?The Heap (Dynamic memory)Memory ManagementHeap Management RequirementsHeap ManagementSlide 14K&R Malloc/Free ImplementationK&R ImplementationChoosing a block in malloc()Peer Instruction – Pros and Cons of fitsAnd in conclusion…Bonus slidesIntel 80x86 C Memory ManagementTradeoffs of allocation policiesCS61C L06 C Memory Management (1)Garcia, Spring 2008 © UCBLecturer SOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61c CS61C : Machine Structures Lecture 6 – C Memory Management 2007-02-04Hello to Justin H from Seattle, WAIntel: High Speed Memory Intel says it has found a way tomake its NAND flash memory five times faster (200MB/s) than before. They call it “high-speed NAND”, and it is expected to be available this summer. Great for hybrid (disk + flash) drives ! www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=9060581CS61C L06 C Memory Management (2)Garcia, Spring 2008 © UCBReview•Use handles to change pointers•Create abstractions (and your own data structures) with structures•Dynamically allocated heap memory must be manually deallocated in C.•Use malloc() and free() to allocate and de-allocate persistent storage.CS61C L06 C Memory Management (3)Garcia, Spring 2008 © UCBDon’t forget the globals!•Remember:•Structure declaration does not allocate memory•Variable declaration does allocate memory•So far we have talked about several different ways to allocate memory for data:1. Declaration of a local variableint i; struct Node list; char *string; int ar[n];2. “Dynamic” allocation at runtime by calling allocation function (alloc). ptr = (struct Node *) malloc(sizeof(struct Node)*n);•One more possibility exists…•Data declared outside of any procedure (i.e., before main).•Similar to #1 above, but has “global” scope.int myGlobal;main() { }CS61C L06 C Memory Management (4)Garcia, Spring 2008 © UCBC Memory Management•C has 3 pools of memory•Static storage: global variable storage, basically permanent, entire program run•The Stack: local variable storage, parameters, return address(location of “activation records” in Java or “stack frame” in C)•The Heap (dynamic malloc storage): data lives until deallocated by programmer •C requires knowing where objects are in memory, otherwise things don’t work as expected•Java hides location of objectsCS61C L06 C Memory Management (5)Garcia, Spring 2008 © UCBNormal C Memory Management•A program’s address space contains 4 regions:•stack: local variables, grows downward •heap: space requested for pointers via malloc() ; resizes dynamically, grows upward•static data: variables declared outside main, does not grow or shrink•code: loaded when program starts, does not changecodestatic dataheapstackFor now, OS somehowprevents accesses between stack and heap (gray hash lines). Wait for virtual memory~ FFFF FFFFhex~ 0hexCS61C L06 C Memory Management (6)Garcia, Spring 2008 © UCBWhere are variables allocated?•If declared outside a procedure, allocated in “static” storage •If declared inside procedure, allocated on the “stack”and freed when procedure returns.•NB: main() is a procedureint myGlobal;main() { int myTemp;}CS61C L06 C Memory Management (7)Garcia, Spring 2008 © UCBThe Stack•Stack frame includes:•Return “instruction” address•Parameters•Space for other local variables•Stack frames contiguous blocks of memory; stack pointer tells where top stack frame is•When procedure ends, stack frame is tossed off the stack; frees memory for future stack framesframeframeframeframeSPCS61C L06 C Memory Management (8)Garcia, Spring 2008 © UCBStack•Last In, First Out (LIFO) data structuremain (){ a(0); }void a (int m){ b(1); }void b (int n){ c(2); }void c (int o){ d(3); }void d (int p){ }stackStack PointerStack PointerStack PointerStack PointerStack PointerStack grows downCS61C L06 C Memory Management (9)Garcia, Spring 2008 © UCB•Pointers in C allow access to deallocated memory, leading to hard-to-find bugs !int *ptr () {int y;y = 3;return &y;};main () {int *stackAddr,content; stackAddr = ptr();content = *stackAddr;printf("%d", content); /* 3 */content = *stackAddr;printf("%d", content); /*13451514 */};Who cares about stack management?mainptr()(y==3)SPmainSPmainprintf()(y==?)SPCS61C L06 C Memory Management (10)Garcia, Spring 2008 © UCBThe Heap (Dynamic memory)•Large pool of memory, not allocated in contiguous order•back-to-back requests for heap memory could result 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(sizeof(int));/* malloc returns type (void *),so need to cast to right type */•malloc(): Allocates raw, uninitialized memory from heapCS61C L06 C Memory Management (11)Garcia, Spring 2008 © UCBMemory 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 timeCS61C L06 C Memory Management (12)Garcia, Spring 2008 © UCBHeap 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.* This is technically called external fragmentionCS61C L06 C Memory Management (13)Garcia, Spring 2008 © UCBHeap Management•An example•Request R1 for 100 bytes•Request R2 for 1 byte•Memory from R1 is freed•Request R3 for 50 bytesR2 (1 byte)R1 (100 bytes)CS61C L06 C Memory Management (14)Garcia, Spring 2008 © UCBHeap Management•An example•Request R1 for 100 bytes•Request R2 for 1 byte•Memory from R1 is freed•Request R3 for 50 bytesR2 (1 byte)R3?R3?CS61C L06 C Memory Management (15)Garcia, Spring 2008 © UCBK&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
View Full Document
Unlocking...