操作系統(tǒng)教學(xué)課件：Chapter 10 Virtual Memory

Chapter10:VirtualMemoryBackgroundDemandPagingProcessCreationPageReplacementAllocationofFramesThrashingOperatingSystemExamplesBackground內(nèi)存管理：如何在內(nèi)存中同時(shí)容納多個(gè)進(jìn)程而實(shí)現(xiàn)多道程序。要求某個(gè)進(jìn)程必須全部在內(nèi)存中才能執(zhí)行進(jìn)程要求的內(nèi)存小于可用的物理內(nèi)存如果超過(guò)，用swap進(jìn)程的執(zhí)行必須全部在內(nèi)存，進(jìn)程的切換開(kāi)銷(xiāo)太大程序員寫(xiě)程序的時(shí)候怎么能知道有多大內(nèi)存可以用呢？能不能使進(jìn)程只有部分在內(nèi)存中時(shí)也可以執(zhí)行呢？……虛存-virtualmemory組團(tuán)游世博，組團(tuán)大小不考慮場(chǎng)館大小。分批參觀，甚至一個(gè)團(tuán)放一部分，放多個(gè)團(tuán)。賣(mài)票、閘機(jī)、場(chǎng)館工作人員分期付款買(mǎi)房BackgroundVirtualmemory–separationofuserlogicalmemoryfromphysicalmemory.Onlypartoftheprogramneedstobeinmemoryforexecution.Logicaladdress

spacecanthereforebemuchlargerthan

physicaladdressspace.Allowsaddressspacestobesharedandfilestobeeasilysharedbyseveralprocesses.Allowsformoreefficientprocesscreation.

Virtualmemorycanbeimplementedvia:Demandpaging

DemandsegmentationVirtualMemoryThatisLargerThanPhysicalMemory用戶(hù)基于虛擬地址空間編程虛擬地址可以比物理地址大每個(gè)程序占用更少的物理內(nèi)存，系統(tǒng)中可以容納更多道程序不用swap全部，單個(gè)程序需要的I/O減少虛擬內(nèi)存用到了外部的存儲(chǔ)器DemandPaging請(qǐng)求分頁(yè)Bringapageintomemoryonlywhenitisneeded.LessI/OneededLessmemoryneededFasterresponseMoreusers

Pageisneededreferencetoitinvalidreferenceabortnot-in-memorybringtomemoryTransferofaPagedMemorytoContiguousDiskSpace仍用“swap”，使用LazyswapperSwapper-對(duì)整個(gè)進(jìn)程進(jìn)行操作需要連續(xù)的大片地址空間Pager-對(duì)進(jìn)程的一個(gè)頁(yè)面進(jìn)行操作（一個(gè)進(jìn)程就是一個(gè)頁(yè)面序列）Valid-InvalidBitWitheachpagetableentryavalid–invalidbitisassociated

(1in-memory,0

not-in-memory)Initiallyvalid–invalidbitissetto0onallentries.Exampleofapagetablesnapshot.

Duringaddresstranslation,ifvalid–invalidbitinpagetableentryis0pagefault（頁(yè)面失效）.1111000Frame#valid-invalidbitpagetablePageTableWhenSomePagesAreNotinMainMemoryPageFault頁(yè)面失效Ifthereiseverareferencetoapage,firstreferencewilltrapto

OSpagefault（每個(gè)page的第一次引用肯定fault）OSlooksatanothertabletodecide:Invalidreferenceabort.Justnotinmemory.Getemptyframe.Swappageintoframe.Resettables,validationbit=1.Restartinstruction:LeastRecentlyUsedblockmove

autoincrement/decrementlocationStepsinHandlingaPageFault123456vWhathappensifthereisnofreeframe?Pagereplacement

–findsomepageinmemory,butnotreallyinuse,swapitout.algorithmperformance–wantanalgorithmwhichwillresultinminimumnumberofpagefaults.

Samepagemaybebroughtintomemoryseveraltimes.PerformanceofDemandPagingPageFaultRate0p1.0ifp=0nopagefaultsifp=1,everyreferenceisafault

