CS 162 Operating Systems and Systems Programming Allow more programs than will fit in memory to be running at same time Professor Anthony D Joseph Spring 2004 15 2 Demand Paging Mechanism Lecture 15 Caching Demand Paged Virtual Memory 15 0 Main Points If present pointer to page frame in memory If not present go to disk 2 Hardware traps to OS on reference to invalid page In MIPS Nachos trap on TLB miss OS checks page table valid bit 3 OS software Concept of paging to disk Replacement policies a Choose an old page to replace b If old page has been modified write contents back to disk For implementation details read Levy and Lipman paper c Change its page table entry and TLB entry d Load new page into memory from disk e Update page table entry f Continue thread All this is transparent OS just runs another job in the meantime 15 1 Demand Paging Up to now all of a job s virtual address space must be in physical memory But programs don t use all of their memory all of the time In fact there is a 9010 rule programs spend 90 of their time in 10 of their code Instead use main memory as a cache for disk Some pages in memory some on disk virtual address space 1 Page table has present valid bit 15 2 1 Software loaded TLB Instead of having the hardware load the TLB when a translation doesn t match the MIPS Snake Nachos TLB is software loaded Idea is if have high TLB hit rate ok to trap to software to fill TLB even if it s a bit slower How do we implement this How can a process run without access to a page table physical memory Basic mechanism just generalization of above 1 TLB has present valid bit if present pointer to page frame in memory if not present use software page table 2 Hardware traps to OS on reference not in TLB page table 3 OS software a check if page is in memory b if yes load page table entry into TLB c if no perform page fault operations outlined above disk Benefits Bigger virtual address space illusion of infinite memory CS 162 Spring 2004 Lecture 15 d continue thread 1 15 CS 162 Spring 2004 Lecture 15 2 15 Paging to disk or even having software load the TLB all this is transparent job doesn t know it happened dest begin source begin 15 2 2 Transparent page faults dest end source end Need to transparently re start faulting instruction Hardware must help out by saving 1 Faulting instruction need to know which instruction caused fault No way to unwind instruction 2 Processor state 15 3 Page replacement policies What if an instruction has side effects CISC processors Replacement policy is an issue with any caching system mov sp 10 15 3 1 Random Typical solution for TLB s Easy to implement in hardware Two options Unwind side effects Finish off side effects 15 3 2 FIFO Throw out oldest page Be fair let every page live in memory for the same amount of time then toss it Are RISCs easier What about delayed loads Delayed branches ld sp r1 What if next instruction causes page fault while load is still in progress Have to save enough state to allow CPU to restart Lots of hardware designers don t think about virtual memory For example block transfer instruction Source destination can be overlapping destination before source Overwrite part of source as instruction proceeds Bad because throws out heavily used pages instead of those that are not frequently used 15 3 3 MIN Replace page that won t be used for the longest time into the future 15 3 4 LRU Replace page that hasn t been used for the longest time If induction works LRU is a good approximation to MIN Actually people don t use even LRU they approximate it CS 162 Spring 2004 Lecture 15 3 15 CS 162 Spring 2004 Lecture 15 4 15 15 3 5 Example Suppose we have 3 page frames and 4 virtual pages with the reference string A B C A B D A D B C B virtual page references Ref String s slot A 1 A 2 What happens with FIFO Ref String slot A 1 A 2 B A B D A D B D C Ref String s slot A 1 A 2 1 A 2 B C A B D A D B C B C B 3 C A B C D D E D B C D A 1 A B E A B C C E A C A B D B Ref String s slot 3 C B D A B D E A B C E B C D E D A 4 E B D C Example of Belady s Anomaly with FIFO replacement What about LRU Same decisions as MIN but won t always be this way When will LRU perform badly When next reference is to the least recently used page With FIFO contents of memory can be completely different with different number of page frames Reference string A B C D A B C D A B C D By contrast with LRU or MIN the contents of memory with X pages are a subset of contents with X 1 pages So with LRU or MIN having more pages never hurts Ref String s slot A 1 A 3 D B 3 2 D Page faults in physical memory with MIN replacement 2 C Yes for LRU MIN No for FIFO Belady s anomaly What about MIN A B Page faults in physical memory with MIN replacement B Page faults in physical memory with FIFO replacement Ref String s slot A 15 3 6 Does adding memory always reduce the number of page faults A C D C C B C C B 3 C B 3 B B C D A B D B D A C A C C C D B D B B C A D Page faults in physical memory with LRU replacement Same behavior with FIFO What about MIN CS 162 Spring 2004 Lecture 15 5 15 CS 162 Spring 2004 Lecture 15 6 15 15 4 3 Nth Chance 15 4 Implementing LRU Nth chance algorithm don t throw page out until hand has swept by n times 15 4 1 Perfect Timestamp page on each reference Keep list of pages ordered by time of reference OS keeps counter per page of sweeps On page fault OS checks use bit 1 clear use and also clear counter go on 0 increment counter if N go on else replace page 15 4 2 Clock algorithm Approximate LRU approx to approx to MIN Replace an old page not the oldest page Clock algorithm arrange physical pages in a circle with a clock hand 1 Hardware keeps use bit per physical page frame 2 Hardware sets use bit on each reference If use bit isn t set means not referenced in a long time 3 On page …
View Full Document
Unlocking...