英文版--存储系统(参考)ppt课件

Chapter6Memory.Chapter6ObjectivesMastertheconceptsofhierarchicalmemoryorganization.Understandhoweachlevelofmemorycontributestosystemperformance,andhowtheperformanceismeasured.Mastertheconceptsbehindcachememory,virtualmemory,memorysegmentation,pagingandaddresstranslation..6.1IntroductionMemoryliesattheheartofthestored-programcomputer.Inpreviouschapters,westudiedthecomponentsfromwhichmemoryisbuiltandthewaysinwhichmemoryisaccessedbyvariousISAs.Inthischapter,wefocusonmemoryorganization.Aclearunderstandingoftheseideasisessentialfortheanalysisofsystemperformance..6.2TypesofMemoryTherearetwokindsofmainmemory:randomaccessmemory,RAM,andread-only-memory,ROM.TherearetwotypesofRAM,dynamicRAM(DRAM)andstaticRAM(SRAM).DynamicRAMconsistsofcapacitorsthatslowlyleaktheirchargeovertime.Thustheymustberefreshedeveryfewmillisecondstopreventdataloss.DRAMis“cheap”memoryowingtoitssimpledesign..6.2TypesofMemorySRAMconsistsofcircuitssimilartotheDflip-flopthatwestudiedinChapter3.SRAMisveryfastmemoryanditdoesn’tneedtoberefreshedlikeDRAMdoes.Itisusedtobuildcachememory,whichwewilldiscussindetaillater.ROMalsodoesnotneedtoberefreshed,either.Infact,itneedsverylittlechargetoretainitsmemory.ROMisusedtostorepermanent,orsemi-permanentdatathatpersistsevenwhilethesystemisturnedoff..6.3TheMemoryHierarchyGenerallyspeaking,fastermemoryismoreexpensivethanslowermemory.Toprovidethebestperformanceatthelowestcost,memoryisorganizedinahierarchicalfashion.Small,faststorageelementsarekeptintheCPU,larger,slowermainmemoryisaccessedthroughthedatabus.Larger,(almost)permanentstorageintheformofdiskandtapedrivesisstillfurtherfromtheCPU..6.3TheMemoryHierarchyThisstorageorganizationcanbethoughtofasapyramid:.6.3TheMemoryHierarchyToaccessaparticularpieceofdata,theCPUfirstsendsarequesttoitsnearestmemory,usuallycache.Ifthedataisnotincache,thenmainmemoryisqueried.Ifthedataisnotinmainmemory,thentherequestgoestodisk.Oncethedataislocated,thenthedata,andanumberofitsnearbydataelementsarefetchedintocachememory..6.3TheMemoryHierarchyThisleadsustosomedefinitions.Ahitiswhendataisfoundatagivenmemorylevel.Amissiswhenitisnotfound.Thehitrateisthepercentageoftimedataisfoundatagivenmemorylevel.Themissrateisthepercentageoftimeitisnot.Missrate=1-hitrate.Thehittimeisthetimerequiredtoaccessdataatagivenmemorylevel.Themisspenaltyisthetimerequiredtoprocessamiss,includingthetimethatittakestoreplaceablockofmemoryplusthetimeittakestodeliverthedatatotheprocessor..6.3TheMemoryHierarchyAnentireblocksofdataiscopiedafterahitbecausetheprincipleoflocalitytellsusthatonceabyteisaccessed,itislikelythatanearbydataelementwillbeneededsoon.Therearethreeformsoflocality:Temporallocality-Recently-accesseddataelementstendtobeaccessedagain.Spatiallocality-Accessestendtocluster.Sequentiallocality-Instructionstendtobeaccessedsequentially..6.4CacheMemoryThepurposeofcachememoryistospeedupaccessesbystoringrecentlyuseddataclosertotheCPU,insteadofstoringitinmainmemory.Althoughcacheismuchsmallerthanmainmemory,itsaccesstimeisafractionofthatofmainmemory.Unlikemainmemory,whichisaccessedbyaddress,cacheistypicallyaccessedbycontent;hence,itisoftencalledcontentaddressablememory.Becauseofthis,asinglelargecachememoryisn’talwaysdesirable--ittakeslongertosearch..6.4CacheMemoryThe“content”thatisaddressedincontentaddressablecachememoryisasubsetofthebitsofamainmemoryaddresscalledafield.Thefieldsintowhichamemoryaddressisdividedprovideamany-to-onemappingbetweenlargermainmemoryandthesmallercachememory.Manyblocksofmainmemorymaptoasingleblockofcache.Atagfieldinthecacheblockdistinguishesonecachedmemoryblockfromanother..6.4CacheMemoryThesimplestcachemappingschemeisdirectmappedcache.InadirectmappedcacheconsistingofNblocksofcache,blockXofmainmemorymapstocacheblockY=XmodN.Thus,ifwehave10blocksofcache,block7ofcachemayholdblocks7,17,27,37,...ofmainmemory.Onceablockofmemoryiscopiedintoitsslotincache,avalidbitissetforthecacheblocktoletthesystemknowthattheblockcontainsvaliddata.Whatcouldhappenwithouthavingavalidbit?.6.4CacheMemoryThediagrambelowisaschematicofwhatcachelookslike.Block0containsmultiplewordsfrommainmemory,identifiedwiththetag00000000.Block1containswordsidentifiedwiththetag11110101.Theothertwoblocksarenotvalid..6.4CacheMemoryThesizeofeachfieldintowhichamemoryaddressisdivideddependsonthesizeofthecache.Supposeourmemoryconsistsof214words,cachehas16=24blocks,andeachblockholds8words.Thusmemoryisdividedinto214/28=211blocks.Forourfieldsizes,weknowweneed4bitsfortheblock,3bitsfortheword,andthetagiswhat’sleftover:.6.4CacheMemoryAsanexample,supposeaprogramgeneratestheaddress1AA.In14-bitbinary,thisnumberis:00000110101010.Thefirst7bitsofthisaddressgointhetagfield,thenext4bitsgointheblockfield,andthefinal3bitsindicatethewordwithintheblock..6.4CacheMemoryIfsubsequentlytheprogramgeneratestheaddress1AB,itwillfindthedataitislookingforinblock0101,word011.However,iftheprogramgeneratestheaddress,3AB,instead,theblockloadedforaddress1AAwouldbeevictedfromthecache,andreplacedbytheblocksassociatedwiththe3ABreference..6.4CacheMemorySupposeaprogramgeneratesaseriesofmemoryreferencessuchas:1AB,3AB,1AB,3AB,...Thecachewillcontinuallyevictandreplaceblocks.Thetheoreticaladvantageofferedbythecacheislostinthisextremecase.Thisisthemaindisadvantageofdirectmappedcache.Othercachemappingschemesaredesignedtopreventthiskindofthrashing..6.4CacheMemoryInsteadofplacingmemoryblocksinspecificcachelocationsbasedonmemoryaddress,wecouldallowablocktogoanywhereincache.Inthisway,cachewouldhavetofillupbeforeanyblocksareevicted.Thisishowfullyassociativecacheworks.Amemoryaddressispartitionedintoonlytwofields:thetagandtheword..6.4CacheMemorySuppose,asbefore,wehave14-bitmemoryaddressesandacachewith16blocks,eachblockofsize8.Thefieldformatofamemoryreferenceis:Whenthecacheissearched,alltagsaresearchedinparalleltoretrievethedataquickly.Thisrequiresspecial,costlyhardware..6.4CacheMemoryYouwillrecallthatdirectmappedcacheevictsablockwheneveranothermemoryreferenceneedsthatblock.Withfullyassociativecache,wehavenosuchmapping,thuswemustdeviseanalgorithmtodeterminewhichblocktoevictfromthecache.Theblockthatisevictedisthevictimblock.Thereareanumberofwaystopickavictim,wewilldiscussthemshortly..6.4CacheMemorySetassociativecachecombinestheideasofdirectmappedcacheandfullyassociativecache.AnN-waysetassociativecachemappingislikedirectmappedcacheinthatamemoryreferencemapstoaparticularlocationincache.Unlikedirectmappedcache,amemoryreferencemapstoasetofseveralcacheblocks,similartothewayinwhichfullyassociativecacheworks.Insteadofmappinganywhereintheentirecache,amemoryreferencecanmaponlytothesubsetofcacheslots..6.4CacheMemoryThenumberofcacheblockspersetinsetassociativecachevariesaccordingtooverallsystemdesign.Forexample,a2-waysetassociativecachecanbeconceptualizedasshownintheschematicbelow.Eachsetcontainstwodifferentmemoryblocks..6.4CacheMemoryInsetassociativecachemapping,amemoryreferenceisdividedintothreefields:tag,set,andword,asshownbelow.Aswithdirect-mappedcache,thewordfieldchoosesthewordwithinthecacheblock,andthetagfielduniquelyidentifiesthememoryaddress.Thesetfielddeterminesthesettowhichthememoryblockmaps..6.4CacheMemorySupposewehaveamainmemoryof214bytes.Thismemoryismappedtoa2-waysetassociativecachehaving16blockswhereeachblockcontains8words.Sincethisisa2-waycache,eachsetconsistsof2blocks,andthereare8sets.Thus,weneed3bitsfortheset,3bitsfortheword,giving8leftoverbitsforthetag:.6.4CacheMemoryWithfullyassociativeandsetassociativecache,areplacementpolicyisinvokedwhenitbecomesnecessarytoevictablockfromcache.Anoptimalreplacementpolicywouldbeabletolookintothefuturetoseewhichblockswon’tbeneededforthelongestperiodoftime.Althoughitisimpossibletoimplementanoptimalreplacementalgorithm,itisinstructivetouseitasabenchmarkforassessingtheefficiencyofanyotherschemewecomeupwith..6.4CacheMemoryThereplacementpolicythatwechoosedependsuponthelocalitythatwearetryingtooptimize--usually,weareinterestedintemporallocality.Aleastrecentlyused(LRU)algorithmkeepstrackofthelasttimethatablockwasassessedandevictstheblockthathasbeenunusedforthelongestperiodoftime.Thedisadvantageofthisapproachisitscomplexity:LRUhastomaintainanaccesshistoryforeachblock,whichultimatelyslowsdownthecache..6.4CacheMemoryFirst-in,first-out(FIFO)isapopularcachereplacementpolicy.InFIFO,theblockthathasbeeninthecachethelongest,regardlessofwhenitwaslastused.Arandomreplacementpolicydoeswhatitsnameimplies:Itpicksablockatrandomandreplacesitwithanewblock.Randomreplacementcancertainlyevictablockthatwillbeneededoftenorneededsoon,butitneverthrashes..6.4CacheMemoryTheperformanceofhierarchicalmemoryismeasuredbyitseffectiveaccesstime(EAT).EATisaweightedaveragethattakesintoaccountthehitratioandrelativeaccesstimesofsuccessivelevelsofmemory.TheEATforatwo-levelmemoryisgivenby:EAT=HAccessC+(1-H)AccessMM.whereHisthecachehitrateandAccessCandAccessMMaretheaccesstimesforcacheandmainmemory,respectively..6.4CacheMemoryForexample,considerasystemwithamainmemoryaccesstimeof200nssupportedbyacachehavinga10nsaccesstimeandahitrateof99%.TheEATis:0.99(10ns)+0.01(200ns)=9.9ns+2ns=11ns.Thisequationfordeterminingtheeffectiveaccesstimecanbeextendedtoanynumberofmemorylevels,aswewillseeinlatersections..6.4CacheMemoryCachereplacementpoliciesmustalsotakeintoaccountdirtyblocks,thoseblocksthathavebeenupdatedwhiletheywereinthecache.Dirtyblocksmustbewrittenbacktomemory.Awritepolicydetermineshowthiswillbedone.Therearetwotypesofwritepolicies,writethroughandwriteback.Writethroughupdatescacheandmainmemorysimultaneouslyoneverywrite..6.4CacheMemoryWriteback(alsocalledcopyback)updatesmemoryonlywhentheblockisselectedforreplacement.Thedisadvantageofwritethroughisthatmemorymustbeupdatedwitheachcachewrite,whichslowsdowntheaccesstimeonupdates.Thisslowdownisusuallynegligible,becausethemajorityofaccessestendtobereads,notwrites.Theadvantageofwritebackisthatmemorytrafficisminimized,butitsdisadvantageisthatmemorydoesnotalwaysagreewiththevalueincache,causingproblemsinsystemswithmanyconcurrentusers..6.5VirtualMemoryCachememoryenhancesperformancebyprovidingfastermemoryaccessspeed.Virtualmemoryenhancesperformancebyprovidinggreatermemorycapacity,withouttheexpenseofaddingmainmemory.Instead,aportionofadiskdriveservesasanextensionofmainmemory.Ifasystemusespaging,virtualmemorypartitionsmainmemoryintoindividuallymanagedpageframes,thatarewritten(orpaged)todiskwhentheyarenotimmediatelyneeded..6.5VirtualMemoryAphysicaladdressistheactualmemoryaddressofphysicalmemory.Programscreatevirtualaddressesthataremappedtophysicaladdressesbythememorymanager.Pagefaultsoccurwhenalogicaladdressrequiresthatapagebebroughtinfromdisk.Memoryfragmentationoccurswhenthepagingprocessresultsinthecreationofsmall,unusableclustersofmemoryaddresses..6.5VirtualMemoryMainmemoryandvirtualmemoryaredividedintoequalsizedpages.Theentireaddressspacerequiredbyaprocessneednotbeinmemoryatonce.Somepartscanbeondisk,whileothersareinmainmemory.Further,thepagesallocatedtoaprocessdonotneedtobestoredcontiguously--eitherondiskorinmemory.Inthisway,onlytheneededpagesareinmemoryatanytime,theunnecessarypagesareinslowerdiskstorage..6.5VirtualMemoryInformationconcerningthelocationofeachpage,whetherondiskorinmemory,ismaintainedinadatastructurecalledapagetable(shownbelow).Thereisonepagetableforeachactiveprocess..6.5VirtualMemoryWhenaprocessgeneratesavirtualaddress,theoperatingsystemtranslatesitintoaphysicalmemoryaddress.Toaccomplishthis,thevirtualaddressisdividedintotwofields:Apagefield,andanoffsetfield.Thepagefielddeterminesthepagelocationoftheaddress,andtheoffsetindicatesthelocationoftheaddresswithinthepage.Thelogicalpagenumberistranslatedintoaphysicalpageframethroughalookupinthepagetable..6.5VirtualMemoryIfthevalidbitiszerointhepagetableentryforthelogicaladdress,thismeansthatthepageisnotinmemoryandmustbefetchedfromdisk.Thisisapagefault.Ifnecessary,apageisevictedfrommemoryandisreplacedbythepageretrievedfromdisk,andthevalidbitissetto1.Ifthevalidbitis1,thevirtualpagenumberisreplacedbythephysicalframenumber.Thedataisthenaccessedbyaddingtheoffsettothephysicalframenumber..6.5VirtualMemoryAsanexample,supposeasystemhasavirtualaddressspaceof8Kandaphysicaladdressspaceof4K,andthesystemusesbyteaddressing.Wehave213/210=23virtualpages.Avirtualaddresshas13bits(8K=213)with3bitsforthepagefieldand10fortheoffset,becausethepagesizeis1024.Aphysicalmemoryaddressrequires12bits,thefirsttwobitsforthepageframeandthetrailing10bitstheoffset..6.5VirtualMemorySupposewehavethepagetableshownbelow.WhathappenswhenCPUgeneratesaddress545910=10101010100112?.6.5VirtualMemoryTheaddress10101010100112isconvertedtophysicaladdress010101010011becausethepagefield101isreplacedbyframenumber01throughalookupinthepagetable..6.5VirtualMemoryWhathappenswhentheCPUgeneratesaddress10000000001002?.6.5VirtualMemoryWesaidearlierthateffectiveaccesstime(EAT)takesalllevelsofmemoryintoconsideration.Thus,virtualmemoryisalsoafactorinthecalculation,andwealsohavetoconsiderpagetableaccesstime.Supposeamainmemoryaccesstakes200ns,thepagefaultrateis1%,andittakes10mstoloadapagefromdisk.Wehave:EAT=0.99(200ns+200ns)0.01(10ms)=100,396ns..6.5VirtualMemoryEvenifwehadnopagefaults,theEATwouldbe400nsbecausememoryisalwaysreadtwice:Firsttoaccessthepagetable,andsecondtoloadthepagefrommemory.Becausepagetablesarereadconstantly,itmakessensetokeeptheminaspecialcachecalledatranslationlook-asidebuffer(TLB).TLBsareaspecialassociativecachethatstoresthemappingofvirtualpagestophysicalpages.Thenextslideshowshowallthepiecesfittogether..6.5VirtualMemory.6.5VirtualMemoryAnotherapproachtovirtualmemoryistheuseofsegmentation.Insteadofdividingmemoryintoequal-sizedpages,virtualaddressspaceisdividedintovariable-lengthsegments,oftenunderthecontroloftheprogrammer.Asegmentislocatedthroughitsentryinasegmenttable,whichcontainsthesegment’smemorylocationandaboundslimitthatindicatesitssize.Afterapagefault,theoperatingsystemsearchesforalocationinmemorylargeenoughtoholdthesegmentthatisretrievedfromdisk..6.5VirtualMemoryBothpagingandsegmentationcancausefragmentation.Pagingissubjecttointernalfragmentationbecauseaprocessmaynotneedtheentirerangeofaddressescontainedwithinthepage.Thus,theremaybemanypagescontainingunusedfragmentsofmemory.Segmentationissubjecttoexternalfragmentation,whichoccurswhencontiguouschunksofmemorybecomebrokenupassegmentsareallocatedanddeallocatedovertime..6.5VirtualMemoryLargepagetablesarecumbersomeandslow,butwithitsuniformmemorymapping,pageoperationsarefast.Segmentationallowsfastaccesstothesegmenttable,butsegmentloadingislabor-intensive.Pagingandsegmentationcanbecombinedtotakeadvantageofthebestfeaturesofbothbyassigningfixed-sizepageswithinvariable-sizedsegments.Eachsegmenthasapagetable.Thismeansthatamemoryaddresswillhavethreefields,oneforthesegment,anotherforthepage,andathirdfortheoffset..6.6AReal-WorldExampleThePentiumarchitecturesupportsbothpagingandsegmentation,andtheycanbeusedinvariouscombinationsincludingunpagedunsegmented,segmentedunpaged,andunsegmentedpaged.Theprocessorsupportstwolevelsofcache(L1andL2),bothhavingablocksizeof32bytes.TheL1cacheisnexttotheprocessor,andtheL2cachesitsbetweentheprocessorandmemory.TheL1cacheisintwoparts:andinstructioncache(I-cache)andadatacache(D-cache).Thenextslideshowsthisorganizationschematically..6.6AReal-WorldExample.Computermemoryisorganizedinahierarchy,withthesmallest,fastestmemoryatthetopandthelargest,slowestmemoryatthebottom.Cachememorygivesfasteraccesstomainmemory,whilevirtualmemoryusesdiskstoragetogivetheillusionofhavingalargemainmemory.Cachemapsblocksofmainmemorytoblocksofcachememory.Virtualmemorymapspageframestovirtualpages.Therearethreegeneraltypesofcache:Directmapped,fullyassociativeandsetassociative.Chapter6Conclusion.Withfullyassociativeandsetassociativecache,aswellaswithvirtualmemory,replacementpoliciesmustbeestablished.ReplacementpoliciesincludeLRU,FIFO,orLFU.Thesepoliciesmustalsotakeintoaccountwhattodowithdirtyblocks.Allvirtualmemorymustdealwithfragmentation,internalforpagedmemory,externalforsegmentedmemory.Chapter6Conclusion.EndofChapter6.