EffectiveAccessTime(EAT) EAT=(1–

p)xmemoryaccess +pxpagefaulttimeDemandPagingExampleMemoryaccesstime=200nanosecond

PagePageTime=8millisecondP=0.1% EAT=(1–p)x0.2microsecond+px8000microsecond=0.999x0.2+0.001x8000=8.2microsecondBenefitsofdemandpagingCanstartaprocessquicklybymerelydemandpaginginthepagecontainingthefirstinstructionEnhancecreatingandrunningprocessCreateprocessCOWFork(),exec()Memory-mappedfilesProcessrunningmayneedfilesInsteadofusingopen(),read(),write(),…eachtimeaccessingadiskfileAllowingapartofvirtualaddressspacetobelogicallyassociatedwithafileProcessCreationVirtualmemoryallowsotherbenefitsduringprocesscreationandrunning:

-Copy-on-Write

-Memory-MappedFilesCopy-on-WriteCopy-on-Write(COW)allowsbothparentandchildprocessestoinitiallysharethesamepagesinmemory.

Ifeitherprocessmodifiesasharedpage,onlythenisthepagecopied.COWallowsmoreefficientprocesscreationasonlymodifiedpagesarecopied.Freepagesareallocatedfromapoolofzeroed-outpages.Memory-MappedFilesMemory-mappedfileI/OallowsfileI/Otobetreatedasroutinememoryaccessbymapping

adiskblocktoapageinmemory.Afileisinitiallyreadusingdemandpaging.Asizedportionofthefileisreadfromthefilesystemintoaphysicalpage.Subsequentreads/writesto/fromthefilearetreatedasordinarymemoryaccesses.SimplifiesfileaccessbytreatingfileI/Othroughmemoryratherthanread()

write()systemcalls.Alsoallowsseveralprocessestomapthesamefileallowingthepagesinmemorytobeshared.MemoryMappedFilesCasestudyWindows內(nèi)存映像文件PageReplacement頁(yè)面置換NotenoughmemoryframesWhy?LimitedmemoryMultiprogramming,over-allocationBuffersforI/OPagingshouldbelogicallytransparenttotheuser用戶(hù)感覺(jué)不到頁(yè)面置換PageReplacementPreventover-allocationofmemorybymodifyingfaultserviceroutinetoincludepagereplacement.

Usemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodisk.

Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemory.NeedForPageReplacement要把M調(diào)進(jìn)來(lái)，發(fā)現(xiàn)沒(méi)有空余的frame再把M調(diào)進(jìn)去選擇B交換出去沒(méi)有空余frame時(shí)，如何處理？由頁(yè)面置換算法確定BasicPageReplacementFindthelocationofthedesiredpageondisk.

Findafreeframe:

-Ifthereisafreeframe,useit.

-Ifthereisnofreeframe,useapagereplacementalgorithmtoselectavictimframe.

Readthedesiredpageintothe(newly)freeframe.Updatethepageandframetables.

Restarttheprocess.PageReplacement1234PageReplacementAlgorithms原則：Wantlowestfaultrate.Evaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstring.Inallourexamples,thereferencestringis 1,2,3,4,1,2,5,1,2,3,4,5.GraphofPageFaultsVersusTheNumberofFrames總的來(lái)說(shuō)：隨著frame個(gè)數(shù)的增加，pagefault呈遞減趨勢(shì)First-In-First-Out(FIFO)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)1,2,3,4,1,2,5,1,2,3,4,54frames

FIFOReplacement–

Belady’sAnomalymoreframeslesspagefaults1231234125349

pagefaults1231235124510

pagefaults443FIFO：站在當(dāng)前往左（過(guò)去）看，選擇替換frame中離當(dāng)前最遠(yuǎn)的（資歷最老的先出去）FIFOPageReplacement另一種表達(dá)FIFOIllustratingBelady’sAnamolyOptimalAlgorithm最優(yōu)算法Replacepagethatwillnotbeusedforlongestperiodoftime.4framesexample 1,2,3,4,1,2,5,1,2,3,4,5

