CS162Operating Systems andSystems ProgrammingLecture 13Address Translation (con’t)Caches and TLBsOctober 13, 2008Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 13.210/13/08Kubiatowicz CS162 ©UCB Fall 2008• 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 Translationpage #0page #1page #3page #4page #5V,RV,Rpage #2V,R,WV,R,WNV,R,WOffsetPhysical AddressVirtual Address:OffsetVirtualPage #VirtualSeg #Base0 Limit0 VBase1 Limit1 VBase2 Limit2 VBase3 Limit3 NBase4 Limit4 VBase5 Limit5 NBase6 Limit6 NBase7 Limit7 VBase2 Limit2 VAccessError>page #2V,R,WPhysicalPage #Check PermAccessErrorLec 13.310/13/08Kubiatowicz CS162 ©UCB Fall 2008PhysicalAddress: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/13/08Kubiatowicz CS162 ©UCB Fall 2008Goals 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/13/08Kubiatowicz CS162 ©UCB Fall 2008What 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=1⇒4MB 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/13/08Kubiatowicz CS162 ©UCB Fall 2008Examples 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 copyof 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/13/08Kubiatowicz CS162 ©UCB Fall 2008How 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/13/08Kubiatowicz CS162 ©UCB Fall 2008Dual-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/13/08Kubiatowicz CS162 ©UCB Fall 2008For 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?» OS → user (kernel → user mode): getting into cell» User→ OS (user → kernel mode): getting out of cellLec 13.1010/13/08Kubiatowicz CS162 ©UCB Fall 2008How 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
View Full Document
Unlocking...