CS162 Operating Systems and Systems Programming Lecture 13 Address Translation con t Caches and TLBs October 12 2009 Prof John Kubiatowicz http inst eecs berkeley edu cs162 Review Multi level Translation What about a tree of tables Lowest level page table memory still allocated with bitmap Higher levels often segmented Could have any number of levels Example top segment Virtual Virtual Virtual Offset Seg Page Address Base0Limit0 V Base1Limit1 V Base2Limit2 V Base3Limit3 N Base4Limit4 V Base5Limit5 N Base6Limit6 N Base7Limit7 V page page page page page page 0 V R 1 V R 2 V R W 3 V R W 4 N 5 V R W Access Error Physical Page Offset Physical Address Check Perm Access Error What must be saved restored on context switch Contents of top level segment registers for this example 10 12 09 Kubiatowicz CS162 UCB Fall 2009 Lec 13 2 Pointer to top level table page table 10 bits Review Two level page table PhysicalPhysical Page 10 bits Virtual Virtual Virtual Address P1 indexP2 index 12 bits Address Offset Offset 4KB PageTablePtr 4 bytes Tree of Page Tables Tables fixed size 1024 entries On context switch save single PageTablePtr register Sometimes top level page tables called directories Intel 4 bytes Each entry called a surprise Page Table Entry PTE CS162 UCB Fall 2009 10 12 09 Kubiatowicz Lec 13 3 Goals for Today Finish discussion of both Address Translation and Protection Caching and TLBs Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and 10 12 09 Kubiatowicz CS162 UCB Fall 2009 Lec 13 4 Gagne What is in a PTE What is in a Page Table Entry or PTE Pointer to next level page table or to actual page Permission bits valid read only read write write only Example Intel x86 architecture PTE Address same format previous slide 10 10 12 bit offset Intermediate page tables called Directories PWT PCD Page Frame Number Free 0 L D A UWP Physical Page Number OS 31 12 11 9 8 7 6 5 4 3 2 1 0 P Present same as valid bit in other architectures W Writeable U User accessible PWT Page write transparent external cache writethrough PCD Page cache disabled page cannot be cached A Accessed page has been accessed recently D Dirty PTE only page has been modified recently L L 1 4MB page directory only Bottom 22 bits of virtual address serve as offset 10 12 09 Kubiatowicz CS162 UCB Fall 2009 Lec 13 5 Examples of how to use a PTE How do we use the PTE Invalid PTE can imply different things Region of address space is actually invalid or Page directory is just somewhere else than memory Validity checked first OS can use other say 31 bits for location info Usage Example Demand Paging Keep only active pages in memory Place others on disk and mark their PTEs invalid Usage Example Copy on Write UNIX fork gives copy of parent address space to child Address spaces disconnected after child created How to do this cheaply Make copy of parent s page tables point at same memory Mark entries in both sets of page tables as read only Page fault on write creates two copies Usage Example Zero Fill On Demand New data pages must carry no information say be zeroed Mark PTEs as invalid page fault on use gets zeroed page Often OS creates zeroed pages in background 10 12 09 Kubiatowicz CS162 UCB Fall 2009 Lec 13 6 How is the translation accomplished CPU Virtual Addresses MMU Physical Addresse s What exactly happens inside MMU One possibility Hardware Tree Traversal For each virtual address takes page table base pointer and traverses the page table in hardware Generates a Page Fault if it encounters invalid PTE Fault handler will decide what to do More on this next lecture Pros Relatively fast but still many memory accesses Cons Inflexible Complex hardware Another possibility Software Each traversal done in software Pros Very flexible Cons Every translation must invoke Fault In fact need way to cache translations for either case 10 12 09 Kubiatowicz CS162 UCB Fall 2009 Lec 13 7 Dual Mode Operation Can Application Modify its own translation tables If it could could get access to all of physical memory Has to be restricted somehow To Assist with Protection Hardware provides at least two modes Dual Mode Operation Kernel mode or supervisor or protected User mode Normal program mode Mode set with bits in special control register only accessible in kernel mode Intel processor actually has four rings of protection PL Priviledge Level from 0 3 PL0 has full access PL3 has least Privilege Level set in code segment descriptor CS Mirrored IOPL bits in condition register gives permission to programs to use the I O instructions Typical OS kernels on Intel processors only use PL0 user and PL3 kernel 10 12 09 Kubiatowicz CS162 UCB Fall 2009 Lec 13 8 For Protection Lock User Programs in Asylum Idea Lock user programs in padded cell with no exit or sharp objects Cannot change mode to kernel mode User cannot modify page table mapping Limited access to memory cannot adversely effect other processes Side effect Limited access to memory mapped I O operations I O that occurs by reading writing memory locations Limited access to interrupt controller What else needs to be protected A couple of issues How to share CPU between kernel and user programs Kinda like both the inmates and the warden in asylum are the same person How do you manage this How do programs interact How does one switch between kernel and user modes 10 12 09 OS user kernel user mode getting into cell User OS user kernel mode getting out of cell Kubiatowicz CS162 UCB Fall 2009 Lec 13 9 How to get from Kernel User What does the kernel do to create a new user process Allocate and initialize address space control block Read program off disk and store in memory Allocate and initialize translation table Point at code in memory so program can execute Possibly point at statically initialized data Run Program Set machine registers Set hardware pointer to translation table Set processor status word for user mode Jump to start of program How does kernel switch between processes Same saving restoring of registers as before Save restore PSL hardware pointer to translation table 10 12 09 Kubiatowicz CS162 UCB Fall 2009 Lec 13 10 User Kernel System Call Can t let inmate user get out of padded cell on own Would defeat purpose of protection So how does the user program get back into kernel System call Voluntary procedure call into kernel Hardware for controlled User Kernel transition Can any kernel routine be called No Only specific ones System call ID encoded into
View Full Document
Unlocking...