怎么可能知道誰(shuí)是最遙遠(yuǎn)的明日之星呢?（算命）故該算法只能Usedformeasuringhowwellyouralgorithmperforms.12346

pagefaults45將來(lái)都看不到1，2，3按FIFO最優(yōu)算法：站在當(dāng)前往右（將來(lái)）看，選擇替換frame中離當(dāng)前最遠(yuǎn)的（最遙遠(yuǎn)的明日之星先出去）OptimalPageReplacementLeastRecentlyUsed(LRU)Algorithm近似最優(yōu)Referencestring:1,2,3,4,1,2,5,1,2,3,4,5

123544358pagefaultsLRU：站在當(dāng)前位置往左（過(guò)去）看只看frame個(gè)（重復(fù)的除外），選擇替換frame中離當(dāng)前最遠(yuǎn)的（與FIFO不一樣，只在一定范圍內(nèi)看資歷與最優(yōu)算法不一樣，不是看將來(lái)）LRUPageReplacementLRUAlgorithm的實(shí)現(xiàn)方法之一：CounterimplementationEverypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounter.Whenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange.給頁(yè)面打上時(shí)間的烙印、搜索頁(yè)表找到LRU頁(yè)面方法之二：Stackimplementation–keepastackofpagenumbersinadoublelinkform:Pagereferenced:moveittothetoprequires6pointerstobechangedatworstNosearchforreplacement頁(yè)面是鏈條中的一環(huán)、最新訪問(wèn)頁(yè)在環(huán)頭、LRU頁(yè)在環(huán)尾UseOfAStacktoRecordTheMostRecentPageReferencesReferencestring4707101212712ab47474004704717410740174012740217401204127changedheadchangedtaildoublelinkedlistLRUpage……LRUApproximationAlgorithms真正的LRU的實(shí)現(xiàn)必須要有額外的硬件支持，counter、stack，否則，因?yàn)槊恳淮蝺?nèi)存訪問(wèn)都要去更新，軟件更新會(huì)很慢。怎么辦？近似LRUReferencebitWitheachpageassociateabit,initially=0Whenpageisreferencedbitsetto1byhardware.Replacetheonewhichis0(ifoneexists).Wedonotknowtheorder,however.LRUApproximationAlgorithms(1)Additional-reference-bitsalgorithmTokeepan8-bitbyteforeachpageinatableinmemoryAtregularintervals(every100ms),atimerinterrupttransferscontroltotheOS.TheOSshiftsthereferencebitforeachpageintothehigh-orderbitofits8-bitbyte,shiftingtheotherbitsright1bit,discardingthelow-orderbit.These8-bitbytescontainthehistoryofthepageuseforthelasteighttimeperiods.Ifweinterpretthese8-bitbytesasunsignedintegers,thepagewiththelowestnumber

istheLRUpageanditcanbereplaced.APBexample6pages,ateachtimerintervalhasthefollowingreference(page0~5)101011110010110101100010011000010000000110000001110000011110000011110001000000001000000011000000011000001011000021000000001000000001000000001000010001000300000000000000001000000001000000001000004100000000100000001100000101100000101100051000000001000000101000000101000000101000值最小，LRU頁(yè)面，如果需要將被替換LRUApproximationAlgorithms(2)Secondchance–aFIFONeedreferencebit.Clockreplacement.Ifpagetobereplaced(inclockorder)hasreferencebit=1.then:setreferencebit0.leavepageinmemory.replacenextpage(inclockorder),subjecttosamerules.某一pagereference為0，則替換，如果為1，再給他一次機(jī)會(huì)，尋找下一個(gè)，但是，便找邊‘擦’掉1.Second-Chance(clock)ReplacementAlgorithmImp.LRUApproximationAlgorithms(3)Enhancedsecond-chancealgorithm(Referencebit,modifiedbit)(0,0): bestpagetoreplace(0,1): notquitegoodforreplacement(1,0): willbeusedsoon(1,1): worstpagetoreplace.MacintoshVMM.Counting-basedAlgorithmsKeepacounterofthenumberofreferencesthathavebeenmadetoeachpage.

