Slide 1TodayVirtual Memory (Previous Lectures)Problem 1: How Does Everything Fit?Problem 2: Memory ManagementProblem 3: How To ProtectSolution: Level Of IndirectionAddress SpacesA System Using Physical AddressingA System Using Virtual AddressingWhy Virtual Memory (VM)?TodayVM as a Tool for CachingMemory Hierarchy: Core 2 DuoDRAM Cache OrganizationAddress Translation: Page TablesAddress Translation With a Page TablePage HitPage MissHandling Page FaultHandling Page FaultHandling Page FaultHandling Page FaultWhy does it work? LocalityTodayVM as a Tool for Memory ManagementVM as a Tool for Memory ManagementSimplifying Linking and LoadingTodayVM as a Tool for Memory ProtectionTodayAddress Translation: Page HitAddress Translation: Page FaultSpeeding up Translation with a TLBTLB HitTLB MissSimple Memory System ExampleSimple Memory System Page TableSimple Memory System TLBSimple Memory System CacheAddress Translation Example #1Address Translation Example #2Address Translation Example #3SummaryTodayAllocating Virtual PagesAllocating Virtual PagesMulti-Level Page TablesA Two-Level Page Table HierarchyTranslating with a k-level Page TableCarnegie MellonIntroduction to Computer Systems15-213, fall 200916th Lecture, Oct. 21stInstructors: Majd Sakr and Khaled HarrasCarnegie MellonTodayVirtual memory (VM)Overview and motivationVM as tool for cachingVM as tool for memory managementVM as tool for memory protectionAddress translationAllocation, multi-level page tablesCarnegie MellonPrograms refer to virtual memory addressesmovl (%ecx),%eaxConceptually very large array of bytesEach byte has its own addressActually implemented with hierarchy of different memory typesSystem provides address space private to particular “process”Allocation: Compiler and run-time systemWhere different program objects should be storedAll allocation within single virtual address spaceBut why virtual memory? Why not physical memory?Virtual Memory (Previous Lectures)00 0∙∙∙∙∙∙FF F∙∙∙∙∙∙Carnegie MellonProblem 1: How Does Everything Fit?64-bit addresses:16 ExabytePhysical main memory:Few Gigabytes?And there are many processes ….Carnegie MellonProblem 2: Memory ManagementPhysical main memoryWhat goes where?stackheap.text.data…Process 1Process 2Process 3…Process nxCarnegie MellonProblem 3: How To ProtectPhysical main memoryProcess iProcess jProblem 4: How To Share?Physical main memoryProcess iProcess jCarnegie MellonSolution: Level Of IndirectionEach process gets its own private memory spaceSolves the previous problemsPhysical memoryVirtual memoryVirtual memoryProcess 1Process nmappingCarnegie MellonAddress 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 MellonA 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:...Carnegie MellonA System Using Virtual AddressingUsed in all modern desktops, laptops, workstationsOne of the great ideas in computer scienceMMU checks the cache0:1:M-1:Main memoryMMU2:3:4:5:6:7:Physical address(PA)Data word8:...CPUVirtual address(VA)CPU ChipCarnegie MellonWhy Virtual Memory (VM)?Efficient use of limited main memory (RAM)Use RAM as a cache for the parts of a virtual address spacesome non-cached parts stored on disksome (unallocated) non-cached parts stored nowhereKeep only active areas of virtual address space in memorytransfer data back and forth as neededSimplifies memory management for programmersEach process gets the same full, private linear address spaceIsolates address spacesOne process can’t interfere with another’s memorybecause they operate in different address spacesUser process cannot access privileged informationdifferent sections of address spaces have different permissionsCarnegie MellonTodayVirtual memory (VM)Overview and motivationVM as tool for cachingVM as tool for memory managementVM as tool for memory protectionAddress translationAllocation, multi-level page tablesCarnegie MellonVM as a Tool for CachingVirtual memory: array of N = 2n contiguous bytesthink of the array (allocated part) as being stored on diskPhysical main memory (DRAM) = cache for allocated virtual memoryBlocks 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 OrganizationDRAM cache organization driven by the enormous miss penaltyDRAM is about 10x slower than SRAMDisk is about 10,000x slower than DRAMFor first byte, faster for next byteConsequencesLarge 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 MellonAddress Translation: Page TablesA page table is an array of page table entries (PTEs) that maps virtual pages to physical pages. Here: 8 VPsPer-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
View Full Document