Class Note for CMPSCI 377 at UMass(54)
Class Note for CMPSCI 377 at UMass(54)
Popular in Course
Popular in Department
This 4 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Class Note for CMPSCI 377 at UMass(54)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 377 Operating Systems Lecturer Emery Berger Lecture 4 September 18 Spring 2007 Scribes Ryan Foley Stephen Brzozowskz39 41 Dynamic Memory Management The Heap When we need memory we grab it form the heap this process is accomplished with a heap managerl Heap manager implementations o C malloc free 0 C new delete Prettier versions of malloc and free 42 Ideal Memory Managers 0 Fast 7 Raw time asymtotic run time locality 7 Need at least Olog n if not constant time 0 Memory Efficient 7 Low fragmentation 7 Avoid paging from disk 0 Balance to be fast we could just allocate and never free out of memory 0 Scalable to multi core and multiprocessors 7 Difficult to do correctly 0 Secure from attack that would be screaming fast until we run 7 Buffer over ows Can allow malicious user to execute arbitrary code 0 Robustness 7 Must be reliable in the face of errors eg if you ask for 8 it gives 9 due to the common 77 Offbyone77 mistake 4 1 421 Allocating Memory Not just Mallocfree o realloc 7 Change size of object copying old contents 7 ptr reallocptr 10 7 reallocptr 0 77free77 reallocNULL 16 77malloc77 o calloc 7 Like malloc except the memory you are given is lled with Us 7 Secures information Since you can7t get at what was there 7 Takes longer because you need to write the 07s 0 memalign 7 Used for building your own memory allocator 7 Aligns request to particular address 7 Needs ability to locate size and object start 43 Fragmentation lntuitively fragmentation stems from breaking up heap into unusable spacesl More fragmentation worse utilization of memory 0 External Fragmentation wasted space outside of objects spaces between total memory memory postfreeing Hl l lllll l 1 1 1H 1 can t t this but could if reallocate Hl l ll 1 o lnternal Fragmentation wasted space inside an object Lecture 4 September 18 7 Assume memory manager gives an amount of memory with size nearest powerof2 if you ask for a size 8 object you get 8 bytes 0 wasted bytes no internal fragmentation if you ask for a size 9 object you get 16 bytes 7 wasted bytes about 43 internal fragme nation 96 if you ask for a size 17 object you get 32 bytes fragmentation o Framentation by a memory manager 7 Worst case K Olog Mm Where K is the total number of bytes M is the size of the biggest object In is the size of the smallest object Typical Case K 110 15 wasted bytes about 46 internal Lecture 4 September 18 4 3 44 Memory Management Algorithms 441 FirstFit Find the rst available chunk of memory large enough and allocate it ex 1 need 12 bytes l have 2 10 46 24 300 8 22 18 20 lterate through the list and when 1 hit 46 that7s large enough so grab it 0 Bene ts Simple o De ciencies Worst case linear On wasted memory with internal fragmentation 442 BestFit Find the smallest object of size greater than needed ex 1 need 12 bytes l have 2 10 46 24 300 8 22 18 20 lterate through the list and the one of size 18 is chosen 0 Bene ts minimizes wasted space both external and internal fragmentation o De ciencies SLOW Always linear On 443 WorstFit rarely used Grab the largest available piece of memory and carve off the size 1 need from it ex 1 need 12 bytes l have 2 10 46 24 300 8 22 18 20 iterate through the list and the one of size 300 is chosen 12 is carved off and allocated leaving 288 0 Bene ts minimizes internal fragmentation allocated objects are the right size 0 De ciencies leads to a lot of external fragmentation 4 4 Lecture 4 September 18 444 Constant time Keep an array7 each array index has a list of memory of the same size class 8 12 16 2o 24 28 32 64 128 1k 2k 4k v v v 1 1 1 If you want 8 bytes7 look up 87 give rst location7 remove it from available list Quick If you want 127 you can get 16 or get new memory from the OS and divide it up into 12s depends on implementation 445 Coalesce Reclaim space by coalescing free adjacent objects into one big object 0 Worst case A list where every other object is free This cannot be coalesced 45 Custom Allocators Typically a waste of time o Gnu allocator pretty 77damn77 fast 0 Windows allocator tons of tricks itemize 0 Can be inefficient o 77Premature Optimization is the root of all evil77
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'