New version page

UGA CSCI 2720 - memory

Documents in this Course
Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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


View Full Document
Download memory
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 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 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?