Carnegie Mellon Introduction to Computer Systems 15 213 18 243 spring 2009 17th Lecture Mar 19th Instructors Gregory Kesden and Markus P schel 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 Today Virtual memory VM Overview and motivation VM as tool for caching VM as tool for memory management VM as tool for memory protection Address translation Allocation multi level page tables Linux VM system Carnegie Mellon VM as a Tool for Caching Virtual memory array of N 2n contiguous bytes think of the array allocated part as being stored on disk Physical main memory DRAM cache for allocated virtual memory Blocks are called pages size 2p Virtual memory VP 0 Unallocated VP 1 Cached Disk VP 2n p 1 Uncached Unallocated Cached Uncached Cached Uncached Physical memory 0 0 Empty PP 0 PP 1 Empty Empty 2m 1 PP 2m p 1 2n 1 Virtual pages VP s stored on disk Physical pages PP s cached in DRAM Carnegie Mellon Memory Hierarchy Core 2 Duo Not drawn to scale L1 L2 cache 64 B blocks 4 MB 4 GB L2 unified cache Main Memory 500 GB L1 I cache 32 KB CPU L1 D cache Reg Throughput 16 B cycle Latency 3 cycles 8 B cycle 14 cycles 2 B cycle 100 cycles 1 B 30 cycles millions Miss penalty latency 30x Miss penalty latency 10 000x Disk Carnegie Mellon DRAM Cache Organization DRAM cache organization driven by the enormous miss penalty DRAM is about 10x slower than SRAM Disk is about 10 000x slower than DRAM For first byte faster for next byte Consequences Large page block size typically 4 8 KB sometimes 4 MB Fully associative Any VP can be placed in any PP Requires a large mapping function different from CPU caches Highly sophisticated expensive replacement algorithms Too complicated and open ended to be implemented in hardware Write back rather than write through Carnegie Mellon Address Translation Page Tables A page table is an array of page table entries PTEs that maps virtual pages to physical pages Here 8 VPs Per process kernel data structure in DRAM Physical page number or Valid disk address PTE 0 0 null 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 VP 2 VP 7 VP 4 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 Address Translation With a Page Table 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 Page Hit Page hit reference to VM word that is in physical memory Virtual address Physical page number or Valid disk address PTE 0 0 null 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 VP 2 VP 7 VP 4 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 Page Miss Page miss reference to VM word that is not in physical memory Virtual address Physical page number or Valid disk address PTE 0 0 null 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 VP 2 VP 7 VP 4 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 Handling Page Fault Page miss causes page fault an exception Virtual address Physical page number or Valid disk address PTE 0 0 null 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 VP 2 VP 7 VP 4 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 Handling Page Fault Page miss causes page fault an exception Page fault handler selects a victim to be evicted here VP 4 Virtual address Physical page number or Valid disk address PTE 0 0 null 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 VP 2 VP 7 VP 4 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 Handling Page Fault Page miss causes page fault an exception Page fault handler selects a victim to be evicted here VP 4 Virtual address 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 Handling Page Fault Page miss causes page fault an exception Page fault handler selects a victim to be evicted here VP 4 Offending instruction is restarted page hit Virtual address 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 Why does it work Locality Virtual memory works because of locality At any point in time programs tend to access a set of active virtual pages called the working set Programs with better temporal locality will have smaller working sets If working set size main memory size Good performance for one process after compulsory misses If SUM working set sizes main memory size Thrashing Performance meltdown where pages are swapped copied in and out continuously Carnegie Mellon Today Virtual memory VM Overview and motivation VM as tool for caching VM as tool for memory management VM as tool for memory protection Address translation Allocation multi level page tables Linux VM system Carnegie Mellon VM as a Tool for Memory Management Key idea each process has its own virtual address space It can view memory as a simple linear array Mapping function scatters addresses through physical memory Well chosen mappings simplify memory allocation and management Virtual Address Space for Process 1 0 VP 1 VP 2 Address translation 0 PP 2 Physical Address Space DRAM N 1 PP 6 Virtual Address Space for Process 2 0 PP 8 VP 1 VP 2 N 1 M …
View Full Document
Unlocking...