CSE 120 Principles of Operating Systems Spring 2009 Lecture 10 Paging Geoffrey M Voelker Lecture Overview Today we ll cover more paging mechanisms Optimizations Managing page tables space Efficient translations TLBs time Demand paged virtual memory space Recap address translation Advanced Functionality Sharing memory Copy on Write Mapped files May 12 2009 CSE 120 Lecture 10 Paging 2 Managing Page Tables Last lecture we computed the size of the page table for a 32 bit address space w 4K pages to be 4MB How can we reduce this overhead Observation Only need to map the portion of the address space actually being used tiny fraction of entire addr space How do we only map what is being used This is far far too much overhead for each process Can dynamically extend page table Does not work if addr space is sparce internal fragmentation Use another level of indirection two level page tables May 12 2009 CSE 120 Lecture 10 Paging 3 Two Level Page Tables Two level page tables Virtual addresses VAs have three parts Master page number secondary page number and offset Master page table maps VAs to secondary page table Secondary page table maps page number to physical page Offset indicates where in physical page address is located Example 4K pages 4 bytes PTE How many bits in offset 4K 12 bits Want master page table in one page 4K 4 bytes 1K entries Hence 1K secondary page tables How many bits Master 1K 10 offset 12 inner 32 10 12 10 bits May 12 2009 CSE 120 Lecture 10 Paging 4 Two Level Page Tables Physical Memory Virtual Address Master page number Secondary Offset Physical Address Page table Master Page Table Page frame Offset Page frame Secondary Page Table May 12 2009 CSE 120 Lecture 10 Paging 5 Addressing Page Tables Where do we store page tables which address space Physical memory Virtual memory OS virtual address space Easy to address no translation required But allocated page tables consume memory for lifetime of VAS Cold unused page table pages can be paged out to disk But addressing page tables requires translation How do we stop recursion Do not page the outer page table called wiring If we re going to page the page tables might as well page the entire OS address space too Need to wire special code and data fault interrupt handlers May 12 2009 CSE 120 Lecture 10 Paging 6 Efficient Translations Our original page table scheme already doubled the cost of doing memory lookups Now two level page tables triple the cost One lookup into the page table another to fetch the data Two lookups into the page tables a third to fetch the data And this assumes the page table is in memory How can we use paging but also have lookups cost about the same as fetching from memory Cache translations in hardware Translation Lookaside Buffer TLB TLB managed by Memory Management Unit MMU May 12 2009 CSE 120 Lecture 10 Paging 7 TLBs Translation Lookaside Buffers TLBs implemented in hardware Translate virtual page s into PTEs not physical addrs Can be done in a single machine cycle Fully associative cache all entries looked up in parallel Cache tags are virtual page numbers Cache values are PTEs entries from page tables With PTE offset can directly calculate physical address TLBs exploit locality Processes only use a handful of pages at a time 16 48 entries pages 64 192K Only need those pages to be mapped Hit rates are therefore very important May 12 2009 CSE 120 Lecture 10 Paging 8 Managing TLBs Address translations for most instructions are handled using the TLB 99 of translations but there are misses TLB miss Who places translations into the TLB loads the TLB Hardware Memory Management Unit x86 Knows where page tables are in main memory OS maintains tables HW accesses them directly Tables have to be in HW defined format inflexible Software loaded TLB OS MIPS Alpha Sparc PowerPC May 12 2009 TLB faults to the OS OS finds appropriate PTE loads it in TLB Must be fast but still 20 200 cycles CPU ISA has instructions for manipulating TLB Tables can be in any format convenient for OS flexible CSE 120 Lecture 10 Paging 9 Managing TLBs 2 OS ensures that TLB and page tables are consistent Reload TLB on a process context switch When it changes the protection bits of a PTE it needs to invalidate the PTE if it is in the TLB Invalidate all entries Why What is one way to fix it When the TLB misses and a new PTE has to be loaded a cached PTE must be evicted Choosing PTE to evict is called the TLB replacement policy Implemented in hardware often simple e g Last Not Used May 12 2009 CSE 120 Lecture 10 Paging 10 Paged Virtual Memory We ve mentioned before that pages can be moved between memory and disk This process is called demand paging OS uses main memory as a page cache of all the data allocated by processes in the system Initially pages are allocated from memory When memory fills up allocating a page in memory requires some other page to be evicted from memory Why physical memory pages are called frames Evicted pages go to disk where the swap file backing store The movement of pages between memory and disk is done by the OS and is transparent to the application May 12 2009 CSE 120 Lecture 10 Paging 11 Page Faults What happens when a process accesses a page that has been evicted 1 When it evicts a page the OS sets the PTE as invalid and stores the location of the page in the swap file in the PTE 2 When a process accesses the page the invalid PTE will cause a trap page fault 3 The trap will run the OS page fault handler 4 Handler uses the invalid PTE to locate page in swap file 5 Reads page into a physical frame updates PTE to point to it 6 Restarts process But where does it put it Have to evict something else May 12 2009 OS usually keeps a pool of free pages around so that allocations do not always cause evictions CSE 120 Lecture 10 Paging 12 Address Translation Redux We started this topic with the high level problem of translating virtual addresses into physical addresses We ve covered all of the pieces Virtual and physical addresses Virtual pages and physical page frames Page tables and page table entries PTEs protection TLBs Demand paging Now let s put it together bottom to top May 12 2009 CSE 120 Lecture 10 Paging 13 The Common Case Situation Process is executing on the CPU and it issues a read to an address What kind of address is it Virtual or physical The read goes to the TLB in the MMU 1 TLB does a lookup using the page number of the address 2 Common case is that the page number matches returning a page table entry
View Full Document
Unlocking...