Review Single Level Translation Virtual Virtual Address Page CS162 Operating Systems and Systems Programming Lecture 13 PageTablePtr PageTableSize Access Error Advantages Address Translation con t Caches and TLBs 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 Physical Page Check Perm Low translation overhead Simplicity Large page tables E g 32b address space 4KB pages up to 210 1mil page entries for each process Expensive to share memory 3 2 10 E g 4KB pages want to share 100MB need to update 25 000 entries in page table CS162 UCB Spring 2010 10 bits Lowest level page table memory still allocated with bitmap Higher levels often segmented 10 bits Virtual Virtual Virtual Address P1 index P2 index 12 bits Physical Physical Address Page Base0 Base1 Base2 Base3 Base4 Base5 Base6 Base7 Limit0 Limit1 Limit2 Limit3 Limit4 Limit5 Limit6 Limit7 V V V N V N N V 4KB 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 PageTablePtr Physical Page Offset Physical Address 4 bytes Tree of Page Tables Tables fixed size 1024 entries Check Perm On context switch save single PageTablePtr register Access Error Sometimes top level page tables called directories Intel Each entry called a surprise Page Table Entry PTE What must be saved restored on context switch Contents of top level segment registers for this example Pointer to top level table page table 3 2 10 CS162 UCB Spring 2010 Offset Offset Could have any number of levels Example top segment Virtual Page Lec 13 2 Review Two level page table Review Multi level Translation What about a tree of tables Virtual Seg Access Error Disadvantages March 2 2010 Ion Stoica http inst eecs berkeley edu cs162 Virtual Address Offset Physical Address 3 2 10 Lec 13 3 Page 1 4 bytes CS162 UCB Spring 2010 Lec 13 4 Goals for Today What is in a PTE What is in a Page Table Entry or PTE Finish discussion of both Address Translation and Protection Caching and TLBs 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 Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne 3 2 10 CS162 UCB Spring 2010 3 2 10 Lec 13 5 Examples of how to use a PTE How do we use the PTE CS162 UCB Spring 2010 CPU Region of address space is actually invalid or Page directory is just somewhere else than memory Validity checked first Lec 13 6 Virtual Addresses MMU Physical Addresses What exactly happens inside MMU One possibility Hardware Tree Traversal Usage Example Demand Paging Keep only active pages in memory Place others on disk and mark their PTEs invalid 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 Usage Example Copy on Write UNIX fork gives copy of parent address space to child Fault handler will decide what to do More on this next lecture Address spaces disconnected after child created How to do this cheaply Pros Relatively fast but still many memory accesses Cons Inflexible Complex hardware 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 Another possibility Software Usage Example Zero Fill On Demand Each traversal done in software Pros Very flexible Cons Every translation must invoke Fault 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 CS162 UCB Spring 2010 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 How is the translation accomplished Invalid PTE can imply different things 3 2 10 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 In fact need way to cache translations for either case 3 2 10 Lec 13 7 Page 2 CS162 UCB Spring 2010 Lec 13 8 Dual Mode Operation For Protection Lock User Programs in Asylum Idea Lock user programs in padded cell with no exit or sharp objects Can Application modify its own translation tables Cannot change mode to kernel mode User cannot modify page table mapping Limited access to memory cannot adversely affect other processes 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 Side effect Limited access to memory mapped I O operations I O that occurs by reading writing memory locations Kernel mode or supervisor or protected User mode Normal program mode Mode set with bits in special control register only accessible in kernel mode Limited access to interrupt controller A couple of issues Intel processor actually has four rings of protection 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 PL Priviledge Level from 0 3 PL0 has full access PL3 has least How do programs interact How does one switch between kernel and user modes Privilege Level set in code segment descriptor CS Typical OS kernels on Intel processors only use PL0 user and PL3 kernel 3 2 10 CS162 UCB Spring 2010 OS user kernel user mode getting into cell User OS user kernel mode getting out of cell 3 2 10 Lec 13 9 How to get from Kernel User CS162 UCB Spring 2010 Lec 13 10 User Kernel System Call Can t let inmate user get out of padded cell on own What does the kernel do to create a new user process Would defeat purpose of protection So how does the user program get back into kernel 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 System call Voluntary procedure call into kernel Hardware for controlled User Kernel
View Full Document
Unlocking...