LFU(leastfrequentlyused)Algorithm:replacespagewithsmallestcount.

MFU(mostfrequentlyused)Algorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused.PageReplacement:BufferingAlgorithmTokeepapooloffreeframesWhenapagefaultoccurs,avictimframeischosenasbeforeThedesiredpageisreadintoafreeframefromthepoolbeforethevictimiswrittenout,canstarttheprocessasapWhentheframeislaterwrittenout,itsframeisaddedtothepool周轉(zhuǎn)資金Another,tokeepapooloffreeframesandtorememberwhichpagewasineachframeIfapageisneededagain,checkthepool.Maybetheframecontainingtheoriginalpageisnotusedbysomeoneelse.Sousethis.高速緩存Casharevery,veryimportantthingsCachingandBufferingarevery,veryimportanttechniques.AllocationofFrames頁(yè)框的分配Eachprocessneedsminimumnumberofpages.Example:IBM370–6pagestohandleSSMOVEinstruction:instructionis6bytes,mightspan2pages.2pagestohandlefrom.2pagestohandleto.Twomajorallocationschemes.fixedallocationpriorityallocationFixedAllocationEqualallocation–e.g.,if100framesand5processes,giveeach20pages.Proportionalallocation–Allocateaccordingtothesizeofprocess.PriorityAllocationUseaproportionalallocationschemeusingprioritiesratherthansize.

IfprocessPigeneratesapagefault,selectforreplacementoneofitsframes.selectforreplacementaframefromaprocesswithlowerprioritynumber.Globalvs.LocalAllocationGlobalreplacement–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanother.Localreplacement–eachprocessselectsfromonlyitsownsetofallocatedframes.ThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto:lowCPUutilization.operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming.anotherprocessaddedtothesystem.

Thrashing

aprocessisbusyswappingpagesinandout.THRASHINGAprocessisthrashingifitisspendingmoretimepagingandexecuting.(Astudentisthrashingsometimesaswell(goingtotheLibs))CauseSolutionsWorking-setmodelfaultfrequencyThrashing:CauseCauseofthrashingWhile(CPUutilization:toolow) increasethedegreeofmultiprogramming Processeswilltakeframesawayfromother processes(byglobalreplacement)processeswaitforthepagingdevice

ThrashingThrashing:Cause處理Thrashing:了解進(jìn)程執(zhí)行的LocalityModelThelocalitymodelstatesthat,asaprocessexecutes,itmoveslocalitytolocality.Alocalityisasetofpagesthatareactivelyusedtogether.Aprogramisgenerallycomposedofseveraldifferentlocalities,whichmayoverlap.Ifaprocesshasenoughframestocontainitslocalities,thenitrunsmoothly.處理Thrashing:了解進(jìn)程執(zhí)行的LocalityModelHowtopreventthrashingToallocateenoughframestoaprocesstoaccommodateitscurrentlocality.Itwillfaultforthepagesinitslocalityuntilallthesepagesareinmemory;thenitwillnotfaultagainuntilitchangeslocalities.Ifweallocatefewerframesthanthesizeofthecurrentlocality,theprocesswillthrash,sinceitcannotkeepinmemoryallthepagesthatitisactivelyusing.利用Locality處理thrashing的兩個(gè)技術(shù)Working-setmodelfaultfrequencyStrategy：Working-SetModelWorking-setwindow,workingsetWorking-setwindowisafixednumberofpagereferencesWorkingsetisthesetofpagesinthemostrecentpagereferences.Ifapageisinactiveuse,itwillbeintheworkingset.Ifitisnolongerbeingused,itwilldropfromtheworkingsettimeunitsafteritslastreference.

