操作系统教学课件：Chapter 10 Virtual Memory

Chapter10:VirtualMemoryBackgroundDemandPagingProcessCreationPageReplacementAllocationofFramesThrashingOperatingSystemExamplesBackground内存管理：如何在内存中同时容纳多个进程而实现多道程序。要求某个进程必须全部在内存中才能执行进程要求的内存小于可用的物理内存如果超过，用swap进程的执行必须全部在内存，进程的切换开销太大程序员写程序的时候怎么能知道有多大内存可以用呢？能不能使进程只有部分在内存中时也可以执行呢？……虚存-virtualmemory组团游世博，组团大小不考虑场馆大小。分批参观，甚至一个团放一部分，放多个团。卖票、闸机、场馆工作人员分期付款买房BackgroundVirtualmemory–separationofuserlogicalmemoryfromphysicalmemory.Onlypartoftheprogramneedstobeinmemoryforexecution.Logicaladdress

spacecanthereforebemuchlargerthan

physicaladdressspace.Allowsaddressspacestobesharedandfilestobeeasilysharedbyseveralprocesses.Allowsformoreefficientprocesscreation.

Virtualmemorycanbeimplementedvia:Demandpaging

DemandsegmentationVirtualMemoryThatisLargerThanPhysicalMemory用户基于虚拟地址空间编程虚拟地址可以比物理地址大每个程序占用更少的物理内存，系统中可以容纳更多道程序不用swap全部，单个程序需要的I/O减少虚拟内存用到了外部的存储器DemandPaging请求分页Bringapageintomemoryonlywhenitisneeded.LessI/OneededLessmemoryneededFasterresponseMoreusers

Pageisneededreferencetoitinvalidreferenceabortnot-in-memorybringtomemoryTransferofaPagedMemorytoContiguousDiskSpace仍用“swap”，使用LazyswapperSwapper-对整个进程进行操作需要连续的大片地址空间Pager-对进程的一个页面进行操作（一个进程就是一个页面序列）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内存映像文件PageReplacement页面置换NotenoughmemoryframesWhy?LimitedmemoryMultiprogramming,over-allocationBuffersforI/OPagingshouldbelogicallytransparenttotheuser用户感觉不到页面置换PageReplacementPreventover-allocationofmemorybymodifyingfaultserviceroutinetoincludepagereplacement.

Usemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodisk.

Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemory.NeedForPageReplacement要把M调进来，发现没有空余的frame再把M调进去选择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个数的增加，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：站在当前往左（过去）看，选择替换frame中离当前最远的（资历最老的先出去）FIFOPageReplacement另一种表达FIFOIllustratingBelady’sAnamolyOptimalAlgorithm最优算法Replacepagethatwillnotbeusedforlongestperiodoftime.4framesexample 1,2,3,4,1,2,5,1,2,3,4,5

怎么可能知道谁是最遥远的明日之星呢?（算命）故该算法只能Usedformeasuringhowwellyouralgorithmperforms.12346

pagefaults45将来都看不到1，2，3按FIFO最优算法：站在当前往右（将来）看，选择替换frame中离当前最远的（最遥远的明日之星先出去）OptimalPageReplacementLeastRecentlyUsed(LRU)Algorithm近似最优Referencestring:1,2,3,4,1,2,5,1,2,3,4,5

