操作系統(tǒng)原理英文版課件：Chapter 9 Virtual Memory

Chapter9VirtualMemoryOperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsBackgroundVirtualmemory–separationofuserlogicalmemoryfromphysicalmemory.Onlypartoftheprogramneedstobeinmemoryforexecution.Logicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace.MoreprogramscanberunatthesametimeLessI/ObeneededtoloadorswapVirtualmemorycanbeimplementedvia:DemandpagingDemandsegmentationOperatingSystemConceptsVirtualMemoryThatisLargerThanPhysicalMemoryOperatingSystemConceptsVirtual-addressSpaceUsuallydesignlogicaladdressspaceforstacktostartatMaxlogicaladdressandgrow“down”whileheapgrows“up”MaximizesaddressspaceuseUnusedaddressspacebetweenthetwoisholeNophysicalmemoryneededuntilheaporstackgrowstoagivennewpageOperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsDemandPagingBringapageintomemoryonlywhenitisneeded.LessI/OneededLessmemoryneededFasterresponseMoreusersPageisneededreferencetoitinvalidreferenceabortnot-in-memorybringtomemoryOperatingSystemConceptsValid-InvalidBitWitheachpagetableentryavalid–invalidbitisassociated

(1in-memory,0

not-in-memory)Initiallyvalid–invalidbitissetto0onallentries.Duringaddresstranslation,ifvalid–invalidbitinpagetableentryis0pagefault.OperatingSystemConceptsPageTableWhenSomePagesAreNotinMainMemoryOperatingSystemConceptsPageFaultIfthereiseverareferencetoapage,firstreferencewilltraptoOSpagefaultOSlooksatanothertabletodecide:Invalidreferenceabort.Justnotinmemory.Getemptyframe.Swappageintoframe.Resettables,validationbit=1.Restartinstructionblockmoveautoincrement/decrementlocationOperatingSystemConceptsStepsinHandlingaPageFaultOperatingSystemConceptsPerformanceofDemandPagingExtremecase–startprocesswithnopagesinmemoryOSsetsinstructionpointertofirstinstructionofprocess,non-memory-resident->pagefaultAndforeveryotherprocesspagesonfirstaccessPuredemandpagingOperatingSystemConceptsPerformanceofDemandPagingPageFaultRate0p1.0ifp=0nopagefaultsifp=1,everyreferenceisafault

EffectiveAccessTime(EAT) EAT=(1–p)xmemoryaccess +p(pagefaultoverhead +[swappageout] +swappagein +restartoverhead)PerformanceofDemandPagingMemoryaccesstime=200nanosecondsAveragefaultservicetime=8millisecondsEAT=(1–p)x200+p(8milliseconds)=200+px7,999,800Ifoneaccessoutof1,000causesapagefault,thenEAT=8.2microseconds.Thisisaslowdownbyafactorof40!!OperatingSystemConceptsPerformanceofDemandPagingIfwantperformancedegradation<10percent220>200+7,999,800xp

20>7,999,800xpp<.0000025<onepagefaultinevery400,000memoryaccessesOperatingSystemConceptsOperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsProcessCreationVirtualmemoryallowsotherbenefitsduringprocesscreation:

-Copy-on-Write

-Memory-MappedFiles(Later)OperatingSystemConceptsCopy-on-WriteCopy-on-Write(COW)allowsbothparentandchildprocessestoinitiallysharethesamepagesinmemory.(Nodemandpaging)Ifeitherprocessmodifiesasharedpage,onlythenisthepagecopied.COWallowsmoreefficientprocesscreationasonlymodifiedpagesarecopied.BeforeProcess1ModifiesPageCOperatingSystemConceptsAfterProcess1ModifiesPageCOperatingSystemConceptsOperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsWhathappensifthereisnofreeframe?Pagereplacement–findsomepageinmemory,butnotreallyinuse,swapitoutalgorithmperformance–wantanalgorithmwhichwillresultinminimumnumberofpagefaultsSamepagemaybebroughtintomemoryseveraltimesOperatingSystemConceptsPageReplacementPreventover-allocationofmemorybymodifyingfaultserviceroutinetoincludepagereplacement.Usemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodisk.Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemory.OperatingSystemConceptsNeedForPageReplacementOperatingSystemConceptsBasicPageReplacementFindthelocationofthedesiredpageondisk.Findafreeframe:

-Ifthereisafreeframe,useit.

-Ifthereisnofreeframe,useapagereplacement algorithmtoselectavictimframe.Readthedesiredpageintothe(newly)freeframe.Updatethepageandframetables.Restarttheinstruction.OperatingSystemConceptsPageReplacementOperatingSystemConceptsPageReplacementAlgorithmsWantlowestfaultrate.Evaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstring.Inallourexamples,thereferencestringis 1,2,3,4,1,2,5,1,2,3,4,5.OperatingSystemConceptsGraphofPageFaultsVersusTheNumberofFramesOperatingSystemConceptsFirst-In-First-Out(FIFO)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)1231234125349pagefaultsOperatingSystemConceptsFirst-In-First-Out(FIFO)Algorithm4frames