Theworkingsetisanapproximationoftheprogram’slocality.Strategy：Working-SetModelStrategy：Working-SetModelWorkingset：窗口大小如何定？Anapproximationoftheprogram’slocalityTheaccuracyoftheworkingsetdependsontheselectionofiftoosmallwillnotencompassentirelocality.iftoolargewillencompassseverallocalities.if= willencompassentireprogram.ChangesdynamicallyStrategy：Working-SetModelHowdoestheworking-setmodelworks?Tocomputetheworking-setsizeforeachprocessinthesystem,Tocomputethetotaldemandforframes.Ifthetotaldemandislessthanthetotalavailableframes,nothrashingwilloccur.Ifthetotaldemandisgreaterthanthetotalavailableframes,thrashingwilloccur.Strategy：Working-SetModelIfoneprocessdoesn’tthrash,itshouldhaveenoughframesforitsworkingset.Ifallprocessdon’tthrash,theOSshouldhaveenoughframesfortotalworkingsets.Ifthrasheverhappens,theOSswapssomeprocessesouttoreducethedegreeofmultiprogramming.Howtokeeptrackoftheworkingset？Strategy：Working-SetModelApproximatewithintervaltimer+areferencebitExample:=10,000Timerinterruptsafterevery5000timeunits.Keepinmemory2bitsforeachpage.Wheneveratimerinterrupts,copyandclearthevaluesofallreferencebitsto0.Ifoneofthebitsinmemory=1itspageisinworkingset.notcompletelyaccurate?Improvement10bitsforeachpageinterruptevery1000timeunits.Strategy：FaultFrequencySchemeTheworking-setmodelissuccessful,knowledgeoftheworking-setcanbeusefulforprepaging,butitseemsaclumsywaytocontrolthrashing.既然thrashing具有很高的pagefault，為何不直接利用當(dāng)前的pagefault率來(lái)解決thrashing呢？Establish“acceptable”faultrate.Ifactualratetoolow,processlosesframe.(couldbesuspended)Ifactualratetoohigh,processgainsframe.Strategy：FaultFrequencySchemeOTHERCONSIDERATIONSPrepagingPagesizeselectionTLBReachProgramstructureI/OInterlockOtherConsiderations:PrepagingPrepagingPuredemandpagingthelargenumberofpagefaultsthatoccurwhenaprocessisstarted.Prepaging:topreventthishighlevelofinitialpaging.Prepaging:totrytobringintomemoryatonetimeallthepagesthatwillbeneeded.TobringinthesavedworkingsetDiscussion:whetherthecostofusingprepagingislessthanthecostofservicingthecorrespondingpagefaults.OtherConsiderations:PagesizePagesizeselectionPagetablesizeInternalfragmentationI/Ooverhead(seektime,latencytime,transfertime)LocalityPagefaultrateThetrendistowardlargerandlargerpagesize.OtherConsiderations:TLBreachTLBReach-TheamountofmemoryaccessiblefromtheTLB.TLBReach=(TLBSize)X(PageSize)Ideally,theworkingsetofeachprocessisstoredintheTLB.Otherwisethereisahighdegreeofpagefaults.OtherConsiderations:TLBReachIncreasethePageSize.Thismayleadtoanincreaseinfragmentationasnotallapplicationsrequirealargepagesize.ProvideMultiplePageSizes.Thisallowsapplicationsthatrequirelargerpagesizestheopportunitytousethemwithoutanincreaseinfragmentation.OtherConsiderations:ProgramstructureProgramstructureintA[][]=newint[1024][1024];Eachrowisstoredinonepage.Program1:1024x1024pagefaults for(j=0;j<A.length;j++)

for(i=0;i<A.length;i++)

A[i,j]=0;

Program2:1024pagefaults for(i=0;i<A.length;i++)

for(j=0;j<A.length;j++)

A[i,j]=0;OtherConsiderations:I/OInterlockI/OInterlock

