AdministriviaDynamic memory allocationWhy is it hard?More abstractlyWhat is fragmentation really?Important decisionsImpossible to ``solve'' fragmentationPathological examplesPathological examplesPathological examplesBest fitBest fit gone wrongFirst fitSubtle pathology: LIFO FFFirst fit: NuancesFirst fit: NuancesFirst/best fit: weird parallelsSome worse ideasSlab allocation href {http://usenix.org/publications/library/proceedings/bos94/bonwick.html}{[Bonwick]}Known patterns of real programsPattern 1: rampsPattern 2: peaksExploiting peaksPattern 3: PlateausFighting fragmentationSimple, fast segregated free listsTypical space overheadsGetting more space from OSFaults + resumption = powerMore fault resumption examplesNot just for kernelsDistributed shared memoryPersistent storesGarbage collectionConcurrent garbage collectionHeap overflow detectionHeap overflow detection 2Reference countingReference counting pros/consAdministrivia• Project 2 due right now- As before, free extension if you are here- For SCPD students, put this at top of design doc: caf656- For non-SCPD students, put this:• Midterm Tuesday- Open book, open notes (but not open notebook computer)- Covers first 10 lectures of course (including today)•Midterm review section tomorrow• Section for Project 3 next Friday• I will monitor newsgroup/list for questions- Please put “[midterm]” in subject of questions about midterm1/36Dynamic memory allocation• Almost every useful program uses it- Gives wonderful functionality benefits⊲ Don’t have to statically specify complex data structures⊲ Can have data grow as a function of input size⊲ Allows recursive procedures (stack growth)- But, can have a huge impact on performance• Today: how to implement it- Lecture draws on [Wilson] (good survey from 1995)• Some interesting facts:- Two or three line code change can have huge, non-obviousimpact on how well allocator works (examples to come)- Proven: impossible to construct an ”always good” allocator- Surprising result: after 35 years, memory management stillpoorly understood2/36Why is it hard?• Satisfy arbitrary set of allocation and free’s.• Easy without free: set a pointer to the beginning ofsome big chunk of memory (“heap”) and incrementon each allocation:• Problem: free creates holes (“fragmentation”) Result?Lots of free space but cannot satisfy request!3/36More abstractly• What an allocator must do:- Track which parts of memory in use, which parts are free- Ideal: no wasted space, no time overhead• What the allocator cannot do:- Control order of the number and size of requested blocks- Change user ptrs =⇒ (bad) placement decisions permanent• The core fight: minimize fragmentation- App frees blocks in any order, creating holes in “heap”- Holes too small? cannot satisfy future requests4/36What is fragmentation really?• Inability to use memory that is free• Two factors required for fragmentation- Different lifetimes—if adjacent objects die at different times, thenfragmentation:- If they die at the same time, then no fragmentation:- Different sizes: If all requests the same size, then no fragmentation(that’s why no external fragmentation w. paging):5/36Important decisions• Placement choice: where in free memory to put arequested block?- Freedom: can select any memory in the heap- Ideal: put block where it won’t cause fragmentation later(impossible in general: requires future knowledge)• Split fre e blocks to satisfy smaller requests?- Fights internal fragmentation- Freedom: can chose any larger block to split- One way: chose block with smallest remainder (best fit)• Coalescing free blocks to yield larger blocks- Freedom: when to coalesce (deferring can be good) fightsexternal fragmentation6/36Impossible to “solve” fragmentation• If you read allocation papers to find the best allocator- All discussions revolve around tradeoffs- The reason? There cannot be a best allocator• Theoretical result:- For any possible allocation algorithm, there exist streams ofallocation and deallocation requests that defeat the allocatorand force it into severe fragmentation.• How much fragmentation should we tolerate?- Let M = bytes of live data, nmin= smallest allocation,nmax= largest – How much gross memory required?- Bad allocator: M · (nmax/nmin)(only ever uses a memory location for a single size)- Good allocator: ∼ M · log(nmax/nmin)7/36Pathological examples• Given allocation of 7 20-byte chunks- What’s a bad stream of frees and then allocates?- Free every other chunk, then alloc 21 bytes• Given a 128-byte limit on malloced space- What’s a really bad combination of mallocs & frees?- Malloc 128 1-byte chunks, free every other- Malloc 32 2-byte chunks, free every other (1- & 2-byte) chunk- Malloc 16 4-byte chunks, free every other chunk. ..• Next: two allocators (best fit, first fit) that, in practice,work pretty well- “pretty well” = ∼20% fragmentation under many workloads8/36Pathological examples• Given allocation of 7 20-byte chunks- What’s a bad stream of frees and then allocates?- Free every other chunk, then alloc 21 bytes• Given a 128-byte limit on malloced space- What’s a really bad combination of mallocs & frees?- Malloc 128 1-byte chunks, free every other- Malloc 32 2-byte chunks, free every other (1- & 2-byte) chunk- Malloc 16 4-byte chunks, free every other chunk. ..• Next: two allocators (best fit, first fit) that, in practice,work pretty well- “pretty well” = ∼20% fragmentation under many workloads8/36Pathological examples• Given allocation of 7 20-byte chunks- What’s a bad stream of frees and then allocates?- Free every other chunk, then alloc 21 bytes• Given a 128-byte limit on malloced space- What’s a really bad combination of mallocs & frees?- Malloc 128 1-byte chunks, free every other- Malloc 32 2-byte chunks, free every other (1- & 2-byte) chunk- Malloc 16 4-byte chunks, free every other chunk. ..• Next: two allocators (best fit, first fit) that, in practice,work pretty well- “pretty well” = ∼20% fragmentation under many workloads8/36Best fit• Strategy: minimize fragmentation by allocatingspace from block that leaves smallest fragment- Data structure: heap is a list of free blocks, each has a headerholding block size and pointers to next- Code: Search freelist for block closest in size to the request.(Exact match is ideal)- During free (usually) coalesce adjacent blocks• Problem: Sawdust-
View Full Document
Unlocking...