Class Note for CMPSCI 377 at UMass(18)
Class Note for CMPSCI 377 at UMass(18)
Popular in Course
Popular in Department
This 3 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 19 views.
Reviews for Class Note for CMPSCI 377 at UMass(18)
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 Spring 2009 Lecture 19 April 14 Lecturer Mark Corner Scribe Bruno Silva 191 Dynamic Memory Management Usually memory is allocated from a large pool of unused memory area called the heap In C dynamic allocationdeallocation must be manually performed using commands like malloc free new and delete Malloc allocates space of a given size and gives a pointer back to the programmer The programmer then can do whatever he or she wants with it The new command on the other hand allocates a speci c object of a given size The general way in which dynamic allocation is done is that the program asks the memory manager to allocate or free objects or multiple pages then the memory manager asks the OS to allocatefree pages or multiple pages Notice however that the allocator does not give the whole allocated page back to the program it just gives what it asked for The rest of the page ie the parts not given to the program is saved for future memory requestsi 192 Allocation techniques Since most of the programs require a lot of memory allocationdeallocation we expect the memory manage ment to be fast to have low fragmentation make good use of locality and be scalable to multiple processors Newer issues include security from attacks eigi use randomization of locations to minimize effect of buffer over ow attacks as well as reliability in the face of errors eigi detecting double free 5 and buffer overruns In analyzing the speed of an allocator the key components are the cost of malloc the cost of free and the cost of getting the size of an object for realloci In certain types of programs for instance those with a lot of graphics manipulation allocators can become the performance bottleneck and so speed is important We say that fragmentation occurs when the heap due to characteristics of the allocation algorithm gets broken up77 into several unusable spaces or when the overall utilization of the memory is compromised External fragmentation happens when there is waste of space outside ie in between allocated objects internal fragmentation happens when there is waste of space inside an allocated areal Remember that the allocator might at any single time have several pages with unused space from which it could draw pieces of memory to give to requesting programs There are several ways to decide what are the good spots among those with free memory from which to take memory The rst t method nds the rst chunk of desired size and returns it it is generally considered to be very fast best t nds the chunk that wastes the least of space and worst t takes memory from the largest existent spot and as a consequence maximizes the free space available As a general rule rst t is faster but increases fragmentationi One useful technique that can be applied with these methods is always to coalesce free adjacent objects into one big free objecti 191 192 Lecture 19 April 14 193 Keeping track of free memory How do we keep track of where the free pieces of memory are One idea is to maintain a set of linkedlists of free space each linkedlist will store free chunks of some given size say one list for chunks of 4 bytes one for chunks of 8 16 etc This approach resembles the best t algorithm since we can easily nd the list with chunks of memory that are the closest to what we need the difference of course is that usually the linked lists store not objects of arbitrary size but only powers of two Also we can never coalesce adjacent elements of the lists or split elements since then the very idea of segregating by size classes wouldnlt make sense anymore Another possible technique to keep track of free memory is called Big Bag of Pages BiBOP In this technique a bunch of pages usually segregated by size classes is maintained such that there is a header on each page on this header among other things we can nd a pointer to the next page of objects of that given size and also a pointer to the rst free slot inside that page Using the right optimizations we can make BiBOP nd and manage free slots of memory in 01 194 Custom memory allocation Some people write custom memory allocators to meet their speci c needs Although this is not needed for most of the applications it is also not uncommon The goal of course is to replace the OS allocator in an optimized version that deals more efficiently with the most frequently used data structures of some given application ldeally we expect the new allocator to require reduced runtime provide expanded functionality sometimes and run on reduced space rarely Examples of applications that use custom allocators are the Apache webserver GCC the STL and most database servers Unfortunately there are also some drawbacks regarding the use of custom memory allocators such as the increased burden on programmers as well as the fact that they seldom allow the use of standard memory debuggers 195 Kinds of allocators We can imagine several types of memory allocators Perclass allocators for instance are useful when we know that we7re going to allocate the same type of object again and again Then instead of segregating by object sizes ie maintaining a list for all 8 l6 byte objects we can create a list of memory slots for objects of say 18 bytes This can be seen as a big pool of free memory chunks used by some commonly occurring structureobject Perclass allocators are typically very fast and simple but might also be spaceinefficient An example is the slab allocator77 in the Linux kernel Custom patterns allocators on the other hand are useful whenever we know were going to have a speci c type of allocation dynamics For instance suppose we know that well always have to allocate a lot of objects and then well delete them all but we will never allocate anything after we started deleting eg alloc alloc delete delete delete In this case a custom pattern allocator could simply use a stack and a pointer to the last occupied position of that stack then when allocating we can just request the size of the object from the memory pointed to by our pointer Allocation and deallocation are 01 In fact this type of pattern allocator can be implement using pointerbumping ie by just moving pointers instead of performing crazy linkedlist operations Notice that if we use this type allocator ie one that assumes a speci c pattern of allocation on some program that does not exhibit that pattern we can end up with tons of unused memory since a free slot a of memory cannot be reclaimed until we free the very last piece of occupied memory following a Lecture 19 April 14 193 Allocation can also be done using regions The idea in this case is to create a big blob of free memory called a region We then de ne that deletion in that region will only occur en masse that is for all objects inside the region This is interesting if we are dealing with modular applications eg a web browser that has to load a plugin and then free all the memory used by that plugini In this case we don7t have to dealloc each individual object of the plugin in fact we don t care what are the objects used internally by the plugin We can simply delete all the region of memory used by it Although very fast when dealing with these speci c scenarios allocation by regions is very prone to programmer errors and are signi cantly nontrivial ie a pain to maintain As a nal remark notice that there is no single best allocator different types of programs perform wildly different under different types of allocators because of the ways they use memory their patterns of allocation etci
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'