Slide 1TodayA System Using Physical AddressingA System Using Virtual AddressingAddress SpacesWhy Virtual Memory (VM)?TodayVM as a Tool for CachingDRAM Cache OrganizationPage TablesPage HitPage FaultHandling Page FaultHandling Page FaultHandling Page FaultHandling Page FaultLocality to the Rescue Again!TodayVM as a Tool for Memory ManagementVM as a Tool for Memory ManagementSimplifying Linking and LoadingTodayVM as a Tool for Memory ProtectionTodayVM Address TranslationSummary of Address Translation SymbolsAddress Translation With a Page TableAddress Translation: Page HitAddress Translation: Page FaultIntegrating VM and CacheSpeeding up Translation with a TLBTLB HitTLB MissMulti-Level Page TablesA Two-Level Page Table HierarchySummaryCarnegie Mellon1Virtual Memory: Concepts15-213: Introduction to Computer Systems15th Lecture, Oct. 14, 2010Instructors: Randy Bryant and Dave O’HallaronCarnegie Mellon2TodayAddress spacesVM as a tool for cachingVM as a tool for memory managementVM as a tool for memory protectionAddress translationCarnegie Mellon3A System Using Physical AddressingUsed in “simple” systems like embedded microcontrollers in devices like cars, elevators, and digital picture frames0:1:M-1:Main memoryCPU2:3:4:5:6:7:Physical address(PA)Data word8:...4Carnegie Mellon4A System Using Virtual AddressingUsed in all modern servers, desktops, and laptopsOne of the great ideas in computer science0:1:M-1:Main memoryMMU2:3:4:5:6:7:Physical address(PA)Data word8:...CPUVirtual address(VA)CPU Chip44100Carnegie Mellon5Address SpacesLinear 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 addressesEvery byte in main memory: one physical address, one (or more) virtual addressesCarnegie Mellon6Why Virtual Memory (VM)?Uses main memory efficientlyUse DRAM as a cache for the parts of a virtual address spaceSimplifies memory managementEach process gets the same uniform linear address spaceIsolates address spacesOne process can’t interfere with another’s memoryUser program cannot access privileged kernel informationCarnegie Mellon7TodayAddress spacesVM as a tool for cachingVM as a tool for memory managementVM as a tool for memory protectionAddress translationCarnegie Mellon8VM as a Tool for CachingVirtual 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)PP 2m-p-1Physical memoryEmptyEmptyUncachedVP 0VP 1VP 2n-p-1Virtual memoryUnallocatedCachedUncachedUnallocatedCachedUncachedPP 0PP 1EmptyCached0N-1M-10Virtual pages (VPs) stored on diskPhysical pages (PPs) cached in DRAMCarnegie Mellon9DRAM Cache OrganizationDRAM cache organization driven by the enormous miss penaltyDRAM is about 10x slower than SRAMDisk is about 10,000x slower than DRAMConsequencesLarge page (block) size: typically 4-8 KB, sometimes 4 MBFully associative Any VP can be placed in any PPRequires a “large” mapping function – different from CPU cachesHighly sophisticated, expensive replacement algorithmsToo complicated and open-ended to be implemented in hardwareWrite-back rather than write-throughCarnegie Mellon10Page TablesA page table is an array of page table entries (PTEs) that maps virtual pages to physical pages. 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 Mellon11Page HitPage hit: reference to VM word that is in physical memory (DRAM cache hit)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 Mellon12Page FaultPage fault: reference to VM word that is not in physical memory (DRAM cache miss)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 Mellon13Handling Page FaultPage 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 Mellon14Handling Page FaultPage 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 Mellon15Handling Page FaultPage 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 Mellon16Handling Page FaultPage 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 Mellon17Locality to the Rescue Again!Virtual memory works because of localityAt any point in time, programs tend to access a set of active virtual pages called the working setPrograms with better temporal locality will have smaller working setsIf (working set size < main memory size) Good performance for one process after compulsory missesIf ( SUM(working set sizes) > main memory size ) Thrashing: Performance meltdown where pages are swapped (copied) in and out continuouslyCarnegie Mellon18TodayAddress spacesVM as a tool for cachingVM as a
View Full Document
Unlocking...