Virtual Memory CS740 October 13 1998 Topics page tables TLBs Alpha 21X64 memory system Levels in a Typical Memory Hierarchy cache CPU CPU regs regs register reference size speed Mbyte block size 200 B 3 ns 4B 4B C a c h e 8B cache reference 32 KB 4MB 6 ns 256 MB 8B virtual memory Memory Memory memory reference 128 MB 100 ns 2 MB 4 KB 4 KB disk disk disk memory reference 20 GB 10 ms 0 10 MB larger slower cheaper 2 CS 740 F 98 Virtual Memory Main memory acts as a cache for the secondary storage disk Increases Program Accessible Memory address space of each job larger than physical memory sum of the memory of many jobs greater than physical memory 3 CS 740 F 98 Address Spaces Virtual and physical address spaces divided into equal sized blocks Pages both virtual and physical Virtual address space typically larger than physical Each process has separate virtual address space Virtual addresses VA 0 Process 1 Physical addresses PA address translation 0 VP 1 VP 2 PP2 2n 1 PP7 Process 2 0 2n 1 4 VP 1 VP 2 Read only library code PP10 2m 1 CS 740 F 98 Other Motivations Simplifies memory management main reason today Can have multiple processes resident in physical memory Their program addresses mapped dynamically Address 0x100 for process P1 doesn t collide with address 0x100 for process P2 Allocate more memory to process as its needs grow Provides Protection One process can t interfere with another Since operate in different address spaces Process cannot access privileged information Different sections of address space have different access permissions 5 CS 740 F 98 Contrast Macintosh Memory Model Does not Use Traditional Virtual Memory All objects accessed through Handles Indirect reference through table Objects can be relocated by updating pointer in table P1 Handles Shared Address Space Process P1 P2 Handles Process P1 6 CS 740 F 98 VM as part of the memory hierarchy Access word w in virtual page p hit Access word v in virtual page q miss or page fault v cache block w cache block p memory p page frames p q page q disk 7 p q pages p q p CS 740 F 98 q VM address V 0 1 n translation 1 virtual address space M 0 1 m 1 physical address space n m MAP V M U address mapping function MAP a a if data at virtual address a is present at physical address a and a in M if data at virtual address a is not present in M a missing item fault Name Space V fault handler Processor a Addr Trans Mechanism a physical address 8 Main Memory Secondary memory OS performs this transfer CS 740 F 98 VM address translation virtual address 31 12 11 virtual page number 0 page offset address translation 29 12 11 physical page number 0 page offset physical address Notice that the page offset bits don t change as a result of translation 9 CS 740 F 98 Address translation with a page table virtual address 31 page table base register 12 11 virtual page number valid access 0 page offset physical page number VPN acts as table index if valid 0 then page is not in memory and page fault exception 29 12 11 physical page number 0 page offset physical address 10 CS 740 F 98 Page Tables 11 CS 740 F 98 Page Table Operation Translation separate set of page table s per process VPN forms index into page table Computing Physical Address Page Table Entry PTE provides information about page Valid bit 1 page in memory Use physical page number PPN to construct address Valid bit 0 page in secondary memory Page fault Must load into main memory before continuing Checking Protection Access rights field indicate allowable access E g read only read write execute only Typically support multiple protection modes e g kernel vs user Protection violation fault if don t have necessary permission 12 CS 740 F 98 VM design issues Everything driven by enormous cost of misses hundreds of thousands to millions of clocks vs units or tens of clocks for cache misses disks are high latency Typically 10 ms access time Moderate disk to memory bandwidth 10 MBytes sec transfer rate Large block sizes Typically 4KB 16 KB amortize high access time reduce miss rate by exploiting spatial locality Perform Context Switch While Waiting Memory filled from disk by direct memory access Meanwhile processor can be executing other processes 13 CS 740 F 98 VM design issues cont Fully associative page placement eliminates conflict misses every miss is a killer so worth the lower hit time Use smart replacement algorithms handle misses in software miss penalty is so high anyway no reason to handle in hardware small improvements pay big dividends Write back only disk access too slow to afford write through write buffer 14 CS 740 F 98 Integrating VM and cache VA CPU Translation data miss PA Cache Main Memory hit Most Caches Physically Addressed Accessed by physical addresses Allows multiple processes to have blocks in cache at same time Allows multiple processes to share pages Cache doesn t need to be concerned with protection issues Access rights checked as part of address translation Perform Address Translation Before Cache Lookup But this could involve a memory access itself Of course page table entries can also become cached 15 CS 740 F 98 Speeding up Translation with a TLB Translation lookaside buffer TLB small usually fully associative cache maps virtual page numbers to physical page numbers Contains complete page table entries for small number of pages VA CPU TLB Lookup miss hit PA miss Cache Main Memory hit Translation data 16 CS 740 F 98 Address translation with a TLB 31 12 11 0 page offset virtual page number process ID valid dirty valid valid valid valid tag virtual address physical page number TLB hit physical address tag index valid tag cache hit 17 byte offset data data CS 740 F 98 Alpha AXP 21064 TLB page size 8KB hit time 1 clock miss penalty 20 clocks TLB size ITLB 8 PTEs DTLB 32 PTEs replacement random but not last used placement Fully assoc 18 CS 740 F 98 TLB Process Interactions TLB Translates Virtual Addresses But virtual address space changes each time have context switch Could flush TLB Every time perform context switch Refill for new process by series of TLB misses 100 clock cycles each Could Include Process ID Tag with TLB Entry Identifies which address space being accessed OK even when sharing physical pages 19 CS 740 F 98 Virtually Indexed Cache VA CPU TLB Lookup Index Data PA Tag Hit Cache Cache Index Determined from Virtual Address Can begin cache and TLB index at same time Cache Physically Addressed Cache tag indicates physical address Compare with TLB result
View Full Document
Unlocking...