CS162 Operating Systems and Systems Programming Lecture 13 Address Translation (con’t) Caches and TLBsReview: Multi-level TranslationReview: Two-level page tableGoals for TodayWhat is in a PTE?Examples of how to use a PTEHow is the translation accomplished?Dual-Mode OperationFor Protection, Lock User-Programs in AsylumHow to get from KernelUserUserKernel (System Call)System Call ContinuedUserKernel (Exceptions: Traps and Interrupts)Additions to MIPS ISA to support Exceptions?Closing thought: Protection without HardwareAdministriviaCaching ConceptWhy Bother with Caching?Another Major Reason to Deal with CachingWhy Does Caching Help? Locality!Memory Hierarchy of a Modern Computer SystemA Summary on Sources of Cache MissesHow is a Block found in a Cache?Review: Direct Mapped CacheReview: Set Associative CacheReview: Fully Associative CacheWhere does a Block Get Placed in a Cache?Review: Which block should be replaced on a miss?Review: What happens on a write?Caching Applied to Address TranslationWhat Actually Happens on a TLB Miss?What happens on a Context Switch?What TLB organization makes sense?TLB organization: include protectionExample: R3000 pipeline includes TLB “stages”Reducing translation time furtherOverlapping TLB & Cache AccessSummary #1/2Summary #2/2: Translation Caching (TLB)CS162Operating Systems andSystems ProgrammingLecture 13Address Translation (con’t)Caches and TLBsOctober 12, 2009Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 13.210/12/09 Kubiatowicz CS162 ©UCB Fall 2009•What about a tree of tables?–Lowest level page tablememory 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 Translationpage #0page #1page #3page #4page #5V,RV,Rpage #2V,R,WV,R,WNV,R,WOffsetPhysical AddressVirtual Address:OffsetVirtualPage #VirtualSeg #Base0Limit0 VBase1Limit1 VBase2Limit2 VBase3Limit3 NBase4Limit4 VBase5Limit5 NBase6Limit6 NBase7Limit7 VBase2Limit2 VAccessError>page #2V,R,WPhysicalPage #Check PermAccessErrorLec 13.310/12/09 Kubiatowicz CS162 ©UCB Fall 2009PhysicalAddress:OffsetPhysicalPage #4KBReview: Two-level page table10 bits 10 bits 12 bitsVirtual Address:OffsetVirtualP2 indexVirtualP1 index4 bytesPageTablePtr•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 bytesLec 13.410/12/09 Kubiatowicz CS162 ©UCB Fall 2009Goals for Today•Finish discussion of both Address Translation and Protection•Caching and TLBsNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and GagneLec 13.510/12/09 Kubiatowicz CS162 ©UCB Fall 2009What 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: WriteableU: User accessiblePWT: Page write transparent: external cache write-throughPCD: Page cache disabled (page cannot be cached)A: Accessed: page has been accessed recentlyD: Dirty (PTE only): page has been modified recentlyL: L=14MB page (directory only).Bottom 22 bits of virtual address serve as offsetPage Frame Number(Physical Page Number)Free(OS)0 L D APCDPWTU W P01234567811-931-12Lec 13.610/12/09 Kubiatowicz CS162 ©UCB Fall 2009Examples 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 backgroundLec 13.710/12/09 Kubiatowicz CS162 ©UCB Fall 2009How 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!CPUMMUVirtualAddressesPhysicalAddressesLec 13.810/12/09 Kubiatowicz CS162 ©UCB Fall 2009Dual-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”)Lec 13.910/12/09 Kubiatowicz CS162 ©UCB Fall 2009For Protection, Lock User-Programs in Asylum•Idea: Lock user programs in padded cell with no exit or sharp objects–Cannot change mode to
View Full Document
Unlocking...