Dynamic Memory ManagementSlide 2Slide 3Goals of Today’s LectureMemory Layout: HeapAllocating & Deallocating MemoryOption #1: Garbage CollectionChallenges of Garbage CollectionOption #2: Manual DeallocationManual Deallocation Can Lead to BugsSlide 11Slide 12Challenges for Malloc and FreeHeap: Dynamic MemorySlide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Goals for Malloc and FreeKeeping Track of Free BlocksNeed to Minimize FragmentationSimple “K&R-Like” ApproachAllocate Memory in Multiples of Base SizeLinked List of Free Blocks“First-Fit” AllocationSplitting an Oversized Free BlockCircular Linked List of Free BlocksMaintaining Free Blocks in OrderCoalescing Adjacent Free BlocksAn Implementation ChallengeStore Information in the Free BlockConclusionsStupid Programmer Tricks, Part 1Expanding on This ApproachStupid Programmer Tricks, Part 2How to Make Purists Cry1Dynamic Memory Management2•What’s worse?50% of instructions/data are cache misses (fetched from RAM)1% of instructions/data are page faults (fetched from disk)3•50% cache misses.50 + .50*100•1% disk misses.99 + .01 * 100,0004Goals of Today’s Lecture•Dynamic memory managementGarbage collection by the run-time system (Java)Manual deallocation by the programmer (C, C++)•Challenges of manual deallocation Arbitrary request sizes in an arbitrary orderComplex evolution of heap as a program runs•Design decisions for the “K&R” implementationCircular linked-list of free blocks with a “first fit” allocationCoalescing of adjacent blocks to create larger blocks5Memory Layout: Heapchar* string = “hello”;int iSize;char* f(){ char* p; scanf(“%d”, &iSize); p = malloc(iSize); return p;}TextBSSStackHeapNeeded when required memory size is not known before the program runsRoDataData6Allocating & Deallocating Memory•Dynamically allocating memoryProgrammer explicitly requests space in memorySpace is allocated dynamically on the heapE.g., using “malloc” in C, and “new” in Java•Dynamically deallocating memoryMust reclaim or recycle memory that is never used againTo avoid (eventually) running out of memory•“Garbage”Allocated block in heap that will not be accessed again Can be reclaimed for later use by the program7Option #1: Garbage Collection•Run-time system does garbage collection (Java)Automatically determines objects that can’t be accessedAnd then reclaims the resources used by these objectsObject x = new Foo();Object y = new Bar();x = new Quux();if (x.check_something()) { x.do_something(y);}System.exit(0);Object Foo() is never used again!8Challenges of Garbage Collection•Detecting the garbage is not always easy“if (complex_function(y)) x = Quux();”Run-time system cannot collect all of the garbage•Detecting the garbage introduces overheadKeeping track of references to objects (e.g., counter)Scanning through accessible objects to identify garbageSometimes walking through a large amount of memory•Cleaning the garbage leads to bursty delaysE.g., periodic scans of the objects to hunt for garbageLeading to unpredictable “freeze” of the running programVery problematic for real-time applications… though good run-time systems avoid long freezes9Option #2: Manual Deallocation•Programmer deallocates the memory (C and C++)Manually determines which objects can’t be accessedAnd the explicitly returns the resources to the heapE.g., using “free” in C or “delete” in C++•AdvantagesLower overheadNo unexpected “pauses” More efficient use of memory•DisadvantagesMore complex for the programmerSubtle memory-related bugsSecurity vulnerabilities in the (buggy) code10Manual Deallocation Can Lead to Bugs•Dangling pointersProgrammer frees a region of memory … but still has a pointer to itDereferencing pointer reads or writes nonsense valuesint main(void) { char *p; p = malloc(10); … free(p); … putchar(*p);}May print nonsense character.11Manual Deallocation Can Lead to Bugs•Memory leakProgrammer neglects to free unused region of memorySo, the space can never be allocated againEventually may consume all of the available memoryvoid f(void) { char *s; s = malloc(50); return;}int main(void) { while (1) f(); return 0;}Eventually, malloc() returns NULL12Manual Deallocation Can Lead to Bugs•Double freeProgrammer mistakenly frees a region more than onceLeading to corruption of the heap data structure… or premature destruction of a different objectint main(void) { char *p, *q; p = malloc(10); … free(p); q = malloc(10); free(p); …}Might free the space allocated to q!13Challenges for Malloc and Free•Malloc() may ask for an arbitrary number of bytes•Memory may be allocated & freed in different order•Cannot reorder requests to improve performancechar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);14Heap: Dynamic Memory #include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p115Heap: Dynamic Memory #include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p216Heap: Dynamic Memory #include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p2p317Heap: Dynamic Memory #include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p2p318Heap: Dynamic Memory #include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p2p3p419Heap: Dynamic Memory
View Full Document
Unlocking...