Page 1 CS162 Operating Systems and Systems Programming Lecture 13 Address Translation (con’t) Caches and TLBs March 2, 2010 Ion Stoica http://inst.eecs.berkeley.edu/~cs162 Lec 13.2 3/2/10 CS162 ©UCB Spring 2010 Review: Single-Level Translation • Advantages – Low translation overhead – Simplicity • Disadvantages – Large page tables » E.g., 32b address space, 4KB pages up to 210 = 1mil page entries for each process – Expensive to share memory » E.g., 4KB pages, want to share 100MB need to update 25,000 entries in page table Physical Address Offset Offset Virtual Page # Virtual Address: Access Error > PageTableSize PageTablePtr page #0 page #2 page #3 page #4 page #5 V,R page #1 V,R V,R,W V,R,W N V,R,W page #1 V,R Check Perm Access Error Physical Page # Lec 13.3 3/2/10 CS162 ©UCB Spring 2010 • 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): • What must be saved/restored on context switch? – Contents of top-level segment registers (for this example) – Pointer to top-level table (page table) Review: Multi-level Translation page #0 page #1 page #3 page #4 page #5 V,R V,R page #2 V,R,W V,R,W N V,R,W Offset Physical Address Virtual Address: Offset Virtual Page # Virtual Seg # Base0 Limit0 V Base1 Limit1 V Base2 Limit2 V Base3 Limit3 N Base4 Limit4 V Base5 Limit5 N Base6 Limit6 N Base7 Limit7 V Base2 Limit2 V Access Error > page #2 V,R,W Physical Page # Check Perm Access Error Lec 13.4 3/2/10 CS162 ©UCB Spring 2010 Physical Address: Offset Physical Page # 4KB Review: Two-level page table 10 bits 10 bits 12 bits Virtual Address: Offset Virtual P2 index Virtual P1 index 4 bytes PageTablePtr • 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) 4 bytesPage 2 Lec 13.5 3/2/10 CS162 ©UCB Spring 2010 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 Gagne Lec 13.6 3/2/10 CS162 ©UCB Spring 2010 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” P: Present (same as “valid” bit in other architectures) W: Writeable U: User accessible PWT: Page write transparent: external cache write-through 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 Page Frame Number (Physical Page Number) Free (OS) 0 L D A PCD PWT U W P 0 1 2 3 4 5 6 7 8 11-9 31-12 Lec 13.7 3/2/10 CS162 ©UCB Spring 2010 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 • 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 Lec 13.8 3/2/10 CS162 ©UCB Spring 2010 How is the translation accomplished? • 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! CPU MMU Virtual Addresses Physical AddressesPage 3 Lec 13.9 3/2/10 CS162 ©UCB Spring 2010 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) – Typical OS kernels on Intel processors only use PL0 (“user”) and PL3 (“kernel”) Lec 13.10 3/2/10 CS162 ©UCB Spring 2010 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 affect 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 • A couple of issues – How to share CPU between kernel and user programs? » Kinda
View Full Document
Unlocking...