Class Note for CMPSCI 377 at UMass(26)
Class Note for CMPSCI 377 at UMass(26)
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 18 views.
Reviews for Class Note for CMPSCI 377 at UMass(26)
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 Memory Allocation 41 Dynamic Memory Management Usually memory for programs is allocated from a large pool of memory called the heap In C dynamic allocationdeallocation must be manually performed using library functions 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 wants with it The new command on the other hand allocates a speci c object and constructs it ie calls its C constructor if one exists The general way in which dynamic allocation is done is that the program asks the memory manager to allocate or free objects or multiple objects 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 411 Allocator issues Since most of the programs require a lot of memory allocationdeallocation we expect the memory man agement to be fast to have low fragmentation wasted space make good use of locality and be scalable to multiple processors 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 lie in between allocated objects internal fragmentation happens when there is waste of space inside an allocated area due to rounding the request size up to the nearest power of 2 or storing object headers containing the object size for example 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 but can leave small unusable chunks of memory in the heap and worst t takes memory from the largest hole and as a consequence keeps a lot of larger holes around As a general rule rst t is fastest but increases fragmentation One useful technique that can be applied with these methods is always to coalesce adjacent free objects into one big free objecti 42 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 eg one list for chunks of 8 bytes one for chunks of 16 and up in powers of 2 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 4 1 42 Chapter 4 Memory Allocation 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 first free slot inside that page Given a pointer to an object on a page we can find the header by masking off bits to find the start of the page With some care we can make BiBoP find and manage free slots of memory in Oli Also we can obviously never coalesce adjacent elements of the lists since then the very idea of segregating by size classes wouldnlt make sense anymorei 43 Custom memory allocation Some people write custom memory allocators to meet their specific 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 Ideally 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 Unfortunatly there are also some drawbacks regarding the use of custom memory allocators such as the fact that they seldom allow the use of memory debuggersi 44 Kinds of allocators We can imagine several types of memory allocatorsi Perclass allocators for instance are usefull when we know that welre going to allocate the same type of object again and again Then instead of segregating by object sizes ie maintaing a list for all 8 16 i i i 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 structureobjecti Perclass allocators are typically very fast and simple but might also be spaceinef cient Custom pattern allocators on the other hand are useful whenever we know welre going to have a specific type of allocation dynamicsi 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 deletei 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 pointeri Allocation and deallocation are Oli In fact this type of pattern allocator can be implemented just by bumping a pointer instead of performing linkedlist operationsi 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 n of memory cannot be reclaimed until we free the very last piece of occupied memory following ni Allocation can also be done using regions A region is a block of allocated memory that is only freed en masse That is the program allocates small objects from the region but no objects can be freed until the entire region is deallocatedi This is useful 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 donlt have to free each individual object created by 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 specific scenarios allocation by regions can be prone to programmer error if some object escapes its region and can be difficult to maintain Region allocators are used often in compilers where lots of objects die simultaneously at the end of an analysis phase As a nal remark notice that there is no single best allocator different types of programs perform differently Chapter 4 Memory Allocation under different types of allocators7 because of the ways they use memory7 their allocation patterns7 etC
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'