FIFOReplacement–Belady’sAnomalymoreframesmorepagefaults1231235124510pagefaults443OperatingSystemConceptsFIFOIllustratingBelady’sAnamolyOperatingSystemConceptsFIFOPageReplacementOperatingSystemConceptsOptimalAlgorithmReplacepagethatwillnotbeusedforlongestperiodoftime.4framesexample 1,2,3,4,1,2,5,1,2,3,4,5

Howdoyouknowthis?Usedformeasuringhowwellyouralgorithmperforms.12346pagefaults45OperatingSystemConceptsOptimalPageReplacementOperatingSystemConceptsLeastRecentlyUsed(LRU)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,5

Counterimplementation(how?)Everypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounter.Whenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange.12354435OperatingSystemConceptsLRUPageReplacementOperatingSystemConceptsLRUAlgorithm(Cont.)Stackimplementation–keepastackofpagenumbersinadoublelinkform:(How?Exercise1)Pagereferenced:moveittothetoprequires6pointerstobechangedNosearchforreplacementOperatingSystemConceptsUseOfAStacktoRecordTheMostRecentPageReferencesOperatingSystemConceptsLRUApproximationAlgorithmsReferencebitWitheachpageassociateabit,initially=0Whenpageisreferencedbitsetto1.Replacetheonewhichis0(ifoneexists).Wedonotknowtheorder,however.Additional-Reference-BitsAlgorithmKeepan8-bitbytesforeachpageAtregularintervalsshiftsthebitsright1bit,shiftthereferencebitintothehigh-orderbitInterpretthese8-bitbytesasunsignedintergers,thepagewithlowestnumberistheLRUpageOperatingSystemConceptsLRUApproximationAlgorithms(Cont.)Secondchance(linklistapproach?)Needreferencebit.Clockreplacement.Ifpagetobereplaced(inclockorder)hasreferencebit=1.then:setreferencebit0.leavepageinmemory.replacenextpage(inclockorder),subjecttosamerules.OperatingSystemConceptsSecond-Chance(clock)ReplacementAlgorithmOperatingSystemConceptsCountingAlgorithmsKeepacounterofthenumberofreferencesthathavebeenmadetoeachpage.

LFUAlgorithm:replacespagewithsmallestcount.

MFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused.OperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFrames

ThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsAllocationofFramesEachprocessneedsminimumnumberofpages.(why?Restartinstruction)Example:IBM370–6pagestohandleSSMOVEinstruction:instructionis6bytes,mightspan2pages.2pagestohandlefrom.2pagestohandleto.Twomajorallocationschemes.fixedallocationpriorityallocationOperatingSystemConceptsFixedAllocationEqualallocation–e.g.,if100framesand5processes,giveeach20pages.Proportionalallocation–Allocateaccordingtothesizeofprocess.OperatingSystemConceptsPriorityAllocationUseaproportionalallocationschemeusingprioritiesratherthansize.

IfprocessPigeneratesapagefault,selectforreplacementoneofitsframes.selectforreplacementaframefromaprocesswithlowerprioritynumber.OperatingSystemConceptsGlobalvs.LocalAllocationGlobalreplacement–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanother.(benefit?Weakness?)Localreplacement–eachprocessselectsfromonlyitsownsetofallocatedframes.OperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto:(howithappens?)lowCPUutilization.operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming.anotherprocessaddedtothesystem.

Thrashing

aprocessisbusyswappingpagesinandout.OperatingSystemConceptsThrashingWhydoespagingwork?(howtoknowtheframenumbertoallocatetoaprocess?)

LocalitymodelProcessmigratesfromonelocalitytoanother.Localitiesmayoverlap.Whydoesthrashingoccur?

sizeoflocality>totalmemorysizeOperatingSystemConceptsLocalityInAMemory-ReferencePatternOperatingSystemConceptsWorking-SetModelworking-setwindowafixednumberofpagereferences

Example:10,000instructionWSSi(workingsetofProcessPi)=

