Carnegie Mellon Virtual Memory Concepts 15 213 Introduction to Computer Systems 15th Lecture Oct 14 2010 Instructors Randy Bryant and Dave O Hallaron 1 Carnegie Mellon Today Address spaces VM as a tool for caching VM as a tool for memory management VM as a tool for memory protection Address translation 2 Carnegie Mellon A System Using Physical Addressing CPU Physical address PA 4 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 3 Carnegie Mellon A System Using Virtual Addressing CPU Chip CPU Virtual address VA 4100 MMU Physical address PA 4 Main memory 0 1 2 3 4 5 6 7 8 M 1 Data word Used in all modern servers desktops and laptops One of the great ideas in computer science 4 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 5 Carnegie Mellon Why Virtual Memory VM Uses main memory efficiently Use DRAM as a cache for the parts of a virtual address space Simplifies memory management Each process gets the same uniform linear address space Isolates address spaces One process can t interfere with another s memory User program cannot access privileged kernel information 6 Carnegie Mellon Today Address spaces VM as a tool for caching VM as a tool for memory management VM as a tool for memory protection Address translation 7 Carnegie Mellon VM as a Tool for Caching Virtual memory is an array of N contiguous bytes stored on disk The contents of the array on disk are cached in physical memory DRAM cache These cache blocks are called pages size is P 2p bytes Virtual memory 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 M 1 PP 2m p 1 N 1 Virtual pages VPs stored on disk Physical pages PPs cached in DRAM 8 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 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 9 Carnegie Mellon Page Tables A page table is an array of page table entries PTEs that maps virtual pages to physical pages 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 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 10 Carnegie Mellon Page Hit Page hit reference to VM word that is in physical memory DRAM cache hit 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 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 11 Carnegie Mellon Page Fault Page fault reference to VM word that is not in physical memory DRAM cache miss 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 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 12 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 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 13 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 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 14 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 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 15 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 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 16 Carnegie Mellon Locality to the Rescue Again 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 17 Carnegie Mellon Today Address spaces VM as a tool for caching VM as a tool for memory management VM as a tool for memory protection Address translation 18 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 …
View Full Document
Unlocking...