操作系统教程09.ppt

Chapter9 VirtualMemory BackgroundDemandPagingCopy on WritePageReplacementAllocationofFramesThrashingMemory MappedFilesAllocatingKernelMemory Background VirtualmemorySeparationofuserlogicalmemoryfromphysicalmemoryOnlypartoftheprograminmemoryLogicaladdressspace physicaladdressspaceInmanycases theentireprogramnotneeded ErrorcodeArrays lists tablesallocatedmorethanneedCertainoptions featuresofaprogramrarelyused Background Benefits ProgramscanbelargerthanphysicalmemoryProgrammersneedn tcareaboutmemorylimitationsMoreprogramscouldberunsimultaneouslyLessI Oneeded eachuserprogramwouldrunfasterEasy2sharefilesamongseveralprocessesMoreefficientprocesscreationDrawbacks VirtualMemoryThatisLargerThanPhysicalMemory Virtual addressSpace Sparseaddressspaces holes SharedLibraryUsingVirtualMemory LibrarycanbesharedCommunicationFork systemcall VirtualMemory Virtualmemorycanbeimplementedvia DemandpagingPagingondemandDemandsegmentationSegmentingondemand DemandPaging PagingondemandBringapageintomemoryonlywhenitisneededLessI OneededLessmemoryneededFasterresponseMoreusersLazyswapperneverswapsapageintomemoryunlesspagewillbeneededSwapperthatdealswithpagesisapager TransferofaPagedMemorytoContiguousDiskSpace Valid InvalidBit Avalid invalidbitforeachpagetableentryAllaresettoiinitiallyv in memory legali not in memory pagefaultwhenreferencedinvalidreference abortnot in memory bringtomemory PageTableWhenSomePagesAreNotinMainMemory PageFault pagefaultFirstreferencetoapagewilltraptooperatingsystem Invalidreference abortValidbutnotinmemoryFindafreeframe fromthefreeframelist SwappageintoframeResetpagetablesSetvalidationbit vRestarttheinstructionthatcausedthepagefault StepsinHandlingaPageFault PageFault Cont RestartinstructionC A B1 fetchtheinstruction2 fetchA3 fetchB4 AddAandB5 StorethesuminC Cnotinmemory ProblemscanbeignoredRepetition1instructioncauseNpagefaults PageFault Cont Restartinstruction1instructionmodifyNlocationsE g MVC movecharacter canmove256bytesBlocksmaystraddlesapageboundaryPagefaultoccuraftermoveispartiallydoneIfthesource destinationblocksoverlapThesourceblockmayhavebeenchangedSolutionsAttempttoaccessbothendsof2blocksUsetempregisterstoholdthevaluesoverwritten PerformanceofDemandPaging PageFaultRate0 p 1 0ifp 0nopagefaultsifp 1 everyreferenceisafault PuredemandpagingEffectiveAccessTime EAT EAT 1 p xmemoryaccess pxpagefaulttime pagefaultoverhead swappageout optional swappagein restartoverhead DemandPagingExample Memoryaccesstime 200nanosecondsAveragepage faultservicetime 8millisecondsEAT 1 p x200 p 8milliseconds 1 px200 px8 000 000 200 px7 999 800Ifoneaccessoutof1 000causesapagefault thenEAT 8 2microseconds Thisisaslowdownbyafactorof40 ProcessCreation Virtualmemoryallowsotherbenefitsduringprocesscreation Copy on Write Memory MappedFiles later Copy on Write Copy on Write COW parent childprocessestoinitiallysharethesamepagesinmemoryIfeitherprocessmodifiesasharedpage pagecopiedOnlypagescanbemodifiedneedtobemarkedMoreefficientprocesscreationAllocatefreepagesfromazeroed outpagepoolZero fill on demand BeforeProcess1ModifiesPageC AfterProcess1ModifiesPageC Whathappensifthereisnofreeframe Pagereplacementfindsomepageinmemory butnotreallyinuse swapitoutalgorithmperformance analgorithmwhichwillresultinminimumnumberofpagefaultsSamepagemaybebroughtintomemoryseveraltimes PageReplacement Preventover allocationofmemoryModifypage faultserviceroutinetoincludepagereplacementmodify dirty bitreduceoverheadofpagetransfers onlymodifiedpagesarewrittentodiskSeparationbetweenlogicalmemoryandphysicalmemorylargevirtualmemorycanbeprovidedonasmallerphysicalmemoryFrame allocation page replacementalgorithmsareneededtoimplementdemandpaging NeedForPageReplacement BasicPageReplacement FindthelocationofthedesiredpageondiskFindafreeframe Ifthereisafreeframe useit Ifthereisnofreeframe useapagereplacementalgorithmtoselectavictimframeBringthedesiredpageintothe newly freeframe updatethepageandframetablesRestarttheprocess PageReplacement PageReplacementAlgorithms Criteria lowestpage faultrateEvaluatealgorithmbyrunningitonaparticularstringofmemoryreferences referencestring computingthenumberofpagefaultsonthatstringInallourexamples thereferencestringis1 2 3 4 1 2 5 1 2 3 4 5 GraphofPageFaultsVersusTheNumberofFrames Expected First In First Out FIFO Algorithm Referencestring 1 2 3 4 1 2 5 1 2 3 4 53frames 3pagescanbeinmemoryatatimeperprocess 9pagefaults 2 1 3 4 2 1 5 1 3 2 4 5 FIFO cont Referencestring 1 2 3 4 1 2 5 1 2 3 4 54framesBelady sAnomaly moreframes morepagefaults 10pagefaults 2 1 3 4 2 1 5 1 3 2 4 5 FIFOPageReplacement FIFOIllustratingBelady sAnomaly OptimalAlgorithm Replacepagenotbeusedforlongestperiodoftime4framesexampleHowdoyouknowthis Usedformeasuringhowwellyouralgorithmperforms 6pagefaults 2 1 3 4 2 1 5 1 3 2 4 5 OptimalPageReplacement LeastRecentlyUsed LRU Algorithm Referencestring CounterimplementationEverypageentryhasacounter everytimepageisreferencedthroughthisentry copytheclockintothecounterWhenapageneedstobechanged lookatthecounterstodeterminewhicharetobechanged 5 1 2 3 4 1 2 5 1 2 3 4 2 1 3 4 2 1 5 1 3 2 4 5 8Pagefaults LRUPageReplacement LRUAlgorithm Cont Stackimplementation keepastackofpagenumbersinadoublylinkedlist Pagereferenced moveittothetoprequires6pointerstobechangedatworstEachupdateisalittlemoreexpensiveButnosearchforreplacement UseOfAStacktoRecordTheMostRecentPageReferences LRUApproximationAlgorithms ReferencebitHWassociatewitheachpageabit initially 0Whenpageisreferenced bitissetto1Replacetheonewhichis0 ifoneexists Wedonotknowtheorder howeverAdditionalreferencebitalgorithmRecordeachentryofapagetableentrywitha8 bitbyteAtanregularinterval atimerinterrupttransfersthecontrol2theOSThebitsshiftright values 00000000111111110110011111001000 LRUApproximationAlgorithms SecondchanceNeedreferencebitClockreplacementIfpagetobereplaced inclockorder hasreferencebit 0 thenreplaceIfpagetobereplacedhasreferencebit 1then setreferencebit0leavepageinmemoryreplacenextpage inclockorder subjecttosamerules Second Chance clock Page ReplacementAlgorithm CountingAlgorithms KeepacounterofthenumberofreferencesthathavebeenmadetoeachpageLFUAlgorithmreplacespagewithsmallestcountProblem heavilyusedinitially thenneverusedShiftthecountsrightby1bit2decayaverageusagecountMFUAlgorithmthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused AllocationofFrames Processneedsminimumnumberofpages causePagenumber processexecution Enough2holdallpagesaninstructionreferencesE g indirectaddressingE g IBM370 6pagestohandleMVCinstruction instructionis6bytes mightstraddle2pages2pagestohandlefrom2pagestohandletoTwomajorallocationschemesfixedallocationpriorityallocation FixedAllocation Equalallocation e g ifthereare100framesand5processes giveeachprocess20frames Proportionalallocation Allocateaccordingtothesizeofprocess PriorityAllocation UseaproportionalallocationschemeusingprioritiesratherthansizeIfprocessPigeneratesapagefault select4replacementoneofitsframesSelect4replacementaframefromaprocesswithlowerprioritynumber Globalvs LocalAllocation GlobalreplacementprocessselectsareplacementframefromthesetofallframesoneprocesscantakeaframefromanotherProb processcan tcontrolitspage faultrateLocalreplacementeachprocessselectsfromonlyitsownsetofallocatedframesProb lessusedpagesofmemory Thrashing Ifaprocessdoesnothave enough pages thepage faultrateisveryhighlowCPUutilizationOSthinksthatitneedstoincreasethedegreeofmultiprogramminganotherprocessaddedtothesystemThrashing aprocessisbusyswappingpagesinandoutSpendingmoretimeinswappingthanexecuting Thrashing Cont DemandPagingandThrashing Whydoesdemandpagingwork LocalitymodelhowmanypagesaprocessusingProcessmigratesfromonelocalitytoanotherAprogrammayhaveNlocalities theymayoverlapWhydoesthrashingoccur sizeoflocality totalmemorysizeActivepages framesallocated LocalityInAMemory ReferencePattern Working SetModel working setwindowafixednumberofpagereferencese g 10 000instructionWSSi workingsetsizeofPi totalno ofpagesreferencedinthemostrecent variesintime if toosmallwillnotencompassentirelocalityif toolargewillencompassseverallocalitiesif willencompassentireprogram Working setmodel D WSSi totaldemandframesm totalno ofavailableframesifD m ThrashingPolicy ifD m thensuspendoneoftheprocesses KeepingTrackoftheWorkingSet Approximatewithfixed intervaltimer areferencebitE g 10 000Timerinterruptsafterevery5000timeunitsKeepinmemory2bitsforeachpageWheneveratimerinterruptscopyandsetsthevaluesofallreferencebitsto0Ifoneofthebitsinmemory 1 pageinworkingsetWhyisthisnotcompletelyaccurate Improvement 10bitsandinterruptevery1000timeunits Page FaultFrequencyScheme Establish acceptable page faultrateIfactualratetoolow processlosesframeIfactualratetoohigh processgainsframe Memory MappedFiles Memory mappedfilemappingadiskblocktoapageinmemoryTreatfileI OasroutinememoryaccessMechanismAfileisinitiallyreadusingdemandpagingApage sizedportionofthefileisreadintoaphysicalpageSubsequentreads writesto fromthefilearetreatedasordinarymemoryaccesses Memory MappedFiles SimplifiesfileaccessWritestoMemory mappedfilescanbe SynchronouswriteAsynchronouswriteNprocessesmaymapthesamefileconcurrentlyallowingthepagesinmemorytobesharedWritesby1processcanbeseenbyallothersSupportcopy on write MemoryMappedFiles Memory MappedSharedMemoryinWindows 1stprocesscreatesafilemapping establishaview2ndopen createaviewofthefileinitsvirtualaddressspace AllocatingKernelMemory TreateddifferentlyfromusermemoryOftenallocatedfromafree memorypoolKernelrequestsmemoryforstructuresofvaryingsizesManyOSsdonotsubjectkernelcode datatopagingSomekernelmemoryneedstobecontiguousCertainhwdevicesinteractdirectlywithphysicalmemory BuddySystem Allocatesmemoryfromfixed sizesegmentconsistingofphysically contiguouspagesMemoryallocatedusingpower of 2allocatorSatisfiesrequestsinunitssizedaspowerof2Requestroundeduptonexthighestpowerof2Whensmallerallocationneededthanisavailablecurrentchunksplitinto2buddiesofnext lowerpowerof2ContinueuntilappropriatesizedchunkavailableCoalescingAdjacentbuddiescanbecombinedquickly BuddySystemAllocator 4a21KBrequest SlabAllocator SlabisoneormorephysicallycontiguouspagesCacheconsistsofoneormoreslabsSinglecacheforeachuniquekerneldatastructureEachcachefilledwithobjects instantiationsofthedatastructure E g semaphores fileobjectsWhencachecreated filledwithobjectsmarkedasfreeWhenstructuresstored objectsmarkedasusedIfslabfullofusedobjects nextobjectallocatedfromemptyslabIfnoemptyslabs newslaballocatedBenefitsincludenofragmentationfastmemoryrequestsatisfaction SlabAllocation OtherIssues Prepaging PrepagingToreducetheno ofpagefaultsatprocessstartupPrepageall someofthepagesaprocesswillneed beforetheyarereferencedButifprepagedpagesareunused I OandmemorywaswastedAssumespagesareprepagedand ofthepagesisusedIscostofs savepagesfaults or thanthecostofprepagings 1 unnecessarypages nearzero prepagingloses OtherIssues TLBReach TLBReach TheamountofmemoryaccessiblefromtheTLBTLBReach TLBSize X PageSize Ideally theworkingsetofeachprocessisstoredintheTLBOtherwisethereisahighdegreeofpagefaultsIncreasethePageSizeThismayleadtoani