Memory Replacement PoliciesCS241 AdministrativeConcepts this LectureIntroduction to Demand Paging - Paging PoliciesDemand Paging ExamplePage Replacement AlgorithmPage ReplacementPage Replacement IssuesSlide 9Page Replacement StrategiesTerminologySlide 12Principal of OptimalitySlide 14Optimal ExampleFIFOPaging Behavior with Increasing Number of Page FramesBelady's Anomaly (for FIFO)LRULeast Recently Used IssuesLRU and AnomaliesNUR: A LRU ApproximationSecond ChanceSlide 24Second Chance ExamplePage ClassesSummaryCS 241 Spring 2007System Programming 1Memory Replacement PoliciesLecture 32Klara Nahrstedt2CS241 AdministrativeRead Stallings Chapter 8.1 and 8.2 about VMLMP2 (Part II due on Monday, April 16)See also lecture notes, self-assessment quiz, discussion sectionLMP2 quiz on Monday, April 16If you found Dr. Cerf’s lecture interesting, you canPay attention next two weeks in cs241 were we cover socket interfaces to TCP/IP - InternetLearn more about Internet material in classes cs438 (Communication Networking – TCP/IP), cs425 (Distributed Systems), ece435 (Computer Networking Lab – Implementation of TCP/IP), cs414 (Multimedia Systems), cs463 (Computer Security3Concepts this LectureIntroduction to Demand PagingReplacementPrinciple of Optimality Replacement Policies4Introduction to Demand Paging - Paging PoliciesFetch Strategies When should a page be brought into primary (main) memory from secondary (disk) storage. Placement StrategiesWhen a page is brought into primary storage, where is it to be put? Replacement StrategiesWhich page now in primary storage is to be removed from primary storage when some other page or segment is to be brought in and there is not enough room.5Demand Paging ExampleLoad MiFree framePagetableVMreffault6Page Replacement Algorithmfind a free page frame if free page frame use itotherwise, select a page frame using the page replacement algorithmwrite the selected page to the disk and update any necessary tables find location of page on diskread the requested page from the disk.restart the user process.7Page Replacement It is necessary to be careful of synchronization problems. For example, page faults may occur for pages being paged out.8Page Replacement Issuesif no frames are free, a disk read and write of page is requiredif the page to be replaced has not been changed since it was read in, it can be discarded and does not need to be copied out to secondary storage.read only pages are never written but may be shared!9Page Replacement Issuesa dirty bit is set in the page table by hardware to indicate that the page has been modified.need to minimize page faults.reference string is the memory references generated by a program.10Page Replacement Strategiesthe principle of optimalityreplace the page that will not be used again the farthest time in the future.random page replacementchoose a page randomlyFIFO - first in first outreplace the page that has been in primary memory the longest11TerminologyReference string: the memory reference sequence generated by a program. Paging – moving pages to (from) diskOptimal – the best (theoretical) strategyEviction – throwing something out Pollution – bringing in useless pages/lines12Page Replacement StrategiesLRU - least recently usedreplace the page not used for the longest timeLFU - least frequently usedreplace the page that is used least oftenNUR - not used recentlyan approximation to LRU.working setkeep in memory those pages that the process is actively using.13Principal of Optimalityprovides a basis for comparison with other schemes.is difficult to implement because of trying to predict the reference string for a program.compiler technology can help by providing hints.14Principal of Optimalityif the reference string can be predicted accurately, then shouldn't use demand paging but should use pre-paging instead as this would allow paging activity of pages needed in the future to be overlapped with computation.15Optimal Example12 references, 7 faults16FIFO12 references, 9 faults17Paging Behavior with IncreasingNumber of Page Frames18Belady's Anomaly (for FIFO)As the number of page frames increase, so does the fault rate. 12 references, 10 faults19LRU12 references, 10 faults20Least Recently Used Issuesdoes not suffer from Belady's anomalyuse time record time of reference with page table entryuse counter as clocksearch for smallest time. use stack remove reference of page from stack (linked list)push it on top of stack both approaches require large processing overhead, more space, and hardware support.21LRU and AnomaliesAnomalies cannot occur, why? 12 references, 8 faults22NUR: A LRU Approximationadditional reference bits a register is kept per pagea one bit is set in the register if the page is referencedthe register is shifted by one after some time interval00110011 would be accessed more recently than 00010111the page with register holding the lowest number is the least recently used.the value may not be unique. use fifo to resolve conflicts.23Second Chancesecond chance algorithm uses a register size one: a reference bit. the page table entry has a reference bitinitially, the reference bit for a page is set to 0when a page is referenced, the page is set to 1pages are kept in FIFO order using a circular list.select head of FIFO24Second Chanceif page has reference bit set, reset bit and select next page in FIFO list.keep processing until reach page with zero reference bit and page that one out.system v, r4 uses a variant of second chance.25Second Chance Example12 references, 9 faults26Page Classes1.(0,0) neither referenced nor dirtied2.(0,1) not referenced (recently) but dirtied3.(1,0) referenced but clean4.(1,1) referenced and dirtied select a page from lowest class if conflict, use random or FIFO.27SummaryFetch, placement, page replacement.Demand paging algorithm.Simple page replacement policies. OptimalFIFO LRUNURSecond chance, page
View Full Document