Slide 1Virtual Memory Management Fundamental issues : A RecapPage Replacement Algorithms ConceptPage Replacement Algorithms Evaluation methodologyOptimal Page Replacement Clairvoyant replacementSlide 6Local Page Replacement FIFO replacementSlide 8Least Recently Used Page Replacement Use the recent past as a predictor of the near futureSlide 10Least Recently Used Page Replacement ImplementationSlide 12Slide 13Approximate LRU Page Replacement The Clock algorithmClock Page Replacement ExampleSlide 16Optimizing Approximate LRU Replacement The Second Chance algorithmThe Second Chance Algorithm ExampleSlide 19The Problem With Local Page Replacement How much memory do we allocate to a process?Slide 21Page Replacement Algorithms PerformanceOptimal Page Replacement For processes with a variable number of framesSlide 24Explicitly Using Locality The working set model of page replacementWorking Set Page Replacement ImplementationSlide 27Page-Fault-Frequency Page Replacement An alternate working set computationPage-Fault-Frequency Page Replacement Example, window size = 2Slide 30Load Control Fundamental tradeoffLoad Control How not to do it: Base load control on CPU utilizationLoad Control ThrashingSlide 341Page Replacement Algorithms2Virtual Memory ManagementFundamental issues : A RecapKey concept: Demand paging Load pages into memory only when a page fault occurs Issues:Placement strategiesPlace pages anywhere – no placement policy required Replacement strategiesWhat to do when there exist more jobs than can fit in memoryLoad control strategiesDetermining how many jobs can be in memory at one timeOperating SystemOperating SystemUser Program 1User Program 1User Program 2User Program 2User Program 2User Program 2User Program nUser Program n...Memory3Page Replacement AlgorithmsConceptTypically i VASi >> Physical MemoryWith demand paging, physical memory fills quicklyWhen a process faults & memory is full, some page must be swapped outHandling a page fault now requires 2 disk accesses not 1!Though writes are more efficient than reads (why?)Which page should be replaced?Local replacement — Replace a page of the faulting processGlobal replacement — Possibly replace the page of another process4Page Replacement AlgorithmsEvaluation methodologyRecord a trace of the pages accessed by a processExample: (Virtual) address trace...(3,0), (1,9), (4,1), (2,1), (5,3), (2,0), (1,9), (2,4), (3,1), (4,8)generates page trace3, 1, 4, 2, 5, 2, 1, 2, 3, 4 (represented as c, a, d, b, e, b, a, b, c, d)Hardware can tell OS when a new page is loaded into the TLBSet a used bit in the page table entryIncrement or shift a registerSimulate the behavior of a page replacement algorithm on the trace and record the number of page faults generatedfewer faults better performance5Optimal Page ReplacementClairvoyant replacementReplace the page that won’t be needed for the longest time in the futurec a d b e b a b c dFaultsPageFrames0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimeTime pageneeded next6Optimal Page ReplacementClairvoyant replacementReplace the page that won’t be needed for the longest time in the futurec a d b e b a b c da a a a a a a a a db b b b b b b b b bc c c c c c c c c cFaults • •PageFramesd d d d e e e e e e0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimea = 7b = 6c = 9d = 10Time pageneeded nexta = 15b = 11c = 13d = 147Local Page ReplacementFIFO replacementSimple to implementA single pointer sufficesPerformance with 4 page frames:c a d b e b a b c dFaultsPageFrames0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimePhysicalMemory023Frame List8Local Page ReplacementFIFO replacementSimple to implementA single pointer sufficesPerformance with 4 page frames:c a d b e b a b c da a a a e e e e e db b b b b b a a a ac c c c c c c b b bFaults • • • • •PageFramesd d d d d d d d c c0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimePhysicalMemory023Frame List9Least Recently Used Page ReplacementUse the recent past as a predictor of the near futureReplace the page that hasn’t been referenced for the longest timec a d b e b a b c dFaultsPageFrames0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimeTime pagelast used10Least Recently Used Page ReplacementUse the recent past as a predictor of the near futureReplace the page that hasn’t been referenced for the longest timec a d b e b a b c da a a a a a a a a ab b b b b b b b b bc c c c e e e e e dFaults • • •PageFramesd d d d d d d d c c0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimea = 2b = 4c = 1d = 3Time pagelast useda = 7b = 8e = 5d = 3a = 7b = 8e = 5c = 911Least Recently Used Page ReplacementImplementationMaintain a “stack” of recently used pagesc a d b e b a b c da a a a a a a a a ab b b b b b b b b bc c c c e e e e e dFaults • • •PageFramesd d d d d d d d c c0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimeccccaaccaaddccaaddbbaaddbbeeaaddeebbddeebbaaddeeaabbeeaabbccaabbccddLRUpage stackPage to replaceccddee12Least Recently Used Page ReplacementImplementationMaintain a “stack” of recently used pagesc a d b e b a b c da a a a a a a a a ab b b b b b b b b bc c c c e e e e e dFaults • • •PageFramesd d d d d d d d c c0123abcd1 2 3 4 5 6 7 8 9 100RequestsTimeccacadcadbadbeadebdebadeabeabcabcdLRUpage stackPage to replacecd e13What is the goal of a page replacement algorithm?A. Make life easier for OS implementerB. Reduce the number of page faultsC. Reduce the penalty for page faults when they occurD. Minimize CPU time of algorithm14Approximate LRU Page ReplacementThe Clock algorithmMaintain a circular list of pages resident in memoryUse a clock (or used/referenced) bit to track how often a page is accessed The bit is set whenever a page is referencedClock hand sweeps over pages looking for one with used bit = 0Replace pages that haven’t been referenced for one complete revolution of the clockfunc Clock_Replacementbegin while (victim page not found) do if(used bit for current page = 0) then replace current page else reset used bit end if advance clock pointer end whileend Clock_Replacementresident bitused bit frame number01Page 7:150Page 1:1 30Page 4:141Page 0:111Page 3:115dcbacClock Page ReplacementExampleFaultsPageFrames0123abcd0RequestsTimePage table entriesfor resident