HW 3 due 11 10 Lecture 11 Paging CSE 120 Principles of Operating Systems Alex C Snoeren 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 2 CSE 120 Lecture 11 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 3 CSE 120 Lecture 11 Two Level Page Tables Last time virtual addresses VAs had two parts Now VAs have three parts We d like a manageable master page size Secondary table maps page number to physical page Master page number secondary page number and offset Master page table maps VAs to secondary page table Page number which mapped to frame and an offset Determines which physical frame the address resides in Offset indicates which byte in physical page Final system page frame size is still the same so offset length stays the same 4 CSE 120 Lecture 11 Two Level Page Tables Master page number Secondary Offset Virtual Address Page table Page frame Offset Physical Address Master Page Table Page frame Secondary Page Table 5 Physical Memory CSE 120 Lecture 11 An Example w 4 byte PTEs 10 bits 10 bits Master page number Secondary 12 bits Offset Virtual Address 12 bits 1K entries Page table Page frame Offset Physical Address Master Page Table 1K entries Page frame Secondary Page Table Physical Memory 4K pages 12 bit offset 1 master page 4K 4 1K entries 10bits Secondary page table size 32 12 10 10 bits 1K entries 4 4K 6 CSE 120 Lecture 11 Where Do Page Tables Live 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 7 CSE 120 Lecture 11 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 8 CSE 120 Lecture 11 TLBs Translation Lookaside Buffers TLBs implemented in hardware Translate virtual page s into PTEs not physical addresses 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 9 CSE 120 Lecture 11 Loading TLBs Most address translations are handled using the TLB 99 of translations but there are misses TLB miss Who places translations into the TLB loads the TLB Software loaded TLB OS 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 Hardware Memory Management Unit Must know where page tables are in main memory OS maintains tables HW accesses them directly Tables have to be in HW defined format inflexible 10 CSE 120 Lecture 11 Managing TLBs 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 11 CSE 120 Lecture 11 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 partition The movement of pages between memory and disk is done by the OS and is transparent to the application 12 CSE 120 Lecture 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 Has to evict something else OS usually keeps a pool of free pages around so that allocations do not always cause evictions 13 CSE 120 Lecture 11 Complete Address Translation We started this topic with the high level problem of translating virtual addresses into physical address 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 Translation lookaside buffers TLBs Demand paging Now let s put it together bottom to top 14 CSE 120 Lecture 11 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
View Full Document
Unlocking...