Review Multi level Translation What about a tree of tables CS162 Operating Systems and Systems Programming Lecture 13 Lowest level page table memory still allocated with bitmap Higher levels often segmented Could have any number of levels Example top segment Virtual Address Address Translation con t Caches and TLBs Virtual Seg Base0 Base1 Base2 Base3 Base4 Base5 Base6 Base7 October 13 2008 Prof John Kubiatowicz http inst eecs berkeley edu cs162 Virtual Page Limit0 Limit1 Limit2 Limit3 Limit4 Limit5 Limit6 Limit7 V V V N V N N V Offset page page page page page page 0 V R 1 V R 2 V R W 3 V R W N 4 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 Pointer to top level table page table 10 13 08 Review Two level page table 10 bits 10 bits Virtual Virtual Virtual Address P1 index P2 index 12 bits Physical Physical Address Page Offset Offset 4KB Kubiatowicz CS162 UCB Fall 2008 Lec 13 2 Goals for Today Finish discussion of both Address Translation and Protection Caching and TLBs 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 Each entry called a surprise Page Table Entry PTE 10 13 08 Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne 4 bytes Kubiatowicz CS162 UCB Fall 2008 Lec 13 3 10 13 08 Kubiatowicz CS162 UCB Fall 2008 Lec 13 4 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 10 13 08 PCD P W U PWT PCD A D L Free 0 L D A UW P OS 11 9 8 7 6 5 4 3 2 1 0 PWT Page Frame Number Physical Page Number 31 12 Present same as valid bit in other architectures Writeable User accessible Page write transparent external cache write through Page cache disabled page cannot be cached Accessed page has been accessed recently Dirty PTE only page has been modified recently L 1 4MB page directory only Bottom 22 bits of virtual address serve as offset Kubiatowicz CS162 UCB Fall 2008 Lec 13 5 How is the translation accomplished CPU Virtual Addresses MMU Physical Addresses 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 13 08 Kubiatowicz CS162 UCB Fall 2008 Lec 13 6 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 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 Kubiatowicz CS162 UCB Fall 2008 Invalid PTE can imply different things Dual Mode Operation Can Application Modify its own translation tables What exactly happens inside MMU One possibility Hardware Tree Traversal 10 13 08 Examples of how to use a PTE How do we use the PTE Lec 13 7 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 13 08 Kubiatowicz CS162 UCB Fall 2008 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 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 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 13 08 OS user kernel user mode getting into cell User OS user kernel mode getting out of cell Kubiatowicz CS162 UCB Fall 2008 Lec 13 9 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 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 13 08 Kubiatowicz CS162 UCB Fall 2008 Lec 13 10 System Call Continued What are some system calls I O open close read write lseek Files delete mkdir rmdir truncate chown chgrp Process fork exit wait like join Network
View Full Document
Unlocking...