Carnegie Mellon Introduction to Computer Systems 15 213 fall 2009 16th Lecture Oct 21st Instructors Majd Sakr and Khaled Harras 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 Carnegie Mellon Virtual Memory Previous Lectures Programs refer to virtual memory addresses 00 0 movl ecx eax Conceptually very large array of bytes Each byte has its own address Actually implemented with hierarchy of different memory types System provides address space private to particular process Allocation Compiler and run time system Where different program objects should be stored All allocation within single virtual address space But why virtual memory Why not physical memory FF F Carnegie Mellon Problem 1 How Does Everything Fit 64 bit addresses 16 Exabyte Physical main memory Few Gigabytes And there are many processes Carnegie Mellon Problem 2 Memory Management Physical main memory Process 1 Process 2 Process 3 Process n x stack heap text data What goes where Carnegie Mellon Problem 3 How To Protect Physical main memory Process i Process j Problem 4 How To Share Physical main memory Process i Process j Carnegie Mellon Solution Level Of Indirection 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 Address Spaces Linear address space Ordered set of contiguous non negative integer addresses 0 1 2 3 Virtual address space Set of N 2n virtual addresses 0 1 2 3 N 1 Physical address space Set of M 2m physical addresses 0 1 2 3 M 1 Clean distinction between data bytes and their attributes addresses Each object can now have multiple addresses Every byte in main memory one physical address one or more virtual addresses Carnegie Mellon A System Using Physical Addressing CPU Physical address PA Main memory 0 1 2 3 4 5 6 7 8 M 1 Data word Used in simple systems like embedded microcontrollers in devices like cars elevators and digital picture frames 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 Why Virtual Memory VM Efficient use of limited main memory RAM Use RAM as a cache for the parts of a virtual address space some non cached parts stored on disk some unallocated non cached parts stored nowhere Keep only active areas of virtual address space in memory transfer data back and forth as needed Simplifies memory management for programmers Each process gets the same full private linear address space Isolates address spaces One process can t interfere with another s memory because they operate in different address spaces User process cannot access privileged information different sections of address spaces have different permissions 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 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 Disk VP 0 Unallocated VP 1 Cached 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 CP U Reg L1 D cache 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 Page table base register PTBR Page table address for process Virtual address 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
View Full Document
Unlocking...