Consider
Starting with 160 k of memory do:Allocate p1 (50 k)Allocate p2 (30 k)Allocate p3 (40 k)Free p2Allocate p4 (40 k)Free p3Allocate p5 (60 k)Free p1Allocate p6 (30k)
Memory Allocation Algorithms
Design YOUR algorithm for allocation and deallocation of memory
Memory Management
Dynamic (heap)Significant issuesSignificant execution time (16%)Memory performance not uniformAllocation policiesBugsDereference problemsMemory leaks
Memory Allocation Strategies
Explicit vs. Implicit Memory AllocatorGeneral purpose vs. custom allocatorSoftware vs. hardware
Allocation Examples
p1 = malloc(4)
p2 = malloc(5)
p3 = malloc(6)
free(p2)
p4 = malloc(2)
Goals of Good malloc/free
Good execution-time performanceGood space utilizationGood locality properties
Fragmentation
Poor memory utilization ---fragmentationInternal – overhead associated with a block of memoryExternal – have enough blocks of memory for a request, but not contiguous
Space in use
Internalfragmentation
External Fragmentation
p1 = malloc(4)
p2 = malloc(5)
p3 = malloc(6)
free(p2)
p4 = malloc(6)
External fragmentation depends onfuturerequests;thus difficult to anticipate
Bidirectional Coalescing
Boundary tags[Knuth73]Replicate size/allocated word at bottom of free blocksAllows us to traverse the“list”backwards, but requires extra spaceImportant and general technique!
Boundary Tags
size
1 word
Format ofallocated andfree blocks
ApplicationMemory(and padding?)
a = 1: allocated blocka = 0: free blocksize: total block sizeApplication memory(allocated blocks only)
a
size
a
Boundary tag(footer)
4
4
4
4
6
4
6
4
Header
Your turn
Using boundary tag data structure, define algorithms for:AllocationFree
Key Allocator Policies
Placement policy:First fit, worst fit, best fit, etc.Trades off lower throughput for less fragmentationSplitting policy:When do we go ahead and split free blocks?How much internal fragmentation are we willing to tolerate?Coalescing policy:Immediate coalescing: coalesce adjacent blocks each time free is calledDeferred coalescing: try to improve performance of free by deferring coalescing until needed. e.g.,
Refinements
Separate listsBinary buddyLea allocatorCustom allocators
Lea Allocator
An approximate best-fit allocator with different behavior based on object sizeSmall Objects (<64 bytes) allocated by exact-size quicklistsMedium Objects (<128K) –coalescequicklistsLarge Objects – allocate and free bymmapGenerally considered the best allocator known (as of 2000, anyway)http://g.oswego.edu/dl/html/malloc.html
Why programmers use Custom Allocators?
Improving runtime performanceReducing memory consumptionImproving software engineering (?)
Alternative Memory Management
Region (arenas)Reserve memory blocks for program“parts”Deallocate entire regions, not per allocationGarbage collectionProgrammer allocates but doesn’t free“System”keeps track of memory“pointed to”locations, removes the restJava
Why Garbage Collect at All?
SafetyMemory leaksContinued use of freed pointersSimplicityCorrectnessProgramming ease
The Two-Phase Abstraction
1. Detection2. Reclamation
Liveness and Garbage
There is a root set which is defined as live.Anything reachable from a live pointer is also liveEverything else is garbage
The Root Set
The Root SetStatic global and module variablesLocal VariablesVariables on any activation stack(s)Everyone elseAnything Reachable From a live value
Reference Counting
Each allocated chunk has reference count that shows how many locations point (refer) to this one.Advantages ???Disadvantages ???
Mark-Sweep Collection
Starting from the root set traverse all pointers via depth/breadth first search.Free everything that is not marked.
More Information/Detail
If you wish to know more:https://www.mpi-inf.mpg.de/departments/rg1/teaching/advancedc-ws08/script/lecture09.pdf
0
Embed
Upload