Dynamic Memory Allocation IHarsh RealityDynamic Memory AllocationProcess Memory ImageMalloc PackageMalloc ExampleAssumptionsAllocation ExamplesConstraintsGoals of Good malloc/freePerformance Goals: ThroughputPerformance Goals: Peak Memory UtilizationInternal FragmentationExternal FragmentationImplementation IssuesKnowing How Much to FreeKeeping Track of Free BlocksMethod 1: Implicit ListImplicit List: Finding a Free BlockImplicit List: Allocating in Free BlockImplicit List: Freeing a BlockImplicit List: CoalescingImplicit List: Bidirectional CoalescingConstant Time CoalescingConstant Time Coalescing (Case 1)Constant Time Coalescing (Case 2)Constant Time Coalescing (Case 3)Constant Time Coalescing (Case 4)Summary of Key Allocator PoliciesImplicit Lists: SummaryDynamic Memory Allocation IDynamic Memory Allocation ITopicsTopicsSimple explicit allocatorsData structuresMechanismsPoliciesdmem1.pptCS 105“Tour of the Black Holes of Systems!”– 2 –CS 105Harsh RealityHarsh RealityMemory MattersMemory MattersMemory is not unboundedMemory is not unboundedIt must be allocated and managedMany applications are memory-dominatedEspecially those based on complex, graph algorithmsMemory referencing bugs especially perniciousMemory referencing bugs especially perniciousEffects are distant in both time and spaceMemory performance is not uniformMemory performance is not uniformCache and virtual-memory effects can greatly affect program performanceAdapting program to characteristics of memory system can lead to major speed improvements– 3 –CS 105Dynamic Memory AllocationDynamic Memory AllocationExplicit vs. Implicit Memory AllocatorExplicit vs. Implicit Memory AllocatorExplicit: application allocates and frees space E.g., malloc and free in CImplicit: application allocates, but does not free spaceE.g. garbage collection in Java, ML or LispAllocationAllocationIn both cases the memory allocator provides an abstraction of memory as a set of blocksDoles out free memory blocks to applicationDone by run-time system (in user mode)ApplicationDynamic Memory AllocatorHeap Memory– 4 –CS 105Process Memory ImageProcess Memory Imagekernel virtual memoryMemory mapped region forshared librariesrun-time heap (via malloc)program text (.text)initialized data (.data)uninitialized data (.bss)stack0%espmemory invisible to user codethe “brk” ptrAllocators requestadditional heap memoryfrom the operating system using the sbrk function.– 5 –CS 105Malloc PackageMalloc Package#include <stdlib.h>#include <stdlib.h>void *malloc(size_t size)void *malloc(size_t size)If successful:Returns a pointer to a memory block of at least size bytes, (typically) aligned to 8-byte boundary.If size == 0, returns NULLIf unsuccessful: returns NULL (0) and sets errno.void free(void *p)void free(void *p)Returns the block pointed at by p to pool of available memoryp must come from a previous call to malloc or realloc.NULL not a legal argument (sigh)void *realloc(void *p, size_t size)void *realloc(void *p, size_t size) Changes size of block p and returns pointer to new block.Contents of new block unchanged up to min of old and new size.– 6 –CS 105Malloc ExampleMalloc Examplevoid foo(int n, int m) { int i, *p; /* allocate a block of n ints */ if ((p = (int *) malloc(n * sizeof(int))) == NULL) { perror("malloc"); exit(0); } for (i = 0; i < n; i++) p[i] = i; /* add m bytes to end of p block */ if ((p = (int *) realloc(p, (n+m) * sizeof(int))) == NULL) { perror("realloc"); exit(0); } for (i = n; i < n+m; i++) p[i] = i; /* print new array */ for (i = 0; i < n+m; i++) printf("%d\n", p[i]); free(p); /* return p to available memory pool */}– 7 –CS 105AssumptionsAssumptionsAssumptions made in this lectureAssumptions made in this lectureMemory is word addressed (each word can hold a pointer)Allocated block(4 words)Free block(3 words)Free wordAllocated word– 8 –CS 105Allocation ExamplesAllocation Examplesp1 = malloc(4)p2 = malloc(5)p3 = malloc(6)free(p2)p4 = malloc(2)– 9 –CS 105ConstraintsConstraintsApplications:Applications:Can issue arbitrary sequence of allocation and free requestsFree requests must correspond to an allocated block – pointer must be correctAllocatorsAllocatorsCan’t control number or size of allocated blocksMust respond immediately to all allocation requestsi.e., can’t reorder or buffer requestsMust allocate blocks from free memoryi.e., can only place allocated blocks in free memoryMust align blocks so they satisfy all alignment requirements8 byte alignment for GNU malloc (libc malloc) on Linux boxesCan only manipulate and modify free memoryCan’t move the allocated blocks once they are allocatedi.e., compaction is not allowed– 10 –CS 105Goals of Good malloc/free Goals of Good malloc/free Primary goalsPrimary goalsGood time performance for malloc and freeIdeally should take constant time (not always possible)Should certainly not take linear time in the number of blocksGood space utilizationUser allocated structures should be large fraction of the heap.Want to minimize “fragmentation”.Some other goalsSome other goalsGood locality propertiesStructures allocated close in time should be close in space“Similar” objects should be allocated close in spaceRobustCan check that free(p1) is on a valid allocated object p1 – don’t free it twice, or free some other ptr…Can check that memory references are to allocated space– 11 –CS 105Performance Goals: ThroughputPerformance Goals: ThroughputGiven some sequence of malloc and free requests:Given some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1Want to maximize throughput and peak memory Want to maximize throughput and peak memory utilization.utilization.These goals are often conflictingThroughput:Throughput:Number of completed requests per unit timeExample:5,000 malloc calls and 5,000 free calls in 10 seconds Throughput is 1,000 operations/second.– 12 –CS 105Performance Goals: Peak Memory UtilizationPerformance Goals: Peak Memory UtilizationGiven some sequence of malloc and free requests:Given some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1Def: Aggregate payload PDef: Aggregate payload Pkk: : malloc(p) results in a block with a payload of p bytes.. After request Rk has
View Full Document
Unlocking...