Carnegie Mellon Virtual Memory Concepts 15 213 Introduc0on 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 protec on Address transla on 2 Carnegie Mellon A System Using Physical Addressing CPU Main memory 0 1 Physical address 2 3 PA 4 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 con0guous non nega0ve 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 dis nc on between data bytes and their aVributes addresses Each object can now have mul ple addresses Every byte in main memory one physical address one or more virtual addresses 5 Carnegie Mellon Why Virtual Memory VM Uses main memory e ciently Use DRAM as a cache for the parts of a virtual address space Simpli es 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 informa0on 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 protec on Address transla on 7 Carnegie Mellon VM as a Tool for Caching Virtual memory is an array of N con guous 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 Physical memory 0 0 Uncached Unallocated Cached Uncached Cached n p VP 2 1 Uncached 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 Organiza on DRAM cache organiza on 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 some0mes 4 MB Fully associa0ve Any VP can be placed in any PP Requires a large mapping func0on di erent from CPU caches Highly sophis0cated 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 excep0on 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 excep0on Page fault handler selects a vic0m 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 excep0on Page fault handler selects a vic0m 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 excep0on Page fault handler selects a vic0m to be evicted here VP 4 O ending instruc0on 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 me programs tend to access a set of ac ve virtual pages called the working set Programs with beger temporal locality will have smaller working sets If working set size main memory size Good performance for one process aier compulsory misses If SUM working set sizes main memory size Thrashing Performance meltdown where pages are swapped copied in and out con0nuously 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 protec on Address transla on 18 Carnegie Mellon VM as a Tool for Memory Management Key idea each process has its own virtual address space It can view memory …
View Full Document
Unlocking...