operatingsystem《操作系统》ch09-virtualmemory

Chapter9:VirtualMemory,ChapterObjectives,TodescribethebenefitsofavirtualmemorysystemToexplaintheconceptsofdemandpaging,page-replacementalgorithms,andallocationofpageframesTodiscusstheprincipleoftheworking-setmodel,ContentOverview,BackgroundDemandPagingCopy-on-WritePageReplacementAllocationofFramesThrashingMemory-MappedFilesAllocatingKernelMemoryOtherConsiderationsOperating-SystemExamples,9.1Background,Virtualmemoryseparationofuserlogicalmemoryfromphysicalmemory.OnlypartoftheprogramneedstobeinmemoryforexecutionLogicaladdressspacecanthereforebemuchlargerthanphysicaladdressspaceAllowsaddressspacestobesharedbyseveralprocessesAllowsformoreefficientprocesscreationVirtualmemorycanbeimplementedvia:DemandpagingDemandsegmentation,VirtualMemoryThatisLargerThanPhysicalMemory,Virtual-addressSpace,SharedLibraryUsingVirtualMemory,9.2DemandPaging,BringapageintomemoryonlywhenitisneededLessI/OneededLessmemoryneededFasterresponseMoreusersPageisneededreferencetoitinvalidreferenceabortnot-in-memorybringtomemoryLazyswapperneverswapsapageintomemoryunlesspagewillbeneededSwapperthatdealswithpagesisapager,TransferofaPagedMemorytoContiguousDiskSpace,Valid-InvalidBit,Witheachpagetableentryavalidinvalidbitisassociated(vin-memory,inot-in-memory)InitiallyvalidinvalidbitissettoionallentriesExampleofapagetablesnapshot:Duringaddresstranslation,ifvalidinvalidbitinpagetableentryisIpagefault,v,v,v,v,i,i,i,.,Frame#,valid-invalidbit,pagetable,PageTableWhenSomePagesAreNotinMainMemory,PageFault,Ifthereisareferencetoapage,firstreferencetothatpagewilltraptooperatingsystem:pagefaultOperatingsystemlooksatanothertabletodecide:InvalidreferenceabortJustnotinmemoryGetemptyframeSwappageintoframeResettablesSetvalidationbit=vRestarttheinstructionthatcausedthepagefault,PageFault(Cont.),Restartinstructionblockmoveautoincrement/decrementlocation,StepsinHandlingaPageFault,PerformanceofDemandPaging,PageFaultRate0p1.0ifp=0nopagefaultsifp=1,everyreferenceisafaultEffectiveAccessTime(EAT)EAT=(1p)xmemoryaccess+p(pagefaultoverhead+swappageout+swappagein+restartoverhead),DemandPagingExample,Memoryaccesstime=200nanosecondsAveragepage-faultservicetime=8millisecondsEAT=(1p)x200+p(8milliseconds)=(1px200+px8,000,000=200+px7,999,800Ifoneaccessoutof1,000causesapagefault,thenEAT=8.2microseconds.Thisisaslowdownbyafactorof40!,ProcessCreation,Virtualmemoryallowsotherbenefitsduringprocesscreation:-Copy-on-Write-Memory-MappedFiles(later),9.3Copy-on-Write,Copy-on-Write(COW)allowsbothparentandchildprocessestoinitiallysharethesamepagesinmemoryIfeitherprocessmodifiesasharedpage,onlythenisthepagecopiedCOWallowsmoreefficientprocesscreationasonlymodifiedpagesarecopiedFreepagesareallocatedfromapoolofzeroed-outpages,BeforeProcess1ModifiesPageC,AfterProcess1ModifiesPageC,Whathappensifthereisnofreeframe?,Pagereplacementfindsomepageinmemory,butnotreallyinuse,swapitoutalgorithmperformancewantanalgorithmwhichwillresultinminimumnumberofpagefaultsSamepagemaybebroughtintomemoryseveraltimes,9.4PageReplacement,Preventover-allocationofmemorybymodifyingpage-faultserviceroutinetoincludepagereplacementUsemodify(dirty)bittoreduceoverheadofpagetransfersonlymodifiedpagesarewrittentodiskPagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemorylargevirtualmemorycanbeprovidedonasmallerphysicalmemory,NeedForPageReplacement,BasicPageReplacement,FindthelocationofthedesiredpageondiskFindafreeframe:-Ifthereisafreeframe,useit-Ifthereisnofreeframe,useapagereplacementalgorithmtoselectavictimframeBringthedesiredpageintothe(newly)freeframe;updatethepageandframetablesRestarttheprocess,PageReplacement,PageReplacementAlgorithms,Wantlowestpage-faultrateEvaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstringInallourexamples,thereferencestringis1,2,3,4,1,2,5,1,2,3,4,5,GraphofPageFaultsVersusTheNumberofFrames,First-In-First-Out(FIFO)Algorithm,Referencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4framesBeladysAnomaly:moreframesmorepagefaults,1,2,3,1,2,3,4,1,2,5,3,4,9pagefaults,1,2,3,1,2,3,5,1,2,4,5,10pagefaults,4,4,3,FIFOPageReplacement,FIFOIllustratingBeladysAnomaly,OptimalAlgorithm,Replacepagethatwillnotbeusedforlongestperiodoftime4framesexample1,2,3,4,1,2,5,1,2,3,4,5Howdoyouknowthis?Usedformeasuringhowwellyouralgorithmperforms,1,2,3,4,6pagefaults,4,5,OptimalPageReplacement,LeastRecentlyUsed(LRU)Algorithm,Referencestring:1,2,3,4,1,2,5,1,2,3,4,5CounterimplementationEverypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounterWhenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange,5,2,4,3,1,2,3,4,1,2,5,4,1,2,5,3,1,2,4,3,LRUPageReplacement,LRUAlgorithm(Cont.),Stackimplementationkeepastackofpagenumbersinadoublelinkform:Pagereferenced:moveittothetoprequires6pointerstobechangedNosearchforreplacement,UseOfAStacktoRecordTheMostRecentPageReferences,LRUApproximationAlgorithms,ReferencebitWitheachpageassociateabit,initially=0Whenpageisreferencedbitsetto1Replacetheonewhichis0(ifoneexists)Wedonotknowtheorder,howeverAdditional-ReferencebitAtimernbitsReferencebitsshiftSecondchanceNeedreferencebitClockreplacementIfpagetobereplaced(inclockorder)hasreferencebit=1then:setreferencebit0leavepageinmemoryreplacenextpage(inclockorder),subjecttosamerules,Second-Chance(clock)Page-ReplacementAlgorithm,CountingAlgorithms,KeepacounterofthenumberofreferencesthathavebeenmadetoeachpageLFUAlgorithm:replacespagewithsmallestcountMFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused,9.5AllocationofFrames,EachprocessneedsminimumnumberofpagesExample:IBM3706pagestohandleSSMOVEinstruction:instructionis6bytes,mightspan2pages2pagestohandlefrom2pagestohandletoTwomajorallocationschemesfixedallocationpriorityallocation,FixedAllocation,EqualallocationForexample,ifthereare100framesand5processes,giveeachprocess20frames.ProportionalallocationAllocateaccordingtothesizeofprocess,PriorityAllocation,UseaproportionalallocationschemeusingprioritiesratherthansizeIfprocessPigeneratesapagefault,selectforreplacementoneofitsframesselectforreplacementaframefromaprocesswithlowerprioritynumber,Globalvs.LocalAllocation,Globalreplacementprocessselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanotherLocalreplacementeachprocessselectsfromonlyitsownsetofallocatedframes,9.6Thrashing,Ifaprocessdoesnothave“enough”pages,thepage-faultrateisveryhigh.Thisleadsto:lowCPUutilizationoperatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramminganotherprocessaddedtothesystemThrashingaprocessisbusyswappingpagesinandout,Thrashing(Cont.),DemandPagingandThrashing,Whydoesdemandpagingwork?LocalitymodelProcessmigratesfromonelocalitytoanotherLocalitiesmayoverlapWhydoesthrashingoccur?sizeoflocalitytotalmemorysize,LocalityInAMemory-ReferencePattern,Working-SetModel,working-setwindowafixednumberofpagereferencesExample:10,000instructionWSSi(workingsetofProcessPi)=totalnumberofpagesreferencedinthemostrecent(variesintime)iftoosmallwillnotencompassentirelocalityiftoolargewillencompassseverallocalitiesif=willencompassentireprogramD=WSSitotaldemandframesifDmThrashingPolicyifDm,thensuspendoneoftheprocesses,Working-setmodel,KeepingTrackoftheWorkingSet,Approximatewithintervaltimer+areferencebitExample:=10,000Timerinterruptsafterevery5000timeunitsKeepinmemory2bitsforeachpageWheneveratimerinterruptscopyandsetsthevaluesofallreferencebitsto0Ifoneofthebitsinmemory=1pageinworkingsetWhyisthisnotcompletelyaccurate?Improvement=10bitsandinterruptevery1000timeunits,Page-FaultFrequencyScheme,Establish“acceptable”page-faultrateIfactualratetoolow,processlosesframeIfactualratetoohigh,processgainsframe,9.7Memory-MappedFiles,Memory-mappedfileI/OallowsfileI/OtobetreatedasroutinememoryaccessbymappingadiskblocktoapageinmemoryAfileisinitiallyreadusingdemandpaging.Apage-sizedportionofthefileisreadfromthefilesystemintoaphysicalpage.Subsequentreads/writesto/fromthefilearetreatedasordinarymemoryaccesses.SimplifiesfileaccessbytreatingfileI/Othroughmemoryratherthanread()write()systemcallsAlsoallowsseveralprocessestomapthesamefileallowingthepagesinmemorytobeshared,MemoryMappedFiles,Memory-MappedSharedMemoryinWindows,9.8AllocatingKernelMemory,TreateddifferentlyfromusermemoryOftenallocatedfromafree-memorypoolKernelrequestsmemoryforstructuresofvaryingsizesSomekernelmemoryneedstobecontiguous,BuddySystem,Allocatesmemoryfromfixed-sizesegmentconsistingofphysically-contiguouspagesMemoryallocatedusingpower-of-2allocatorSatisfiesrequestsinunitssizedaspowerof2Requestroundeduptonexthighestpowerof2Whensmallerallocationneededthanisavailable,currentchunksplitintotwobuddiesofnext-lowerpowerof2Continueuntilappropriatesizedchunkavailable,BuddySystemAllocator,SlabAllocator,AlternatestrategySlabisoneormorephysicallycontiguouspagesCacheconsistsofoneormoreslabsSinglecacheforeachuniquekerneldatastructureEachcachefilledwithobjectsinstantiationsofthedatastructureWhencachecreated,filledwithobjectsmarkedasfreeWhenstructuresstored,objectsmarkedasusedIfslabisfullofusedobjects,nextobjectallocatedfromemptyslabIfnoemptyslabs,newslaballocatedBenefitsincludenofragmentation,fastmemoryrequestsatisfaction,SlabAllocation,9.9OtherIssues-Prepaging,PrepagingToreducethelargenumberofpagefaultsthatoccursatprocessstartupPrepageallorsomeofthepagesaprocesswillneed,beforetheyarereferencedButifprepagedpagesareunused,I/OandmemorywaswastedAssumespagesareprepagedandofthepagesisusedIscostofs*savepagesfaultsorthanthecostofprepagings*(1-)unnecessarypages?nearzeroprepagingloses,OtherIssuesPageSize,Pagesizeselectionmusttakeintoconsideration:fragmentationtablesizeI/Ooverheadlocality,OtherIssuesTLBReach,TLBReach-TheamountofmemoryaccessiblefromtheTLBTLBReach=(TLBSize)X(PageSize)Ideally,theworkingsetofeachprocessisstoredintheTLBOtherwisethereisahighdegreeofpagefaultsIncreasethePageSizeThismayleadtoanincreaseinfragmentationasnotallapplicationsrequirealargepagesizeProvideMultiplePageSizesThisallowsapplicationsthatrequirelargerpagesizestheopportunitytousethemwithoutanincreaseinfragmentation,OtherIssuesProgramStructure,ProgramstructureInt128,128data;EachrowisstoredinonepageProgram1for(j=0;j128;j+)for(i=0;i128;i+)datai,j=0;128x128=16,384pagefaultsProgram2for(i=0;i128;i+)for(j=0;j128;j+)datai,j=0;128pagefaults,OtherIssuesI/Ointerlock,I/OInterlockPagesmustsometimesbelockedintomemoryConsiderI