Memory ManagementWhat is memory management?TerminologyWhat’s a good MM scheme?Fixed v. varying size blocksLinked v. unlinkedIf unlinked, thenSmall v. largeTime v. memoryExplicit v. implicit releaseScheduled v. unscheduled releaseInitialized v. uninitialized blocksRecords of a single sizeSlide 14Reference countsSlide 16Reference CountsSlide 18What else can we do?Memory ManagementCSCI 2720Spring 2005What is memory management?“the prudent utilization of this scarce resource (memory), whether by conservation, recycling, or other strategies.”Terminologyheap** - a table M[0..N-1] of N cellsSmaller blocks of memory are allocated from this heapAn allocated block is said to be reserved or in useThe allocated block may later be freed or deallocated.** -- no relation to the partially ordered, implicitly represented tree we just talked about in class.What’s a good MM scheme?It depends:Blocks of fixed size v. varying sizeLinked blocks v. unlinked blocksSmall blocks v. large blocksTime v. memoryExplicit v. implicit releaseScheduled v. unscheduled releaseInitialized v. uninitialized blocksFixed v. varying size blocksIf fixed, or large number of same size, makes sense to set aside a heap for those requestsFixed-size easier to manageLinked v. unlinkedIf linked then can’t arbitrarily move blocks:Example:Can’t relocate B without breaking AA BIf unlinked, thenProgram AProgram BProgram CProgram AProgram BProgram CProgram DSmall v. largeMay need to handle a few bytes … or megabytesSmall blocks –May make sense to move, zero out, etc.Large blocksWant to avoid operations whose performance depends on size of blockTime v. memoryWhich are you optimizing?If you can “waste” some memory (have a large heap), then may be able to use faster management algorithms.If memory is scarce, may need more time-consuming algorithms.Explicit v. implicit releaseDoes “user” notify memory manager when memory is no longer needed by program?Garbage = memory that MM has allocated, but that is no longer referenced by any variable that can/will be accessed by client.When can MM reclaim memory?Scheduled v. unscheduled releaseMemory manager can benefit from knowing order in which memory will be released.(For example: if release is LIFO, can use a stack.)Initialized v. uninitialized blocksInitialize to all zeros to meet semantics of programming language.Initialize for security purposes.… but takes time proportional to size of block.Records of a single sizeGiven heap of memory M[0..N-1], if records are all of same size k, can partition at init into a table of cells of size k, T[0..m-1], where m = floor(N/k)For any allocation request, return some T[i]At any time, some cells are in use, some are free; no particular order or pattern to their statusRecords of a single sizeMaintain a free list: singly linked list of cells not in use. No additional memory needed, can use part of cell as pointer to next chunk. Assumes size(cell) > size(pointer)Access as a stack: Pop to allocate, Push on deallocation, thus (1).Garbage collection problem remains: when is a chunk available to be reclaimed?Reference countsSuppose we have:47xyyReference countsEach time the address of a cell is copied, we have another “use” of that memory locationCan’t deallocate until all copies of the address have been destroyed.Method for keeping track of the use of cells: maintain a reference count for each cellReference Countsxy47Reference CountsCons:Lots of machinery:P <- Q requiresDecrement ref count of *PIf *P is now 0, deallocateIncrement *Q Requires memory in cells for ref countAnd how big should it be??Circularity a problemWhat else can we do?Mark and sweep garbage