Carnegie MellonIntroduction to Computer Systems15-213/18-243, spring 200917thLecture, Mar. 19thInstructors:Gregory Kesden and Markus PüschelCarnegie MellonLast Time: Virtual Memory Each process gets its own private memory space Solves the previous problemsPhysical memoryVirtual memoryVirtual memoryProcess 1Process nmappingCarnegie MellonA System Using Virtual Addressing Used in all modern desktops, laptops, workstations One of the great ideas in computer science MMU checks the cache0:1:M-1:Main memoryMMU2:3:4:5:6:7:Physical address(PA)Data word8:...CPUVirtual address(VA)CPU ChipCarnegie MellonToday 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 systemCarnegie MellonVM as a Tool for Caching Virtual memory: array of N = 2ncontiguous 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 = 2pPP 2m-p-1Physical memoryEmptyEmptyUncachedVP 0VP 1VP 2n-p-1Virtual memoryUnallocatedCachedUncachedUnallocatedCachedUncachedPP 0PP 1EmptyCached02n-12m-10Virtual pages (VP's) stored on diskPhysical pages (PP's) cached in DRAMDiskCarnegie MellonMemory Hierarchy: Core 2 DuoDiskMain MemoryL2 unified cacheL1 I-cacheL1 D-cacheCPU Reg2 B/cycle8 B/cycle16 B/cycle 1 B/30 cyclesThroughput:Latency: 100 cycles14 cycles3 cycles millions~4 MB32 KB~4 GB ~500 GBNot drawn to scale L1/L2 cache: 64 B blocksMiss penalty (latency): 30xMiss penalty (latency): 10,000xCarnegie MellonDRAM 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-throughCarnegie MellonAddress 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 DRAMnullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Carnegie MellonAddress Translation With a Page TableVirtual page number (VPN) Virtual page offset (VPO)Physical page number (PPN) Physical page offset (PPO)Virtual addressPhysical addressValidPhysical page number (PPN)Page table base register(PTBR)Page table Page table address for processValid bit = 0:page not in memory(page fault)Carnegie MellonPage Hit Page hit: reference to VM word that is in physical memorynullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressCarnegie MellonPage Miss Page miss: reference to VM word that is not in physical memorynullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressCarnegie MellonHandling Page Fault Page miss causes page fault (an exception)nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressCarnegie MellonHandling Page Fault Page miss causes page fault (an exception) Page fault handler selects a victim to be evicted (here VP 4)nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressCarnegie MellonHandling Page Fault Page miss causes page fault (an exception) Page fault handler selects a victim to be evicted (here VP 4)nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 3Virtual memory(disk)Valid01100101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressCarnegie MellonHandling 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!nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 3Virtual memory(disk)Valid01100101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressCarnegie MellonWhy 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 continuouslyCarnegie MellonToday 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 systemCarnegie MellonVM 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 managementVirtual Address Space for Process 1:Physical Address Space (DRAM)0N-1(e.g., read-only library code)Virtual Address Space for Process 2:VP 1VP 2...0N-1VP 1VP 2...PP 2PP 6PP 8...0M-1Address translationCarnegie MellonVM as a Tool for Memory Management Memory allocation Each virtual page can be mapped to any physical page A virtual page can be stored in different physical pages at different times Sharing code and data among processes Map virtual pages to the same physical page (here: PP 6)Virtual Address Space for Process
View Full Document
Unlocking...