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

.,1,Chapter6,Memory,.,2,Chapter6Objectives,Mastertheconceptsofhierarchicalmemoryorganization.Understandhoweachlevelofmemorycontributestosystemperformance,andhowtheperformanceismeasured.Mastertheconceptsbehindcachememory,virtualmemory,memorysegmentation,pagingandaddresstranslation.,.,3,6.1Introduction,Memoryliesattheheartofthestored-programcomputer.Inpreviouschapters,westudiedthecomponentsfromwhichmemoryisbuiltandthewaysinwhichmemoryisaccessedbyvariousISAs.Inthischapter,wefocusonmemoryorganization.Aclearunderstandingoftheseideasisessentialfortheanalysisofsystemperformance.,.,4,6.2TypesofMemory,Therearetwokindsofmainmemory:randomaccessmemory,RAM,andread-only-memory,ROM.TherearetwotypesofRAM,dynamicRAM(DRAM)andstaticRAM(SRAM).DynamicRAMconsistsofcapacitorsthatslowlyleaktheirchargeovertime.Thustheymustberefreshedeveryfewmillisecondstopreventdataloss.DRAMis“cheap”memoryowingtoitssimpledesign.,.,5,6.2TypesofMemory,SRAMconsistsofcircuitssimilartotheDflip-flopthatwestudiedinChapter3.SRAMisveryfastmemoryanditdoesntneedtoberefreshedlikeDRAMdoes.Itisusedtobuildcachememory,whichwewilldiscussindetaillater.ROMalsodoesnotneedtoberefreshed,either.Infact,itneedsverylittlechargetoretainitsmemory.ROMisusedtostorepermanent,orsemi-permanentdatathatpersistsevenwhilethesystemisturnedoff.,.,6,6.3TheMemoryHierarchy,Generallyspeaking,fastermemoryismoreexpensivethanslowermemory.Toprovidethebestperformanceatthelowestcost,memoryisorganizedinahierarchicalfashion.Small,faststorageelementsarekeptintheCPU,larger,slowermainmemoryisaccessedthroughthedatabus.Larger,(almost)permanentstorageintheformofdiskandtapedrivesisstillfurtherfromtheCPU.,.,7,6.3TheMemoryHierarchy,Thisstorageorganizationcanbethoughtofasapyramid:,.,8,6.3TheMemoryHierarchy,Toaccessaparticularpieceofdata,theCPUfirstsendsarequesttoitsnearestmemory,usuallycache.Ifthedataisnotincache,thenmainmemoryisqueried.Ifthedataisnotinmainmemory,thentherequestgoestodisk.Oncethedataislocated,thenthedata,andanumberofitsnearbydataelementsarefetchedintocachememory.,.,9,6.3TheMemoryHierarchy,Thisleadsustosomedefinitions.Ahitiswhendataisfoundatagivenmemorylevel.Amissiswhenitisnotfound.Thehitrateisthepercentageoftimedataisfoundatagivenmemorylevel.Themissrateisthepercentageoftimeitisnot.Missrate=1-hitrate.Thehittimeisthetimerequiredtoaccessdataatagivenmemorylevel.Themisspenaltyisthetimerequiredtoprocessamiss,includingthetimethatittakestoreplaceablockofmemoryplusthetimeittakestodeliverthedatatotheprocessor.,.,10,6.3TheMemoryHierarchy,Anentireblocksofdataiscopiedafterahitbecausetheprincipleoflocalitytellsusthatonceabyteisaccessed,itislikelythatanearbydataelementwillbeneededsoon.Therearethreeformsoflocality:Temporallocality-Recently-accesseddataelementstendtobeaccessedagain.Spatiallocality-Accessestendtocluster.Sequentiallocality-Instructionstendtobeaccessedsequentially.,.,11,6.4CacheMemory,ThepurposeofcachememoryistospeedupaccessesbystoringrecentlyuseddataclosertotheCPU,insteadofstoringitinmainmemory.Althoughcacheismuchsmallerthanmainmemory,itsaccesstimeisafractionofthatofmainmemory.Unlikemainmemory,whichisaccessedbyaddress,cacheistypicallyaccessedbycontent;hence,itisoftencalledcontentaddressablememory.Becauseofthis,asinglelargecachememoryisntalwaysdesirable-ittakeslongertosearch.,.,12,6.4CacheMemory,The“content”thatisaddressedincontentaddressablecachememoryisasubsetofthebitsofamainmemoryaddresscalledafield.Thefieldsintowhichamemoryaddressisdividedprovideamany-to-onemappingbetweenlargermainmemoryandthesmallercachememory.Manyblocksofmainmemorymaptoasingleblockofcache.Atagfieldinthecacheblockdistinguishesonecachedmemoryblockfromanother.,.,13,6.4CacheMemory,Thesimplestcachemappingschemeisdirectmappedcache.InadirectmappedcacheconsistingofNblocksofcache,blockXofmainmemorymapstocacheblockY=XmodN.Thus,ifwehave10blocksofcache,block7ofcachemayholdblocks7,17,27,37,.ofmainmemory.Onceablockofmemoryiscopiedintoitsslotincache,avalidbitissetforthecacheblocktoletthesystemknowthattheblockcontainsvaliddata.,Whatcouldhappenwithouthavingavalidbit?,.,14,6.4CacheMemory,Thediagrambelowisaschematicofwhatcachelookslike.Block0containsmultiplewordsfrommainmemory,identifiedwiththetag00000000.Block1containswordsidentifiedwiththetag11110101.Theothertwoblocksarenotvalid.,.,15,6.4CacheMemory,Thesizeofeachfieldintowhichamemoryaddressisdivideddependsonthesizeofthecache.Supposeourmemoryconsistsof214words,cachehas16=24blocks,andeachblockholds8words.Thusmemoryisdividedinto214/28=211blocks.Forourfieldsizes,weknowweneed4bitsfortheblock,3bitsfortheword,andthetagiswhatsleftover:,.,16,6.4CacheMemory,Asanexample,supposeaprogramgeneratestheaddress1AA.In14-bitbinary,thisnumberis:00000110101010.Thefirst7bitsofthisaddressgointhetagfield,thenext4bitsgointheblockfield,andthefinal3bitsindicatethewordwithintheblock.,.,17,6.4CacheMemory,Ifsubsequentlytheprogramgeneratestheaddress1AB,itwillfindthedataitislookingforinblock0101,word011.However,iftheprogramgeneratestheaddress,3AB,instead,theblockloadedforaddress1AAwouldbeevictedfromthecache,andreplacedbytheblocksassociatedwiththe3ABreference.,.,18,6.4CacheMemory,Supposeaprogramgeneratesaseriesofmemoryreferencessuchas:1AB,3AB,1AB,3AB,.Thecachewillcontinuallyevictandreplaceblocks.Thetheoreticaladvantageofferedbythecacheislostinthisextremecase.Thisisthemaindisadvantageofdirectmappedcache.Othercachemappingschemesaredesignedtopreventthiskindofthrashing.,.,19,6.4CacheMemory,Insteadofplacingmemoryblocksinspecificcachelocationsbasedonmemoryaddress,wecouldallowablocktogoanywhereincache.Inthisway,cachewouldhavetofillupbeforeanyblocksareevicted.Thisishowfullyassociativecacheworks.Amemoryaddressispartitionedintoonlytwofields:thetagandtheword.,.,20,6.4CacheMemory,Suppose,asbefore,wehave14-bitmemoryaddressesandacachewith16blocks,eachblockofsize8.Thefieldformatofamemoryreferenceis:Whenthecacheissearched,alltagsaresearchedinparalleltoretrievethedataquickly.Thisrequiresspecial,costlyhardware.,.,21,6.4CacheMemory,Youwillrecallthatdirectmappedcacheevictsablockwheneveranothermemoryreferenceneedsthatblock.Withfullyassociativecache,wehavenosuchmapping,thuswemustdeviseanalgorithmtodeterminewhichblocktoevictfromthecache.Theblockthatisevictedisthevictimblock.Thereareanumberofwaystopickavictim,wewilldiscussthemshortly.,.,22,6.4CacheMemory,Setassociativecachecombinestheideasofdirectmappedcacheandfullyassociativecache.AnN-waysetassociativecachemappingislikedirectmappedcacheinthatamemoryreferencemapstoaparticularlocationincache.Unlikedirectmappedcache,amemoryreferencemapstoasetofseveralcacheblocks,similartothewayinwhichfullyassociativecacheworks.Insteadofmappinganywhereintheentirecache,amemoryreferencecanmaponlytothesubsetofcacheslots.,.,23,6.4CacheMemory,Thenumberofcacheblockspersetinsetassociativecachevariesaccordingtooverallsystemdesign.Forexample,a2-waysetassociativecachecanbeconceptualizedasshownintheschematicbelow.Eachsetcontainstwodifferentmemoryblocks.,.,24,6.4CacheMemory,Insetassociativecachemapping,amemoryreferenceisdividedintothreefields:tag,set,andword,asshownbelow.Aswithdirect-mappedcache,thewordfieldchoosesthewordwithinthecacheblock,andthetagfielduniquelyidentifiesthememoryaddress.Thesetfielddeterminesthesettowhichthememoryblockmaps.,.,25,6.4CacheMemory,Supposewehaveamainmemoryof214bytes.Thismemoryismappedtoa2-waysetassociativecachehaving16blockswhereeachblockcontains8words.Sincethisisa2-waycache,eachsetconsistsof2blocks,andthereare8sets.Thus,weneed3bitsfortheset,3bitsfortheword,giving8leftoverbitsforthetag:,.,26,6.4CacheMemory,Withfullyassociativeandsetassociativecache,areplacementpolicyisinvokedwhenitbecomesnecessarytoevictablockfromcache.Anoptimalreplacementpolicywouldbeabletolookintothefuturetoseewhichblockswontbeneededforthelongestperiodoftime.Althoughitisimpossibletoimplementanoptimalreplacementalgorithm,itisinstructivetouseitasabenchmarkforassessingtheefficiencyofanyotherschemewecomeupwith.,.,27,6.4CacheMemory,Thereplacementpolicythatwechoosedependsuponthelocalitythatwearetryingtooptimize-usually,weareinterestedintemporallocality.Aleastrecentlyused(LRU)algorithmkeepstrackofthelasttimethatablockwasassessedandevictstheblockthathasbeenunusedforthelongestperiodoftime.Thedisadvantageofthisapproachisitscomplexity:LRUhastomaintainanaccesshistoryforeachblock,whichultimatelyslowsdownthecache.,.,28,6.4CacheMemory,First-in,first-out(FIFO)isapopularcachereplacementpolicy.InFIFO,theblockthathasbeeninthecachethelongest,regardlessofwhenitwaslastused.Arandomreplacementpolicydoeswhatitsnameimplies:Itpicksablockatrandomandreplacesitwithanewblock.Randomreplacementcancertainlyevictablockthatwillbeneededoftenorneededsoon,butitneverthrashes.,.,29,6.4CacheMemory,Theperformanceofhierarchicalmemoryismeasuredbyitseffectiveaccesstime(EAT).EATisaweightedaveragethattakesintoaccountthehitratioandrelativeaccesstimesofsuccessivelevelsofmemory.TheEATforatwo-levelmemoryisgivenby:EAT=HAccessC+(1-H)AccessMM.whereHisthecachehitrateandAccessCandAccessMMaretheaccesstimesforcacheandmainmemory,respectively.,.,30,6.4CacheMemory,Forexample,considerasystemwithamainmemoryaccesstimeof200nssupportedbyacachehavinga10nsaccesstimeandahitrateof99%.TheEATis:0.99(10ns)+0.01(200ns)=9.9ns+2ns=11ns.Thisequationfordeterminingtheeffectiveaccesstimecanbeextendedtoanynumberofmemorylevels,aswewillseeinlatersections.,.,31,6.4CacheMemory,Cachereplacementpoliciesmustalsotakeintoaccountdirtyblocks,thoseblocksthathavebeenupdatedwhiletheywereinthecache.Dirtyblocksmustbewrittenbacktomemory.Awritepolicydetermineshowthiswillbedone.Therearetwotypesofwritepolicies,writethroughandwriteback.Writethroughupdatescacheandmainmemorysimultaneouslyoneverywrite.,.,32,6.4CacheMemory,Writeback(alsocalledcopyback)updatesmemoryonlywhentheblockisselectedforreplacement.Thedisadvantageofwritethroughisthatmemorymustbeupdatedwitheachcachewrite,whichslowsdowntheaccesstimeonupdates.Thisslowdownisusuallynegligible,becausethemajorityofaccessestendtobereads,notwrites.Theadvantageofwritebackisthatmemorytrafficisminimized,butitsdisadvantageisthatmemorydoesnotalwaysagreewiththevalueincache,causingproblemsinsystemswithmanyconcurrentusers.,.,33,6.5VirtualMemory,Cachememoryenhancesperformancebyprovidingfastermemoryaccessspeed.Virtualmemoryenhancesperformancebyprovidinggreatermemorycapacity,withouttheexpenseofaddingmainmemory.Instead,aportionofadiskdriveservesasanextensionofmainmemory.Ifasystemusespaging,virtualmemorypartitionsmainmemoryintoindividuallymanagedpageframes,thatarewritten(orpaged)todiskwhentheyarenotimmediatelyneeded.,.,34,6.5VirtualMemory,Aphysicaladdressistheactualmemoryaddressofphysicalmemory.Programscreatevirtualaddressesthataremappedtophysicaladdressesbythememorymanager.Pagefaultsoccurwhenalogicaladdressrequiresthatapagebebroughtinfromdisk.Memoryfragmentationoccurswhenthepagingprocessresultsinthecreationofsmall,unusableclustersofmemoryaddresses.,.,35,6.5VirtualMemory,Mainmemoryandvirtualmemoryaredividedintoequalsizedpages.Theentireaddressspacerequiredbyaprocessneednotbeinmemoryatonce.Somepartscanbeondisk,whileothersareinmainmemory.Further,thepagesallocatedtoaprocessdonotneedtobestoredcontiguously-eitherondiskorinmemory.Inthisway,onlytheneededpagesareinmemoryatanytime,theunnecessarypagesareinslowerdiskstorage.,.,36,6.5VirtualMemory,Informationconcerningthelocationofeachpage,whetherondiskorinmemory,ismaintainedinadatastructurecalledapagetable(shownbelow).Thereisonepagetableforeachactiveprocess.,.,37,6.5VirtualMemory,Whenaprocessgeneratesavirtualaddress,theoperatingsystemtranslatesitintoaphysicalmemoryaddress.Toaccomplishthis,thevirtualaddressisdividedintotwofields:Apagefield,andanoffsetfield.Thepagefielddeterminesthepagelocationoftheaddress,andtheoffsetindicatesthelocationoftheaddresswithinthepage.Thelogicalpagenumberistranslatedintoaphysicalpageframethroughalookupinthepagetable.,.,38,6.5VirtualMemory,Ifthevalidbitiszerointhepagetableentryforthelogicaladdress,thismeansthatthepageisnotinmemoryandmustbefetchedfromdisk.Thisisapagefault.Ifnecessary,apageisevictedfrommemoryandisreplacedbythepageretrievedfromdisk,andthevalidbitissetto1.Ifthevalidbitis1,thevirtualpagenumberisreplacedbythephysicalframenumber.Thedataisthenaccessedbyaddingtheoffsettothephysicalframenumber.,.,39,6.5VirtualMemory,Asanexample,supposeasystemhasavirtualaddressspaceof8Kandaphysicaladdressspaceof4K,andthesystemusesbyteaddressing.Wehave213/210=23virtualpages.Avirtualaddresshas13bits(8K=213)with3bitsforthepagefieldand10fortheoffset,becausethepagesizeis1024.Aphysicalmemoryaddressrequires12bits,thefirsttwobitsforthepageframeandthetrailing10bitstheoffset.,.,40,6.5VirtualMemory,Supposewehavethepagetableshownbelow.WhathappenswhenCPUgeneratesaddress545910=10101010100112?,.,41,6.5VirtualMemory,Theaddress10101010100112isconvertedtophysicaladdress010101010011becausethepagefield101isreplacedbyframenumber01throughalookupinthepagetable.,.,42,6.5VirtualMemory,WhathappenswhentheCPUgeneratesaddress10000000001002?,.,43,6.5VirtualMemory,Wesaidearlierthateffectiveaccesstime(EAT)takesalllevelsofmemoryintoconsideration.Thus,virtualmemoryisalsoafactorinthecalculation,andwealsohavetoconsiderpagetableaccesstime.Supposeamainmemoryaccesstakes200ns,thepagefaultrateis1%,andittakes10mstoloadapagefromdisk.Wehave:EAT=0.99(200ns+200ns)0.01(10ms)=100,396ns.,.,44,6.5VirtualMemory,Evenifwehadnopagefaults,theEATwouldbe400nsbecausememoryisalwaysreadtwice:Firsttoaccessthepagetable,andsecondtoloadthepagefrommemory.Becausepagetablesarereadconstantly,itmakessensetokeeptheminaspecialcachecalledatranslationlook-asidebuffer(TLB).TLBsareaspecialassociativecachethatstoresthemappingofvirtualpagestophysicalpages.,Thenextslideshowshowallthepiecesfittogether.,.,45,6.5VirtualMemory,.,46,6.5VirtualMemory,Anotherapproachtovirtualmemoryistheuseofsegmentation.Insteadofdividingmemoryintoequal-sizedpages,virtualaddressspaceisdividedintovariable-lengthsegments,oftenunderthecontroloftheprogrammer.Asegmentislocatedthroughitsentryinasegmenttable,whichcontainsthesegmentsmemorylocationandaboundslimitthatindicatesitssize.Afterapagefault,theoperatingsystemsearchesforalocationinmemorylargeenoughtoholdthesegmentthatisretrievedfromdisk.,.,47,6.5VirtualMemory,Bothpagingandsegmentationcancausefragmentation.Pagingissubjecttointernalfragmentationbecauseaprocessmaynotneedtheentirerangeofaddressescontainedwithinthepage.Thus,theremaybemanypagescontainingunusedfragmentsofmemory.Segmentationissubjecttoexternalfragmentation,whichoccurswhencontiguouschunksofmemorybecomebrokenupassegmentsareallocatedanddeallocatedovertime.,.,48,6.5VirtualMemory,Largepagetablesarecumbersomeandslow,butwithitsuniformmemorymapping,pageope