CSE 120 Principles of Operating Systems Fall 2004 Lecture 10 Paging Geoffrey M Voelker Lecture Overview Today we ll cover more paging mechanisms z Optimizations z z 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 2 1 Managing Page Tables z Last lecture we computed the size of the page table for a 32 bit address space w 4K pages to be 4MB z How can we reduce this overhead z 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 z 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 3 Two Level Page Tables z Two level page tables Virtual addresses VAs have three parts Master page number secondary page number and offset z 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 4 2 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 5 Addressing Page Tables Where do we store page tables which address space z Physical memory z Virtual memory OS virtual address space z 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 6 3 Efficient Translations z Our original page table scheme already doubled the cost of doing memory lookups z Now two level page tables triple the cost z 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 7 TLBs z Translation Lookaside Buffers z TLBs implemented in hardware z 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 8 4 Managing TLBs z Address translations for most instructions are handled using the TLB z 99 of translations but there are misses TLB miss Who places translations into the TLB loads the TLB Hardware Memory Management Unit 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 November 4 2004 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 2004 Geoffrey M Voelker 9 Managing TLBs 2 z OS ensures that TLB and page tables are consistent z Reload TLB on a process context switch z 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 November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 10 5 Paged Virtual Memory z We ve mentioned before that pages can be moved between memory and disk z 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 The movement of pages between memory and disk is done by the OS and is transparent to the application November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 11 Page Faults z 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 z But where does it put it Have to evict something else OS usually keeps a pool of free pages around so that allocations do not always cause evictions November 4 2004 CSE 120 Lecture 10 Paging 2004 Geoffrey M Voelker 12 6 Address Translation Redux z z We started this topic with the high level problem of translating virtual addresses into physical address We ve covered all of the pieces z 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 November 4 2004
View Full Document
Unlocking...