CS162Operating Systems andSystems ProgrammingLecture 15Page Allocation and ReplacementOctober 22, 2008Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 15.210/22/08Kubiatowicz CS162 ©UCB Fall 2008• 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» Suspended process sits on wait queueReview: Demand Paging MechanismsLec 15.310/22/08Kubiatowicz CS162 ©UCB Fall 2008Goals for Today• Precise Exceptions• Page Replacement Policies– Clock Algorithm– Nthchance algorithm– Second-Chance-List Algorithm• Page Allocation Policies• Working Set/ThrashingNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne Note: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated from my lecture notes by Kubiatowicz.Lec 15.410/22/08Kubiatowicz CS162 ©UCB Fall 2008Software-Loaded TLB• MIPS/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 handlingLec 15.510/22/08Kubiatowicz CS162 ©UCB Fall 2008Transparent Exceptions• How to transparently restart faulting instructions?– Could we just skip it? » No: need to perform load or store after reconnecting physical page• Hardware must help out by saving:– 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» Save/restore registers, stack, etc• What if an instruction has side-effects?Load TLBFaultingInst 1FaultingInst 1FaultingInst 2FaultingInst 2Fetch page/Load TLBUserOSTLB FaultsLec 15.610/22/08Kubiatowicz CS162 ©UCB Fall 2008Consider weird things that can happen• What if an instruction has side effects?– 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?– 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• What about “RISC” processors?– For instance delayed branches?» Example: bne somewhereld r1,(sp)» Precise exception state consists of two PCs: PC and nPC– Delayed exceptions:» Example: div r1, r2, r3ld r1, (sp)» What if takes many cycles to discover divide by zero, but load has already caused page fault?Lec 15.710/22/08Kubiatowicz CS162 ©UCB Fall 2008Precise Exceptions• 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 interruptsLec 15.810/22/08Kubiatowicz CS162 ©UCB Fall 2008Steps in Handling a Page FaultLec 15.910/22/08Kubiatowicz CS162 ©UCB Fall 2008Demand 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!Lec 15.1010/22/08Kubiatowicz CS162 ©UCB Fall 2008What 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 policyLec 15.1110/22/08Kubiatowicz CS162 ©UCB Fall
View Full Document
Unlocking...