123544358pagefaultsLRU：站在当前位置往左（过去）看只看frame个（重复的除外），选择替换frame中离当前最远的（与FIFO不一样，只在一定范围内看资历与最优算法不一样，不是看将来）LRUPageReplacementLRUAlgorithm的实现方法之一：CounterimplementationEverypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounter.Whenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange.给页面打上时间的烙印、搜索页表找到LRU页面方法之二：Stackimplementation–keepastackofpagenumbersinadoublelinkform:Pagereferenced:moveittothetoprequires6pointerstobechangedatworstNosearchforreplacement页面是链条中的一环、最新访问页在环头、LRU页在环尾UseOfAStacktoRecordTheMostRecentPageReferencesReferencestring4707101212712ab47474004704717410740174012740217401204127changedheadchangedtaildoublelinkedlistLRUpage……LRUApproximationAlgorithms真正的LRU的实现必须要有额外的硬件支持，counter、stack，否则，因为每一次内存访问都要去更新，软件更新会很慢。怎么办？近似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周转资金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:了解进程执行的LocalityModelThelocalitymodelstatesthat,asaprocessexecutes,itmoveslocalitytolocality.Alocalityisasetofpagesthatareactivelyusedtogether.Aprogramisgenerallycomposedofseveraldifferentlocalities,whichmayoverlap.Ifaprocesshasenoughframestocontainitslocalities,thenitrunsmoothly.处理Thrashing:了解进程执行的LocalityModelHowtopreventthrashingToallocateenoughframestoaprocesstoaccommodateitscurrentlocality.Itwillfaultforthepagesinitslocalityuntilallthesepagesareinmemory;thenitwillnotfaultagainuntilitchangeslocalities.Ifweallocatefewerframesthanthesizeofthecurrentlocality,theprocesswillthrash,sinceitcannotkeepinmemoryallthepagesthatitisactivelyusing.利用Locality处理thrashing的两个技术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，为何不直接利用当前的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伙伴系统Allocatesmemoryfromfixed-sizesegmentconsistingofphysically-contiguouspagesMemoryallocatedusingpower-of-2allocatorSatisfiesrequestsinunitssizedaspowerof2Requestroundeduptonexthighestpowerof2Whensmallerallocationneededthanisavailable,currentchunksplitintotwobuddiesofnext-lowerpowerof2ContinueuntilappropriatesizedchunkavailableBuddySystemAllocator把所有空闲页框分成11个块链表，每个链表分别包含大小为1，2，4，8，16，32，64，128，256，512，1024个连续页框的块。每个块的第一个页框的物理地址是该块大小的整数倍，如大小为8个页框的块，其起始地址为8x212，一个页框的大小为212。分配页框。假设要请求一个具有8个连续页框的块，该算法先在8个连续页框的块链表中检查是否有一个空闲块，如果没有，算法就查找下一个更大的块（16个连续页框的块）链表，……，直到找到为止，如果找到，就把这16个连续页框分成两等份，一份用来满足请求，另一份插入到具有8个页框的块链表中。回收页框。回收进程释放的页框时，内核试图把大小相等且连续的两个伙伴块合并成一个新块，并插入到相应的块链表中。Allocatingkernelmemory运行在用户态的进程，需要更多的内存时，分配的内存来自于由内核所维护的空余内存页框链表Kernelmemory，与用户态的不同，来自于不同的空余内存池需要特事特办Kernelrequestsmemoryforstructuresofvaryingsizes，shouldminimizewasteduetofragmentationSomekernelmemoryneedstobecontiguous,evenwithoutVMSlabAllocator层板分配器AlternatestrategySlabisoneormorephysicallycontiguouspagesCacheconsistsofoneormoreslabsSinglecacheforeachuniquekerneldatastructureEachcachefilledwithobjects

–instantiationsofthedatastructureWhencachecreated,filledwithobjectsmarkedasfreeWhenstructuresstored,objectsmarkedasusedIfslabisfullofusedobjects,nextobjectallocatedfromemptyslabIfnoemptyslabs,newslaballocatedBenefitsincludenofragmentation,fastmemoryrequestsatisfactionSlabAllocationCasestudyLinux中内存的分配和回收

Summary虚拟内存允许进程只有一部分页面在内存页框中也能执行采用请求调页机制，每个页面在第一次访问时都会产生缺页中断错误，页面置换算法影响虚拟内存的性能，程序的结构影响性能虚拟内存机制加快了进程的创建，通过内存映像加快进程对文件的访问内核对象采用slaballocator作业1.Underwhatcircumstancesdopagefaultsoccur?De