DOC PREVIEW
Berkeley COMPSCI 61C - Memory Management

This preview shows page 1-2-3-19-20-39-40-41 out of 41 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Memory Management (1/2)Memory Management (2/2)The Stack (1/4)The Stack (2/4)The Stack (3/4)The Stack (4/4): Dangling PointersStatic and Code SegmentsThe Heap (Dynamic memory)Memory ManagementHeap Management RequirementsHeap ManagementSlide 13K&R Malloc/Free ImplementationK&R ImplementationChoosing a block in malloc()PRS Round 1Tradeoffs of allocation policiesAdministriviaSlab AllocatorSlide 21Slide 22Slab Allocator TradeoffsInternal vs. External FragmentationBuddy SystemSlide 26Allocation SchemesAutomatic Memory ManagementTracking Memory UsageSlide 30Scheme 1: Reference CountingReference Counting ExampleSlide 33Reference Counting (p1, p2 are pointers)Reference Counting FlawsScheme 2: Mark and Sweep Garbage Col.Mark and SweepScheme 3: Copying Garbage CollectionPRS Round 2Summary (1/2)Summary (2/2)CS 61C L05 Memory Management (1)A Carle, Summer 2005 © UCB inst.eecs.berkeley.edu/~cs61c/su05CS61C : Machine Structures Lecture #5: Memory Management2005-06-27Andy CarleCS 61C L05 Memory Management (2)A Carle, Summer 2005 © UCBMemory 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 heapint myGlobal;main() { int myTemp; int *f= malloc(16);}CS 61C L05 Memory Management (3)A Carle, Summer 2005 © UCBMemory Management (2/2)•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~ 0hexCS 61C L05 Memory Management (4)A Carle, Summer 2005 © UCBThe Stack (1/4)•Terminology:•Stack is composed of frames•A frame corresponds to one procedure invocation•Stack frame includes:-Return address of caller-Space for other local variables•When procedure ends, stack frame is tossed off the stack; frees memory for future stack framesframeframeframeframe$SPCS 61C L05 Memory Management (5)A Carle, Summer 2005 © UCBThe 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 callerframeframeframeframe$SPCS 61C L05 Memory Management (6)A Carle, Summer 2005 © UCBThe Stack (3/4)•Last In, First Out (LIFO) memory usagemain (){ 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 PointerCS 61C L05 Memory Management (7)A Carle, Summer 2005 © 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; stackAddr = ptr();printf("%d", *stackAddr); /* 3 */printf("%d", *stackAddr); /* XXX */}The Stack (4/4): Dangling Pointersmainptr()(y==3)SPmainSPmainprintf()(y==?)SPCS 61C L05 Memory Management (8)A Carle, Summer 2005 © UCBStatic 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 knownCS 61C L05 Memory Management (9)A Carle, Summer 2005 © UCBThe 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 heapCS 61C L05 Memory Management (10)A Carle, Summer 2005 © 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 timeCS 61C L05 Memory Management (11)A Carle, Summer 2005 © 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.CS 61C L05 Memory Management (12)A Carle, Summer 2005 © 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)CS 61C L05 Memory Management (13)A Carle, Summer 2005 © 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?CS 61C L05 Memory Management (14)A Carle, Summer 2005 © 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 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 blockCS 61C L05 Memory Management (15)A Carle, Summer 2005 © UCBK&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 listCS 61C L05 Memory Management (16)A Carle, Summer 2005 © UCBChoosing 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


View Full Document

Berkeley COMPSCI 61C - Memory Management

Documents in this Course
SIMD II

SIMD II

8 pages

Midterm

Midterm

7 pages

Lecture 7

Lecture 7

31 pages

Caches

Caches

7 pages

Lecture 9

Lecture 9

24 pages

Lecture 1

Lecture 1

28 pages

Lecture 2

Lecture 2

25 pages

VM II

VM II

4 pages

Midterm

Midterm

10 pages

Load more
Download Memory Management
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Memory Management and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Memory Management 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?