–Pagesmustsometimesbelockedintomemory.ConsiderI/O.Pagesthatareusedforcopyingafilefromadevicemustbelockedfrombeingselectedforevictionbyapagereplacementalgorithm.OtherConsiderations:I/OInterlockReasonWhyFramesUsedForI/OMustBeInMemoryBuddySystem伙伴系統(tǒng)Allocatesmemoryfromfixed-sizesegmentconsistingofphysically-contiguouspagesMemoryallocatedusingpower-of-2allocatorSatisfiesrequestsinunitssizedaspowerof2Requestroundeduptonexthighestpowerof2Whensmallerallocationneededthanisavailable,currentchunksplitintotwobuddiesofnext-lowerpowerof2ContinueuntilappropriatesizedchunkavailableBuddySystemAllocator把所有空閑頁(yè)框分成11個(gè)塊鏈表，每個(gè)鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512，1024個(gè)連續(xù)頁(yè)框的塊。每個(gè)塊的第一個(gè)頁(yè)框的物理地址是該塊大小的整數(shù)倍，如大小為8個(gè)頁(yè)框的塊，其起始地址為8x212，一個(gè)頁(yè)框的大小為212。分配頁(yè)框。假設(shè)要請(qǐng)求一個(gè)具有8個(gè)連續(xù)頁(yè)框的塊，該算法先在8個(gè)連續(xù)頁(yè)框的塊鏈表中檢查是否有一個(gè)空閑塊，如果沒(méi)有，算法就查找下一個(gè)更大的塊（16個(gè)連續(xù)頁(yè)框的塊）鏈表，……，直到找到為止，如果找到，就把這16個(gè)連續(xù)頁(yè)框分成兩等份，一份用來(lái)滿(mǎn)足請(qǐng)求，另一份插入到具有8個(gè)頁(yè)框的塊鏈表中?；厥枕?yè)框?；厥者M(jìn)程釋放的頁(yè)框時(shí)，內(nèi)核試圖把大小相等且連續(xù)的兩個(gè)伙伴塊合并成一個(gè)新塊，并插入到相應(yīng)的塊鏈表中。Allocatingkernelmemory運(yùn)行在用戶(hù)態(tài)的進(jìn)程，需要更多的內(nèi)存時(shí)，分配的內(nèi)存來(lái)自于由內(nèi)核所維護(hù)的空余內(nèi)存頁(yè)框鏈表Kernelmemory，與用戶(hù)態(tài)的不同，來(lái)自于不同的空余內(nèi)存池需要特事特辦Kernelrequestsmemoryforstructuresofvaryingsizes，shouldminimizewasteduetofragmentationSomekernelmemoryneedstobecontiguous,evenwithoutVMSlabAllocator層板分配器AlternatestrategySlabisoneormorephysicallycontiguouspagesCacheconsistsofoneormoreslabsSinglecacheforeachuniquekerneldatastructureEachcachefilledwithobjects

–instantiationsofthedatastructureWhencachecreated,filledwithobjectsmarkedasfreeWhenstructuresstored,objectsmarkedasusedIfslabisfullofusedobjects,nextobjectallocatedfromemptyslabIfnoemptyslabs,newslaballocatedBenefitsincludenofragmentation,fastmemoryrequestsatisfactionSlabAllocationCasestudyLinux中內(nèi)存的分配和回收

Summary虛擬內(nèi)存允許進(jìn)程只有一部分頁(yè)面在內(nèi)存頁(yè)框中也能執(zhí)行采用請(qǐng)求調(diào)頁(yè)機(jī)制，每個(gè)頁(yè)面在第一次訪問(wèn)時(shí)都會(huì)產(chǎn)生缺頁(yè)中斷錯(cuò)誤，頁(yè)面置換算法影響虛擬內(nèi)存的性能，程序的結(jié)構(gòu)影響性能虛擬內(nèi)存機(jī)制加快了進(jìn)程的創(chuàng)建，通過(guò)內(nèi)存映像加快進(jìn)程對(duì)文件的訪問(wèn)內(nèi)核對(duì)象采用slaballocator作業(yè)1.Underwhatcircumstancesdopagefaultsoccur?De