Review Demand Paging Mechanisms PTE helps us implement demand paging CS162 Operating Systems and Systems Programming Lecture 15 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 Page Allocation and Replacement What does OS do on a Page Fault October 22 2008 Prof John Kubiatowicz http inst eecs berkeley edu cs162 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 Suspended process sits on wait queue 10 22 08 Goals for Today Kubiatowicz CS162 UCB Fall 2008 Lec 15 2 Software Loaded TLB MIPS Nachos TLB is loaded by software Precise Exceptions Page Replacement Policies 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 Clock Algorithm Nth chance algorithm Second Chance List Algorithm How can a process run without hardware TLB fill Fast path TLB hit with valid 1 Translation to physical page done by hardware Page Allocation Policies Working Set Thrashing Slow path TLB hit with valid 0 or TLB miss Hardware receives a TLB Fault What does OS do on a TLB Fault Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne Gagne Many slides generated from my lecture notes by Kubiatowicz 10 22 08 Kubiatowicz CS162 UCB Fall 2008 Lec 15 3 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 22 08 Kubiatowicz CS162 UCB Fall 2008 Lec 15 4 OS Load TLB Consider weird things that can happen What if an instruction has side effects Faulting Inst 2 Faulting Inst 2 TLB Faults Faulting Inst 1 User Faulting Inst 1 Transparent Exceptions Options Unwind side effects easy to restart Finish off side effects messy Example 1 mov sp 10 What if page fault occurs when write to stack pointer Did sp get incremented before or after the page fault Fetch page Load TLB How to transparently restart faulting instructions Example 2 strcpy r1 r2 Source and destination overlap can t unwind in principle IBM S 370 and VAX solution execute twice once read only Could we just skip it No need to perform load or store after reconnecting physical page Hardware must help out by saving What about RISC processors For instance delayed branches Example bne somewhere ld r1 sp Precise exception state consists of two PCs PC and nPC Faulting instruction and partial state Need to know which instruction caused fault Is single PC sufficient to identify faulting position Processor State sufficient to restart user thread Delayed exceptions Example Save restore registers stack etc What if an instruction has side effects 10 22 08 Kubiatowicz CS162 UCB Fall 2008 Lec 15 5 10 22 08 Precise Exceptions div r1 r2 r3 ld r1 sp What if takes many cycles to discover divide by zero but load has already caused page fault Kubiatowicz CS162 UCB Fall 2008 Lec 15 6 Steps in Handling a Page Fault Precise 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 Same system code will work on different implementations Difficult in the presence of pipelining out of order execution MIPS takes this position Imprecise system software has to figure out what is where and put it all back together Performance goals often lead designers to forsake precise interrupts system software developers user markets etc usually wish they had not done this Modern techniques for out of order execution and branch prediction help implement precise interrupts 10 22 08 Kubiatowicz CS162 UCB Fall 2008 Lec 15 7 10 22 08 Kubiatowicz CS162 UCB Fall 2008 Lec 15 8 Demand Paging Example Since Demand Paging like caching can compute average access time Effective Access Time What Factors Lead to Misses Compulsory Misses 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 22 08 Kubiatowicz CS162 UCB Fall 2008 Lec 15 9 Page Replacement Policies Why do we care about Replacement Policy 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 real time guarantees Kubiatowicz CS162 UCB Fall 2008 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 22 08 Kubiatowicz CS162 UCB Fall 2008 Lec 15 10 Replacement Policies Con t LRU Least Recently Used
View Full Document
Unlocking...