totalnumberofpagesreferencedinthemostrecent(variesintime)iftoosmallwillnotencompassentirelocality.iftoolargewillencompassseverallocalities.if=willencompassentireprogram.OperatingSystemConceptsWorking-SetModel(Cont.)D=WSSitotaldemandframesifD>mThrashingPolicyifD>m,thensuspendoneoftheprocesses.OperatingSystemConceptsWorking-setmodelOperatingSystemConceptsKeepingTrackoftheWorkingSetApproximatewithintervaltimer+areferencebitExample:=10,000Timerinterruptsafterevery5000timeunits.Keepinmemory2bitsforeachpage.Wheneveratimerinterruptscopyandsetsthevaluesofallreferencebitsto0.Ifoneofthebitsinmemory=1pageinworkingset.Whyisthisnotcompletelyaccurate?Improvement=10bitsandinterruptevery1000timeunits.Whathappenswhenpagefaultoccurs?OperatingSystemConceptsFaultFrequencySchemeEstablish“acceptable”faultrate.Ifactualratetoolow,processlosesframe.Ifactualratetoohigh,processgainsframe.OperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsMemory-MappedFilesMemory-mappedfileI/OallowsfileI/Otobetreatedasroutinememoryaccessbymappingadiskblocktoapageinmemory.Afileisinitiallyreadusingdemandpaging.Asizedportionofthefileisreadfromthefilesystemintoaphysicalpage.Subsequentreads/writesto/fromthefilearetreatedasordinarymemoryaccesses.SimplifiesfileaccessbytreatingfileI/Othroughmemoryratherthanread()

write()systemcalls.Alsoallowsseveralprocessestomapthesamefileallowingthepagesinmemorytobeshared.OperatingSystemConceptsMemoryMappedFilesOperatingSystemConceptsMemory-MappedSharedMemoryinWindowsExample:linuxmmapFollowinglink:/developerworks/cn/linux/l-ipc/part5/index1.htmlOperatingSystemConceptsOperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsAllocatingKernelMemoryTreateddifferentlyfromusermemoryOftenallocatedfromafree-memorypoolKernelrequestsmemoryforstructuresofvaryingsizes,fragmentationneedtobetakencareofSomekernelmemoryneedstobecontiguousOperatingSystemConceptsBuddySystemAllocatesmemoryfromfixed-sizesegmentconsistingofphysically-contiguouspagesMemoryallocatedusingpower-of-2allocatorSatisfiesrequestsinunitssizedaspowerof2Requestroundeduptonexthighestpowerof2Whensmallerallocationneededthanisavailable,currentchunksplitintotwobuddiesofnext-lowerpowerof2ContinueuntilappropriatesizedchunkavailableOperatingSystemConceptsBuddySystemAllocator21KBkernelmemoryallocationrequestFragmentationproblemOperatingSystemConceptsSlabAllocatorAlternatestrategySlabisoneormorephysicallycontiguouspagesCacheconsistsofoneormoreslabsSinglecacheforeachuniquekerneldatastructureEachcachefilledwithobjects–instantiationsofthedatastructureOperatingSystemConceptsSlabAllocator(Cont)Whencachecreated,filledwithobjectsmarkedasfreeWhenstructuresstored,objectsmarkedasusedIfslabisfullofusedobjects,nextobjectallocatedfromemptyslabIfnoemptyslabs,newslaballocatedBenefitsincludenofragmentation,fastmemoryrequestsatisfactionOperatingSystemConceptsSlabAllocationSlabAllocationForexampleprocessdescriptorisoftypestructtask_structApprox1.7KBofmemoryNewtask->allocatenewstructfromcacheWilluseexistingfreestructtask_structSlabcanbeinthreepossiblestatesFull–allusedEmpty–allfreePartial–mixoffreeandusedUponrequest,slaballocatorUsesfreestructinpartialslabIfnone,takesonefromemptyslabIfnoemptyslab,createnewemptyOperatingSystemConceptsOperatingSystemConceptsChapter9:VirtualMemoryBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamplesOperatingSystemConceptsOtherIssues--PrepagingPrepagingToreducethelargenumberofpagefaultsthatoccursatprocessstartupPrepageallorsomeofthepagesaprocesswillneed,beforetheyarereferenced(worksetmodel)Butifprepagedpagesareunused,I/OandmemorywaswastedAssumespagesareprepagedandα

ofthepagesisusedIscostofs*α

savepagesfaults>or<thanthecostofprepaging

s*(1-α)unnecessarypages?α

nearzeroprepagingloses

OperatingSystemConceptsOtherIssues–PageSizePagesizeselectionmusttakeintoconsideration:Fragmentation(?)tablesize(?)I/Ooverhead(?)Locality(?)OperatingSystemConceptsOtherIssues–TLBReachTLBReach-TheamountofmemoryaccessiblefromtheTLBTLBReach=(TLBSize)X(PageSize)Ideally,theworkingsetofeachprocessisstoredintheTLBOtherwisethereisahighdegreeofpagefaultsIncreasethePageSizeProvideMultiplePageSizesThisallowsapplicationsthatrequirelargerpagesizestheopportunitytousethemwithoutanincreaseinfragmentationOperatingSystemConceptsOtherIssues–ProgramStructureProgramstructureintA[][]=newint[1024]