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

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

spacecanthereforebemuchlargerthan

physicaladdressspace.Allowsaddressspacestobesharedandfilestobeeasilysharedbyseveralprocesses.Allowsformoreefficientprocesscreation.

Virtualmemorycanbeimplementedvia:Demandpaging

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

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

(1in-memory,0

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

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

OSpagefault（每個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頁面置換NotenoughmemoryframesWhy?LimitedmemoryMultiprogramming,over-allocationBuffersforI/OPagingshouldbelogicallytransparenttotheuser用戶感覺不到頁面置換PageReplacementPreventover-allocationofmemorybymodifyingfaultserviceroutinetoincludepagereplacement.

Usemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodisk.

Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemory.NeedForPageReplacement要把M調(diào)進(jìn)來，發(fā)現(xiàn)沒有空余的frame再把M調(diào)進(jìn)去選擇B交換出去沒有空余frame時，如何處理？由頁面置換算法確定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總的來說：隨著frame個數(shù)的增加，pagefault呈遞減趨勢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)前往左（過去）看，選擇替換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

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

pagefaults45將來都看不到1，2，3按FIFO最優(yōu)算法：站在當(dāng)前往右（將來）看，選擇替換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)前位置往左（過去）看只看frame個（重復(fù)的除外），選擇替換frame中離當(dāng)前最遠(yuǎn)的（與FIFO不一樣，只在一定范圍內(nèi)看資歷與最優(yōu)算法不一樣，不是看將來）LRUPageReplacementLRUAlgorithm的實現(xiàn)方法之一：CounterimplementationEverypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounter.Whenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange.給頁面打上時間的烙印、搜索頁表找到LRU頁面方法之二：Stackimplementation–keepastackofpagenumbersinadoublelinkform:Pagereferenced:moveittothetoprequires6pointerstobechangedatworstNosearchforreplacement頁面是鏈條中的一環(huán)、最新訪問頁在環(huán)頭、LRU頁在環(huán)尾UseOfAStacktoRecordTheMostRecentPageReferencesReferencestring4707101212712ab47474004704717410740174012740217401204127changedheadchangedtaildoublelinkedlistLRUpage……LRUApproximationAlgorithms真正的LRU的實現(xiàn)必須要有額外的硬件支持，counter、stack，否則，因為每一次內(nèi)存訪問都要去更新，軟件更新會很慢。怎么辦？近似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頁面，如果需要將被替換LRUApproximationAlgorithms(2)Secondchance–aFIFONeedreferencebit.Clockreplacement.Ifpagetobereplaced(inclockorder)hasreferencebit=1.then:setreferencebit0.leavepageinmemory.replacenextpage(inclockorder),subjecttosamerules.某一pagereference為0，則替換，如果為1，再給他一次機會，尋找下一個，但是，便找邊‘擦’掉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頁框的分配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的兩個技術(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率來解決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把所有空閑頁框分成11個塊鏈表，每個鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512，1024個連續(xù)頁框的塊。每個塊的第一個頁框的物理地址是該塊大小的整數(shù)倍，如大小為8個頁框的塊，其起始地址為8x212，一個頁框的大小為212。分配頁框。假設(shè)要請求一個具有8個連續(xù)頁框的塊，該算法先在8個連續(xù)頁框的塊鏈表中檢查是否有一個空閑塊，如果沒有，算法就查找下一個更大的塊（16個連續(xù)頁框的塊）鏈表，……，直到找到為止，如果找到，就把這16個連續(xù)頁框分成兩等份，一份用來滿足請求，另一份插入到具有8個頁框的塊鏈表中。回收頁框?；厥者M(jìn)程釋放的頁框時，內(nèi)核試圖把大小相等且連續(xù)的兩個伙伴塊合并成一個新塊，并插入到相應(yīng)的塊鏈表中。Allocatingkernelmemory運行在用戶態(tài)的進(jìn)程，需要更多的內(nèi)存時，分配的內(nèi)存來自于由內(nèi)核所維護(hù)的空余內(nèi)存頁框鏈表Kernelmemory，與用戶態(tài)的不同，來自于不同的空余內(nèi)存池需要特事特辦Kernelrequestsmemoryforstructuresofvaryingsizes，shouldminimizewasteduetofragmentationSomekernelmemoryneedstobecontiguous,evenwithoutVMSlabAllocator層板分配器AlternatestrategySlabisoneormorephysicallycontiguouspagesCacheconsistsofoneormoreslabsSinglecacheforeachuniquekerneldatastructureEachcachefilledwithobjects

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

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