计算机系统基础：库函数

1从程序到可执行代码

库函数

2次课2DynamicMemoryAllocation3Mallocpackage#include<stdlib.h>void*malloc(size_tsize)voidfree(void*p)4Run-timeheap(createdatruntimebymalloc)5sbrk()Function#include<unistd.h>void*sbrk(intincr)6Run-timeheap(createdatruntimebymalloc)sbrk7Run-timeheap(createdatruntimebymalloc)sbrk8Run-timeheap(createdatruntimebymalloc)sbrk9p1=malloc(4*sizeof(long))p2=malloc(5*sizeof(long))p3=malloc(6*sizeof(long))free(p2)p4=malloc(2*sizeof(long))Allocationexamples10RequirementsHandlearbitrarysequenceofrequestsMakingimmediateresponsestorequestsUsingonlytheheapAligningblocksNotmodifyingallocatedblocks11GoalsGivensomesequenceofmallocandfreerequests:

R0,R1,...,Rk,...,Rn-1Wanttomaximizethroughputandpeakmemoryutilization.Thesegoalsareoftenconflicting12Performancegoals:throughputNumberofcompletedrequestsperunittimeExample:5,00malloccallsand5,00freecallsin1secondsthroughputis1,000operations/second.13Performancegoals:peakmemoryutilizationGivensomesequenceofmallocandfreerequests:

R0,R1,...,Rk,...,Rn-1Def:aggregatepayloadPk:malloc(p)resultsinablockwithapayloadofpbytes.AfterrequestRkhascompleted,theaggregatepayload

Pkisthesumofcurrentlyallocatedpayloads.14Performancegoals:peakmemoryutilizationDef:currentheapsizeisdenotedbyHkNotethatHkismonotonicallynondecreasing(canberelaxed)Def:peakmemoryutilization:Afterkrequests,peakmemoryutilizationis:Uk=(maxi<=kPi)/Hk15FragmentationPoormemoryutilizationcausedbyfragmentationTwoformsoffragmentationInternalfragmentationExternalfragmentation16InternalFragmentationInternalfragmentationForsomeblock,internalfragmentationisthedifferencebetweentheblocksizeandthepayloadsizepayloadInternalfragmentationblockInternalfragmentation17InternalFragmentationInternalfragmentationIscausedbyoverheadofmaintainingheapdatastructures,paddingforalignmentpurposes,orexplicitpolicydecisions(e.g.,nottosplittheblock).Dependsonlyonthepatternofpreviousrequests,andthusiseasytomeasure.18ExternalFragmentationOccurswhenthereisenoughaggregateheapmemory,butnosinglefreeblockislargeenoughp4=malloc(6*sizeof(long))19ExternalFragmentationExternalfragmentationdependsonthepatternoffuturerequestsandthusisdifficulttomeasure20KnowinghowMuchtoFreeStandardmethodkeepthelengthofastructureinthewordprecedingthestructureThiswordisoftencalledtheheaderfieldorheaderrequiresanextrawordforeveryallocatedstructure21KnowinghowMuchtoFreefree(p0)p0=malloc(4)p0Blocksizedata522ImplicitListNeedtoidentifywhethereachblockisfreeorallocatedCanuseextrabitBitcanbeputinthesamewordasthesizeifblocksizesarealwaysmultiplesof8(maskoutloworderbitwhenreadingsize).23Implicitlistsize1wordFormatofallocatedandfreeblockspayloada=1:allocatedblocka=0:freeblocksize:blocksizepayload:applicationdata(allocatedblocksonly)aoptionalpadding0024FindingaFreeBlockFirstfitNextfitBestfit25AllocatinginafreeblockAllocatinginafreeblock-splittingSinceallocatedspacemightbesmallerthanfreespace,wemightwanttosplittheblock26GettingAdditionalHeapMemoryWhentheallocatorisunabletofindafitfortherequestedblockTheallocatorasksthekernelforadditionalheapmemorybycallingsbrk()Theallocatortransformtheadditionalmemoryintoonelargefreeblockandinsertitintothefreelist27FreeingablockSimplestimplementation:OnlyneedtoclearallocatedflagButcanleadto“falsefragmentation”Thereisenoughfreespace,buttheallocatorwon’tbeabletofindit28CoalescingJoinwithnextand/orpreviousblockiftheyarefreeCoalescingwithnextblockButhowdowecoalescewithpreviousblock?29BidirectionalBoundarytags[Knuth73]replicatesize/allocatedwordatbottomoffreeblocksAllowsustotraversethe“list”backwards,butrequiresextraspaceImportantandgeneraltechnique!30Bidirectional444464641wordFormatofallocatedandfreeblocksa=1:allocatedblocka=0:freeblocksize:blocksizepayload:applicationdata(allocatedblocksonly)boundarytag(footer)headersizepayloadandpaddingasizea000031allocatedallocatedallocatedfreefreeallocatedfreefreeblockbeingfreedCase1Case2Case3Case4ConstantTimeCoalescing32m11m11n1n1m21m21m11m11n0n0m21m21ConstantTimeCoalescing(Case1)33m11m11n+m20n+m20m11m11n1n1m20m20ConstantTimeCoalescing(Case2)34m10m10n1n1m21m21n+m10n+m10m21m21ConstantTimeCoalescing(Case3)35m10m10n1n1m20m20n+m1+m20n+m1+m20ConstantTimeCoalescing(Case4)36DataStructure37ExplicitfreelistsExplicitlistamongthefreeblocksusingpointerswithinthefreeblocksUsedataspaceforlinkpointersTypicallydoublylinkedStillneedboundarytagsforcoalescingItisimportanttorealizethatlinksarenotnecessarilyinthesameorderastheblocks38ExplicitfreelistsABC4444664444ForwardlinksBacklinksABC39FreeingwithexplicitfreelistsWheretoputthenewlyfreedblockinthefreelistLIFO(last-in-first-out)policyinsertfreedblockatthebeginningofthefreelistpro:simpleandconstanttimecon:studiessuggestfragmentationisworsethanaddressordered.40FreeingwithexplicitfreelistsWheretoputthenewlyfreedblockinthefreelistAddress-orderedpolicyinsertfreedblockssothatfreelistblocksarealwaysinaddressorderi.e.addr(pred)<addr(curr)<addr(succ)con:requiressearchpro:studiessuggestfragmentationisbetterthanLIFO41SegregatedStorageMultiplefreelists,whereeachlistholdsblocksthatareroughlythesamesizeOftenhaveseparatecollectionforeverysmallsize(2,3,4,…)Forlargersizestypicallyhaveacollectionforeachpowerof242SegregatedStorage1-2345-89-1643freelistforeachsizeclasscontainssame-sizedblocksNosplittingToallocateablockofsizen:iffreelistforsizenisnotemptyallocatefirstblockonlistiffreelistisempty,getafixed-sizedchunkofadditionalmemorydividethechunkintoequal-sizedblockscreatenewfreelistfromallblocksinthechunkallocatefirstblockonlistconstanttimeSimplesegregatedstorage44Tofreeablock:AddtothebeginningofthefreelistTradeoffs:fast,butcanfragmentbadlyS