operating system《操作系统》ch09-virtual memory

Chapter9:VirtualMemoryChapterObjectivesTodescribethebenefitsofavirtualmemorysystemToexplaintheconceptsofdemandpaging,page-replacementalgorithms,andallocationofpageframesTodiscusstheprincipleoftheworking-setmodelContentOverviewBackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamples9.1BackgroundVirtualmemory–separationofuserlogicalmemoryfromphysicalmemory.OnlypartoftheprogramneedstobeinmemoryforexecutionLogicaladdressspacecanthereforebemuchlargerthanphysicaladdressspaceAllowsaddressspacestobesharedbyseveralprocessesAllowsformoreefficientprocesscreationVirtualmemorycanbeimplementedvia:DemandpagingDemandsegmentationVirtualMemoryThatisLargerThanPhysicalMemoryVirtual-addressSpaceSharedLibraryUsingVirtualMemory9.2DemandPagingBringapageintomemoryonlywhenitisneededLessI/OneededLessmemoryneededFasterresponseMoreusersPageisneededreferencetoitinvalidreferenceabortnot-in-memorybringtomemoryLazyswapper–neverswapsapageintomemoryunlesspagewillbeneededSwapperthatdealswithpagesisapagerTransferofaPagedMemorytoContiguousDiskSpaceValid-InvalidBitWitheachpagetableentryavalid–invalidbitisassociated(vin-memory,inot-in-memory)Initiallyvalid–invalidbitissettoionallentriesExampleofapagetablesnapshot:Duringaddresstranslation,ifvalid–invalidbitinpagetableentryisIpagefaultvvvviii….Frame#valid-invalidbitpagetablePageTableWhenSomePagesAreNotinMainMemoryPageFaultIfthereisareferencetoapage,firstreferencetothatpagewilltraptooperatingsystem:pagefaultOperatingsystemlooksatanothertabletodecide:InvalidreferenceabortJustnotinmemoryGetemptyframeSwappageintoframeResettablesSetvalidationbit=vRestarttheinstructionthatcausedthepagefaultPageFault(Cont.)Restartinstructionblockmoveautoincrement/decrementlocationStepsinHandlingaPageFaultPerformanceofDemandPagingPageFaultRate0p1.0ifp=0nopagefaultsifp=1,everyreferenceisafaultEffectiveAccessTime(EAT)EAT=(1–p)xmemoryaccess+p(pagefaultoverhead+swappageout+swappagein+restartoverhead)DemandPagingExampleMemoryaccesstime=200nanosecondsAveragepage-faultservicetime=8millisecondsEAT=(1–p)x200+p(8milliseconds)=(1–px200+px8,000,000=200+px7,999,800Ifoneaccessoutof1,000causesapagefault,thenEAT=8.2microseconds.Thisisaslowdownbyafactorof40!!ProcessCreationVirtualmemoryallowsotherbenefitsduringprocesscreation:-Copy-on-Write-Memory-MappedFiles(later)9.3Copy-on-WriteCopy-on-Write(COW)allowsbothparentandchildprocessestoinitiallysharethesamepagesinmemoryIfeitherprocessmodifiesasharedpage,onlythenisthepagecopiedCOWallowsmoreefficientprocesscreationasonlymodifiedpagesarecopiedFreepagesareallocatedfromapoolofzeroed-outpagesBeforeProcess1ModifiesPageCAfterProcess1ModifiesPageCWhathappensifthereisnofreeframe?Pagereplacement–findsomepageinmemory,butnotreallyinuse,swapitoutalgorithmperformance–wantanalgorithmwhichwillresultinminimumnumberofpagefaultsSamepagemaybebroughtintomemoryseveraltimes9.4PageReplacementPreventover-allocationofmemorybymodifyingpage-faultserviceroutinetoincludepagereplacementUsemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodiskPagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemoryNeedForPageReplacementBasicPageReplacementFindthelocationofthedesiredpageondiskFindafreeframe:-Ifthereisafreeframe,useit-Ifthereisnofreeframe,useapagereplacementalgorithmtoselectavictimframeBringthedesiredpageintothe(newly)freeframe;updatethepageandframetablesRestarttheprocessPageReplacementPageReplacementAlgorithmsWantlowestpage-faultrateEvaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstringInallourexamples,thereferencestringis1,2,3,4,1,2,5,1,2,3,4,5GraphofPageFaultsVersusTheNumberofFramesFirst-In-First-Out(FIFO)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4framesBelady’sAnomaly:moreframesmorepagefaults1231234125349pagefaults1231235124510pagefaults443FIFOPageReplacementFIFOIllustratingBelady’sAnomalyOptimalAlgorithmReplacepagethatwillnotbeusedforlongestperiodoftime4framesexample1,2,3,4,1,2,5,1,2,3,4,5Howdoyouknowthis?Usedformeasuringhowwellyouralgorithmperforms12346pagefaults45OptimalPageReplacementLeastRecentlyUsed(LRU)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,5CounterimplementationEverypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounterWhenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange52431234125412531243LRUPageReplacementLRUAlgorithm(Cont.)Stackimplementation–keepastackofpagenumbersinadoublelinkform:Pagereferenced:moveittothetoprequires6pointerstobechangedNosearchforreplacementUseOfAStacktoRecordTheMostRecentPageReferencesLRUApproximationAlgorithmsReferencebitWitheachpageassociateabit,initially=0Whenpageisreferencedbitsetto1Replacetheonewhichis0(ifoneexists)Wedonotknowtheorder,howeverAdditional-ReferencebitAtimernbitsReferencebitsshiftSecondchanceNeedreferencebitClockreplacementIfpagetobereplaced(inclockorder)hasreferencebit=1then:setreferencebit0leavepageinmemoryreplacenextpage(inclockorder),subjecttosamerulesSecond-Chance(clock)Page-ReplacementAlgorithmCountingAlgorithmsKeepacounterofthenumberofreferencesthathavebeenmadetoeachpageLFUAlgorithm:replacespagewithsmallestcountMFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused9.5AllocationofFramesEachprocessneedsminimumnumberofpagesExample:IBM370–6pagestohandleSSMOVEinstruction:instructionis6bytes,mightspan2pages2pagestohandlefrom2pagestohandletoTwomajorallocationschemesfixedallocationpriorityallocationFixedAllocationEqualallocation–Forexample,ifthereare100framesand5processes,giveeachprocess20frames.Proportionalallocation–AllocateaccordingtothesizeofprocessPriorityAllocationUseaproportionalallocationschemeusingprioritiesratherthansizeIfprocessPigeneratesapagefault,selectforreplacementoneofitsframesselectforreplacementaframefromaprocesswithlowerprioritynumberGlobalvs.LocalAllocationGlobalreplacement–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanotherLocalreplacement–eachprocessselectsfromonlyitsownsetofallocatedframes9.6ThrashingIfaprocessdoesnothave“enough”pages,thepage-faultrateisveryhigh.Thisleadsto:lowCPUutilizationoperatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramminganotherprocessaddedtothesystemThrashingaprocessisbusyswappingpagesinandoutThrashing(Cont.)DemandPagingandThrashingWhydoesdemandpagingwork?LocalitymodelProcessmigratesfromonelocalitytoanotherLocalitiesmayoverlapWhydoesthrashingoccur?sizeoflocality>totalmemorysizeLocalityInAMemory-ReferencePatternWorking-SetModelworking-setwindowafixednumberofpagereferencesExample:10,000instructionWSSi(workingsetofProcessPi)=totalnumberofpagesreferencedinthemostrecent(variesintime)iftoosmallwillnotencompassentirelocalityiftoolargewillencompassseverallocalitiesif=willencompassentireprogramD=WSSitotaldemandframesifD>mThrashingPolicyifD>m,thensuspendoneoftheprocessesWorking-setmodelKeepingTrackoftheWorkingSetApproximatewithintervaltimer+areferencebitExample:=10,000Timerinterruptsafterevery5000timeunitsKeepinmemory2bitsforeachpageWheneveratimerinterruptscopyandsetsthevaluesofallreferencebitsto0Ifoneofthebitsinmemory=1pageinworkingsetWhyisthisnotcompletelyaccurate?Improvement=10bitsandinterruptevery1000timeunitsPage-FaultFrequencySchemeEstablish“acceptable”page-faultrateIfactualratetoolow,processlosesframeIfactualratetoohigh,processgainsframe9.7Memory-MappedFilesMemory-mappedfileI/OallowsfileI/OtobetreatedasroutinememoryaccessbymappingadiskblocktoapageinmemoryAfileisinitiallyreadusingdemandpaging.Apage-sizedportionofthefileisreadfromthefilesystemintoaphysicalpage.Subsequentreads/writesto/fromthefilearetreatedasordinarymemoryaccesses.SimplifiesfileaccessbytreatingfileI/Othroughmemoryratherthanread()write()systemcallsAlsoallowsseveralprocessestomapthesamefileallowingthepagesinmemorytobesharedMemoryMappedFilesMemory-MappedSharedMemoryinWindows9.8AllocatingKernelMemoryTreateddifferentlyfromusermemoryOftenallocatedfromafree-memorypoolKernelrequestsmemoryforstructuresofvaryingsizesSomekernelmemoryneedstobecontiguousBuddySystemAllocatesmemoryfromfixed-sizesegmentconsistingofphysically-contiguouspagesMemoryallocatedusingpower-of-2allocatorSatisfiesrequestsinunitssizedaspowerof2Requestroundeduptonexthighestpowerof2Whensmallerallocationneededthanisavailable,currentchunksplitintotwobuddiesofnext-lowerpowerof2ContinueuntilappropriatesizedchunkavailableBuddySystemAllocatorSlabAllocatorAlternatestrategySlabisoneormorephysicallycontiguouspagesCacheconsistsofoneormoreslabsSinglecacheforeachuniquekerneldatastructureEachcachefilledwithobjects–instantiationsofthedatastructureWhencachecreated,filledwithobjectsmarkedasfreeWhenstructuresstored,objectsmarkedasusedIfslabisfullofusedobjects,nextobjectallocatedfromemptyslabIfnoemptyslabs,newslaballocatedBenefitsincludenofragmentation,fastmemoryrequestsatisfactionSlabAllocation9.9OtherIssues--PrepagingPrepagingToreducethelargenumberofpagefaultsthatoccursatprocessstartupPrepageallorsomeofthepagesaprocesswillneed,beforetheyarereferencedButifprepagedpagesareunused,I/OandmemorywaswastedAssumespagesareprepagedandαofthepagesisusedIscostofs*αsavepagesfaults>or