CS162 Operating Systems and Systems Programming Lecture 15 Page Allocation and Replacement October 24 2005 Prof John Kubiatowicz http inst eecs berkeley edu cs162 Review Demand Paging Mechanisms PTE helps us implement demand paging Valid Page in memory PTE points at physical page Not Valid Page not in memory use info in PTE to find it on disk when necessary Suppose user references page with invalid PTE Memory Management Unit MMU traps to OS Resulting trap is a Page Fault What does OS do on a Page Fault Choose an old page to replace If old page modified D 1 write contents back to disk Change its PTE and any cached TLB to be invalid Load new page into memory from disk Update page table entry invalidate TLB for new entry Continue thread from original faulting location TLB for new page will be loaded when thread continued While pulling pages off disk for one process OS runs another process from ready queue 10 24 05 SuspendedKubiatowicz process CS162 sits on wait UCB Fall queue 2005 Lec 15 2 Review Software Loaded TLB MIPS Snake Nachos TLB is loaded by software High TLB hit rate ok to trap to software to fill the TLB even if slower Simpler hardware and added flexibility software can maintain translation tables in whatever convenient format How can a process run without hardware TLB fill Fast path TLB hit with valid 1 Translation to physical page done by hardware Slow path TLB hit with valid 0 or TLB miss Hardware receives a TLB Fault What does OS do on a TLB Fault Traverse page table to find appropriate PTE If valid 1 load page table entry into TLB continue thread If valid 0 perform Page Fault detailed previously Continue thread Everything is transparent to the user process It doesn t know about paging to from disk It doesn t even know about software TLB handling 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 3 OS Load TLB Faulting Inst 2 Faulting Inst 2 TLB Faults Faulting Inst 1 User Faulting Inst 1 Review Transparent Exceptions Fetch page Load TLB Hardware must help out by saving Faulting instruction and partial state Processor State sufficient to restart user thread Save restore registers stack etc Precise Exception state of the machine is preserved as if program executed up to the offending instruction All previous instructions completed Offending instruction and all following instructions act as if they have not even started Difficult with pipelining out of order execution MIPS takes this position Modern techniques for out of order execution and branch prediction help implement precise interrupts 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 4 Goals for Today Page Replacement Policies Clock Algorithm Nth chance algorithm Second Chance List Algorithm Page Allocation Policies Working Set Thrashing Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 5 Gagne Steps in Handling a Page Fault 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 6 Demand Paging Example Since Demand Paging like caching can compute average access time Effective Access Time EAT Hit Rate x Hit Time Miss Rate x Miss Time Example Memory access time 200 nanoseconds Average page fault service time 8 milliseconds Suppose p Probability of miss 1 p Probably of hit Then we can compute EAT as follows EAT 1 p x 200ns p x 8 ms 1 p x 200ns p x 8 000 000ns 200ns p x 7 999 800ns If one access out of 1 000 causes a page fault then EAT 8 2 s This is a slowdown by a factor of 40 What if want slowdown by less than 10 200ns x 1 1 EAT p 2 5 x 10 6 This is about 1 page fault in 400000 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 7 What Factors Lead to Misses Compulsory Misses Pages that have never been paged into memory before How might we remove these misses Prefetching loading them into memory before needed Need to predict future somehow More later Capacity Misses Not enough memory Must somehow increase size Can we do this One option Increase amount of DRAM not quick fix Another option If multiple processes in memory adjust percentage of memory allocated to each one Conflict Misses Technically conflict misses don t exist in virtual memory since it is a fully associative cache Policy Misses Caused when pages were in memory but kicked out prematurely because of the replacement policy How to fix Better replacement policy 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 8 Page Replacement Policies Why do we care about Replacement Policy Replacement is an issue with any cache Particularly important with pages The cost of being wrong is high must go to disk Must keep important pages in memory not toss them out FIFO First In First Out Throw out oldest page Be fair let every page live in memory for same amount of time Bad because throws out heavily used pages instead of infrequently used pages MIN Minimum Replace page that won t be used for the longest time Great but can t really know future Makes good comparison case however RANDOM Pick random page for every replacement Typical solution for TLB s Simple hardware Pretty unpredictable makes it hard to make realtime guarantees 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 9 Replacement Policies Con t LRU Least Recently Used Replace page that hasn t been used for the longest time Programs have locality so if something not used for a while unlikely to be used in the near future Seems like LRU should be a good approximation to MIN How to implement LRU Use a list Head Page 6 Page 7 Page 1 Page 2 Tail LRU On each use remove page from list and place at head LRU page is at tail Problems with this scheme for paging Need to know immediately when each page used so that can change position in list Many instructions for each hardware access In practice 10 24 05 people approximate Kubiatowicz CS162 UCB FallLRU 2005 more later Lec 15 10 Example FIFO Suppose we have 3 page frames 4 virtual pages and following reference stream ABCABDADBCB Consider FIFO Page replacement Ref Page A 1 A 2 3 B C A B D A D B D B C B C A C B FIFO 7 faults When referencing D replacing A is bad choice since needKubiatowicz A againCS162 right away 10 24 05 UCB Fall 2005 Lec 15 11 Example MIN Suppose we have the same reference stream ABCABDADBCB Consider MIN Page replacement Ref Page A 1 A 2 3 B C A B D A D B C B C B C D MIN 5 faults Where will D be brought in Look for page not referenced farthest in future What will LRU do Same decisions as MIN here but won t always be 10 24 05 Kubiatowicz CS162 UCB Fall 2005 Lec 15 12 true
View Full Document
Unlocking...