Review CSE120 Principles of Operating Systems Fixed and variable size partition Prof Yuanyuan YY Zhou Lecture 10 paging Nov 2nd 2010 Paging Today s Lecture Segmentation Hybrid paging segmentation Segmentation table 11 1 2010 CSE 120 Lecture 10 Paging Page Mapping Hardware Today we ll cover more paging mechanisms Optimizations Page size is a power of 2 Virtual page number physical page frame How to calculate VPN from virtual address How to get physical address 2 Simple to implement base and limit registers Internal vs external fragmentation Best worst fast fit Bitmap vs link list implementation of free memory regions Page Table 0 P 1 0 1 P F 1 0 1 Managing page tables space Efficient translations TLBs time Demand paged virtual memory space Recap address translation Virtual Address P D P D Virtual Memory P Contents P D Physical Memory F D F Physical Address F D Contents F D 3 11 1 2010 CSE 120 Lecture 10 Paging 4 D 11 1 2010 D CSE 120 Lecture 10 Paging 1 Paging Issues Page Mapping Hardware Page Table 0 4 1 0 1 4 5 1 0 1 Virtual Memory Virtual Address 004006 004 006 Contents 4006 004 006 Page size 0x1000 Number of Possible Virtual Pages 0x1000 Number of Page Frames 8 11 1 2010 005 Contents 5006 006 CSE 120 Lecture 10 Paging 6 Managing Page Tables The page table for a 32 bit address space w 4K pages to be 4MB How can we reduce this overhead 7 11 1 2010 CSE 120 Lecture 10 Paging Discussion How to reduce page table size if the virtual pages are sparse This is far too much overhead for each process 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 220 page entries take 222 bytes 4MB 006 Physical Address F D 5 usually 512 1k 2k 4k or 8k E g 32 bit VM address may have 220 1MB pages with 4k 212 bytes per page Page table Physical Memory 005 Page size is 2n Can dynamically extend page table Does not work if addr space is sparce internal fragmentation why So now what 11 1 2010 CSE 120 Lecture 10 Paging 8 11 1 2010 CSE 120 Lecture 10 Paging 2 Two Level Page Tables Two level page tables Physical Memory Virtual addresses VAs have three parts Two Level Page Tables 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 Virtual Address Master page number 9 Physical Address 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 1024 secondary page tables How many bits Master 1K 10 offset 12 secondary 32 10 12 10 bits 11 1 2010 CSE 120 Lecture 10 Paging Master Page Table 10 CSE 120 Lecture 10 Paging Hints Easy to address no translation required But allocated page tables consume memory Programs only know virtual addresses Each virtual address must be translated So each program memory access requires several actual memory accesses 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 master page table called wiring or pinning If we re going to page the page tables might as well page the entire OS address space too 11 Page frame 11 1 2010 Virtual memory OS virtual address space Offset So what is the problem with twolevel page table Where do we store page tables which address space Physical memory Page frame Secondary Page Table Addressing Page Tables Offset Page table Example Secondary Need to wire special code and data fault interrupt handlers 11 1 2010 CSE 120 Lecture 10 Paging 12 11 1 2010 CSE 120 Lecture 10 Paging 3 Translation Look aside Buffer TLB Efficient Translations Our original page table scheme already doubled the cost of doing memory lookups VPage 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 offset One lookup into the page table another to fetch the data Now two level page tables triple the cost Virtual address VPage PPage VPage PPage VPage PPage Miss Real page table TLB Cache translations in hardware Translation Lookaside Buffer TLB TLB managed by Memory Management Unit MMU Hit PPage offset Physical address 13 11 1 2010 CSE 120 Lecture 10 Paging 14 11 1 2010 TLBs 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 If a virtual address is presented to MMU the hardware checks TLB by comparing all entries simultaneously in parallel If match is valid the page is taken from TLB without going through page table If match is not valid TLBs exploit locality Processes only use a handful of pages at a time 15 Translate virtual page s into PTEs not physical addrs Can be done in a single machine cycle TLBs implemented in hardware TLB Function Translation Lookaside Buffers 16 48 entries pages 64 192K Only need those pages to be mapped Hit rates are therefore very important 11 1 2010 CSE 120 Lecture 10 Paging CSE 120 Lecture 10 Paging 16 MMU detects miss and does an ordinary page table lookup It then evicts one page out of TLB and replaces it with the new entry so that next time that page is found in TLB 11 1 2010 CSE 120 Lecture 10 Paging 4 Page Mapping Hardware Page Mapping Example Virtual Memory Address P D P D Associative Look Up Page Table 0 P 1 0 1 P F 1 0 1 P F First F D Page Table 0 4 1 0 1 004 009 1 0 1 Physical Address F D 17 11 1 2010 CSE 120 Lecture 10 Paging 18 11 1 2010 Address translations for most instructions are handled using the TLB Who places translations into the TLB loads the TLB 99 of translations but there are misses TLB miss Hardware Memory Management Unit x86 Table organized by LRU 11 1 2010 CSE 120 Lecture 10 Paging 20 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 Physical Address F D 19 CSE 120 Lecture 10 Paging 00a Table organized by LRU 006 Managing TLBs Virtual Memory Address P D 004 00a Associative Look Up 1 12 4 9 19 3 First 3 7 009 009 Physical Address F D Page Mapping Example next reference Page Table 0 4 1 0 1 004 009 1 0 1 Virtual Memory Address P D 004 006 Associative …
View Full Document