6 3ULQFLSOHV RI 2SHUDWLQJ 6 VWHPV DOO Lecture 10 Paging Geoffrey M Voelker HFWXUH 2YHUYLHZ 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 November 1 2000 CSE 120 Lecture 10 Paging 2 1 0DQDJLQJ 3DJH 7DEOHV 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 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 1 2000 CSE 120 Lecture 10 Paging 3 7ZR HYHO 3DJH 7DEOHV Two level page tables Virtual addresses VAs have three parts 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 Master page number secondary page number and offset 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 20 bits November 1 2000 CSE 120 Lecture 10 Paging 4 2 7ZR HYHO 3DJH 7DEOHV 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 1 2000 CSE 120 Lecture 10 Paging 5 GGUHVVLQJ 3DJH 7DEOHV 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 November 1 2000 CSE 120 Lecture 10 Paging 6 3 IILFLHQW 7UDQVODWLRQV 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 November 1 2000 CSE 120 Lecture 10 Paging 7 7 V 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 November 1 2000 CSE 120 Lecture 10 Paging 8 4 0DQDJLQJ 7 V 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 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 1 2000 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 0DQDJLQJ 7 V 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 November 1 2000 CSE 120 Lecture 10 Paging 10 5 3DJHG 9LUWXDO 0HPRU 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 The movement of pages between memory and disk is done by the OS and is transparent to the application November 1 2000 CSE 120 Lecture 10 Paging 11 3DJH DXOWV 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 OS usually keeps a pool of free pages around so that allocations do not always cause evictions November 1 2000 CSE 120 Lecture 10 Paging 12 6 GGUHVV 7UDQVODWLRQ 5HGX 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 TLBs Demand paging Now let s put it together bottom to top November 1 2000 CSE 120 Lecture 10 Paging 13 7KH RPPRQ DVH 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 PTE for the mapping for this
View Full Document
Unlocking...