动态内存分配实验报告-Malloc-Lab

动态内存分配实验报告MallocLab(DynamicStorageAllocators)07300720035电子信息科学与技术王泮渠（DepartmentofElectricalEngineering,ChrisWang)2010.01.02INTRODUCTIONInthislabyouwillbewritingadynamicstorageallocatorforCprogram,i.e.,yourownversionofthemalloc,freeandreallocroutines.Youareencouragedtoexplorethedesignspacecreativelyandimplementanallocatorthatiscorrect,efficientandfast.PREPARATIONSReadtheintroductionofmalloc_labcarefullyandthinkaboutitindepth.Itshowsushowtoontheprogram,howtocheckoursyntaxandgrammars,andhowtoevaluateourperformanceandfindhowtoimproveit.ThetextbookCSAPPisalwaysyourbestinstructorandhelper.ItprovidewithanoriginalversionofImplicitFreeList.Althoughitsperformanceisrelativelylow,itshowsthebasicprogramstructureandalgorithmaboutdynamicmemoryallocators.Also,wecangetfamiliarwithallfunctions,libraries,pointersandvariablesusedinthegiganticprogram.Weshouldcautiouslyselectouralgorithmanddatastructureusedintheprogramtomeetwiththerequestandevaluationsystemofmalloc_lab.Themostimportant,ourprogrammustberunontheserversuccessfully,smoothlyandefficientlywithoutanyerrors,bugsorleaks.ABOUTMYPROGRAMDATASTRUCTUREAsmentionedabove,theoriginalversionofimplicitfreelistintroducedinthetextbookisagoodgatewayprogram,butitcanbeonlythegateway,cannotbethesummit.Asweallknow,althoughimplicitfreelistissimple,asignificantdisadvantageisthatthecostofanyoperation,suchasplacingallocatedblocks,thatrequiresasearchofthefreelistwillbelinearinthetotalnumberofallocatedfreeblocksintheheap.Asaresult,implicitfreelistisnotappropriateforageneral-purposeallocator.SoIturnedtotheExplicitFreeList.Sincebydefinitionthebodyofafreeblockisnotneededbytheprogram,thepointersthatimplementthedatastructurecanbestoredwithinthebodiesofthefreeblocks.Usingadoubly-linkedlistinsteadofanimplicitfreelistreducesthefirstfitallocationtimefromlinearinthetotalnumberofblockstolinearinthenumberoffreeblocks.However,thetimetofreeablockcanbeeitherlinearorconstant,dependingonthepolicywechoosefororderingtheblocksinthefreelist.Inmyprogram,theessenceistofindthepolicy(datastructure)fororderingtheblocksinthefreelist.IselectthedatastructurenamedBINARYTREE.ThenameofBINARYTREEisnotunfamiliartous,sinceweallmeetwithitinthesecretphaseourourbomblab!Inmyprogram,weuseBINARYTREEtostoreourfreelist.Thatis,fromtheroot,nodesandtheleaves,eachonerepresentsoneKINDoffreelist.EverynodewhohavechildrenarecalledPARTENTS,andifonenodehasoneormoreblocksthathasthesamesizeofit,thenode,togetherwiththeblocks,arecalledBROTHERS.Theparentnodetypicallyhave2children,theLEFTchildandtheRIGHTchild.Wecanusethegraphbelowtodescribetherelationshipofallcharactersmentionedabove:WhenIputmystructureontoonelist,itwillappearasbelow:HeaderLeftptrRightptrPRNTBROSDataFooterHeaderLeftptr-1PRNTBROSDataFooterAscanbeseenfromabove,nodesdefinitelyhaveparents,brothersanditsleftandrightchild.However,thenode'sbrothersDONOThaveitsrightchild.Theirleftchildrenaretheclusteringlinestoshowtheirparalleledbutnotprivilegedstatustothenodes.Ifonenodeisdeleted,oneoftheirbrotherswillreplaceittobeparentsorchildren.So,alldatastructureofmyBINARYTREEwillrequireatleast24bytes.(oneblockrepresent4bytes,1word)FitStrategy(Algorithm)WewillchooseBESTFITstrategyformyprogram.Itexamineseveryfreeblockandselectsthefreeblockwiththesmallestsizethatfits.IfwecombinethebestfitstrategywiththeBINARYTREE,theoriginaldisadvantageforbestfit,thatisthecostoftimeforuttersearch,willbeeliminated.NODE0NODE1NODE2NODE5BLOCK1BLOCK2BLOCK1BLOCK1BLOCK2NODE3NODE4Left childRight childBROTHERSBROTHERSRoot && ParentLeft childRight childRight childParentParentParentBROTHERNodes:Brother:WecanpredictthatourBINARYTREEwillpossessfollowingpersonalities:1.Withrelativelyhighspeedinsearchingandallocating,thethroughputpertimewillbeenormous.2.AsweadoptBESTFITstrategy,thememoryutilizationwillbequitegood.However,eventhesmallestblockinthebinarytreecanbe24bytes,itmaycauserelativelyhighamountfragmentations.Howtobalancethemmustbeaninterestingbutcrucialissue.Now,let'sstartthethroughoutobservationofmycode!Firstly,wehavetodefinesomeconstantsandmacros:/*Constants*/#defineSSIZE4//Singleword,4bytes#defineDSIZE8//Doublewords,8bytes#defineTSIZE12//Triplewords,12bytes#defineQSIZE16//Quadriwords,16bytes#defineOVERHEAD8//Headerandfootersign,8bytes#defineALIGNMENT8//Alignmentrequest,8bytes#defineBLKSIZE24//Singleword,24bytes#defineCHUNKSIZE(112)//Initialheapsize#defineINISIZE1016//Heapextendedsize/*Macros*//*Maxandminvalueof2values*/#defineMAX(x,y)((x)(y)?(x):(y))#defineMIN(x,y)((x)(y)?(x):(y))/*Readandwriteawordataddressp*/#defineGET(p)(*(size_t*)(p))#definePUT(p,val)(*(size_t*)(p)=(val))/*Readthesizeandallocatedfieldsfromaddressp*/#defineSIZE(p)(GET(p)&~0x7)#definePACK(size,alloc)((size)|(alloc))#defineALLOC(p)(GET(p)&0x1)/*Givenpointerpatthesecondwordofthedatastructure,computeaddressesofitsHEAD,LEFT,RIGHT,PRNT,BROSandFOOTpointer*/#defineHEAD(p)((void*)(p)-SSIZE)#defineLEFT(p)((void*)(p))#defineRIGHT(p)((void*)(p)+SSIZE)#definePRNT(p)((void*)(p)+DSIZE)#defineBROS(p)((void*)(p)+TSIZE)#defineFOOT(p)((void*)(p)+SIZE(HEAD(p))-DSIZE)/*Makethebl