Carnegie Mellon Introduction to Computer Systems 15 213 fall 2009 17th Lecture Oct 26th Instructors Majd Sakr and Khaled Harras Carnegie Mellon Last Time Virtual Memory Virtual memory Process 1 Physical memory mapping Virtual memory Process n Each process gets its own private memory space Solves the previous problems Carnegie Mellon A System Using Virtual Addressing CPU Chip CPU Virtual address VA MMU Physical address PA Main memory 0 1 2 3 4 5 6 7 8 M 1 Data word Used in all modern desktops laptops workstations One of the great ideas in computer science MMU checks the cache Carnegie Mellon Last Time Address Translation Virtual address Page table base register PTBR Page table address for process Virtual page number VPN Virtual page offset VPO Page table Valid Physical page number PPN Valid bit 0 page not in memory page fault Physical page number PPN Physical address Physical page offset PPO Carnegie Mellon Today Virtual memory VM Address translation Allocation Multi level page tables Linux VM system Carnegie Mellon Address Translation Page Hit 2 PTEA CPU Chip CPU 1 VA PTE MMU 3 PA 4 Data 5 1 Processor sends virtual address to MMU 2 3 MMU fetches PTE from page table in memory 4 MMU sends physical address to cache memory 5 Cache memory sends data word to processor Cache Memory Carnegie Mellon Address Translation Page Fault Exception Page fault handler 4 2 PTEA CPU Chip CPU 1 VA 7 MMU PTE 3 Victim page 5 Cache Memory Disk New page 6 1 Processor sends virtual address to MMU 2 3 MMU fetches PTE from page table in memory 4 Valid bit is zero so MMU triggers page fault exception 5 Handler identifies victim and if dirty pages it out to disk 6 Handler pages in new page and updates PTE in memory 7 Handler returns to original process restarting faulting instruction Carnegie Mellon Speeding up Translation with a TLB Page table entries PTEs are cached in L1 like any other memory word PTEs may be evicted by other data references PTE hit still requires a 1 cycle delay Solution Translation Lookaside Buffer TLB Small hardware cache in MMU Maps virtual page numbers to physical page numbers Contains complete page table entries for small number of pages Carnegie Mellon TLB Hit CPU Chip CPU TLB 2 PTE VPN 3 1 VA MMU Data 5 A TLB hit eliminates a memory access PA 4 Cache Memory Carnegie Mellon TLB Miss CPU Chip TLB 2 4 PTE VPN CPU 1 VA MMU 3 PTEA PA Cache Memory 5 Data 6 A TLB miss incurs an add l memory access the PTE Fortunately TLB misses are rare Carnegie Mellon Simple Memory System Example Addressing 14 bit virtual addresses 12 bit physical address Page size 64 bytes 13 12 11 10 9 8 7 6 5 4 3 2 1 VPN VPO Virtual Page Number Virtual Page Offset 11 10 9 8 7 6 5 4 3 2 1 PPN PPO Physical Page Number Physical Page Offset 0 0 Carnegie Mellon Simple Memory System Page Table Only show first 16 entries out of 256 VPN PPN Valid VPN PPN Valid 00 28 1 08 13 1 01 0 09 17 1 02 33 1 0A 09 1 03 02 1 0B 0 04 0 0C 0 05 16 1 0D 2D 1 06 0 0E 11 1 07 0 0F 0D 1 Carnegie Mellon Simple Memory System TLB 16 entries 4 way associative TLBT 13 12 11 10 TLBI 9 8 7 6 5 4 3 VPN 2 1 0 VPO Set Tag PPN Valid Tag PPN Valid Tag PPN Valid Tag PPN Valid 0 03 0 09 0D 1 00 0 07 02 1 1 03 2D 1 02 0 04 0 0A 0 2 02 0 08 0 06 0 03 0 3 07 0 03 0D 1 0A 34 1 02 0 Carnegie Mellon Simple Memory System Cache 16 lines 4 byte block size Physically addressed Direct mapped CT 11 10 9 CI 8 7 6 5 4 CO 3 PPN 2 1 0 PPO Idx Tag Valid B0 B1 B2 B3 Idx Tag Valid B0 B1 B2 B3 0 19 1 99 11 23 11 8 24 1 3A 00 51 89 1 15 0 9 2D 0 2 1B 1 00 02 04 08 A 2D 1 93 15 DA 3B 3 36 0 B 0B 0 4 32 1 43 6D 8F 09 C 12 0 5 0D 1 36 72 F0 1D D 16 1 04 96 34 15 6 31 0 E 13 1 83 77 1B D3 7 16 1 11 C2 DF 03 F 14 0 Carnegie Mellon Address Translation Example 1 Virtual Address 0x03D4 TLBT TLBI 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 VPN 0x0F VPN VPO 3 TLBI 0x03 TLBT Physical Address Y TLB Hit Page Fault 0x0D PPN CI CT CO 11 10 9 8 7 6 5 4 3 2 1 0 0 0 1 1 0 1 0 1 0 1 0 0 PPN 0 N 0x5 0x0D PPO Y 0x36 Carnegie Mellon Address Translation Example 2 Virtual Address 0x0B8F TLBT TLBI 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 VPN 0x2E VPN VPO 2 TLBI 0x0B TLBT Physical Address 11 N TLB Hit Y Page Fault 9 PPN PPN CI CT 10 TBD 8 7 6 5 4 CO 3 PPO 2 1 0 Carnegie Mellon Address Translation Example 3 Virtual Address 0x0020 TLBT TLBI 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 VPN 0x00 VPN VPO 0 TLBI 0x00 TLBT Physical Address N TLB Hit Page Fault 0x28 PPN CI CT CO 11 10 9 8 7 6 5 4 3 2 1 0 1 0 1 0 0 0 1 0 0 0 0 0 PPN 0 N 0x8 0x28 PPO N Mem Carnegie Mellon Summary Programmer s view of virtual memory Each process has its own private linear address space Cannot be corrupted by other processes System view of virtual memory Uses memory efficiently by caching virtual memory pages Efficient only because of locality Simplifies memory management and programming Simplifies protection by providing a convenient interpositioning point to check permissions Carnegie Mellon Today Virtual memory VM Address translation Allocation Multi level page tables Linux VM system Carnegie Mellon Allocating Virtual Pages Example Allocating VP5 Physical page number or Valid disk address PTE 0 0 null 1 1 1 0 0 0 PTE 7 1 null Physical memory DRAM VP 1 VP 2 VP 7 VP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 PP 0 PP 3 Carnegie Mellon Allocating Virtual Pages Example Allocating VP 5 Kernel allocates VP 5 on disk and points PTE 5 to it Physical …
View Full Document
Unlocking...