Introduction to Computer Systems 15-213, fall 2009 16th Lecture, Oct. 21stTodayVirtual 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 200916thLecture, Oct. 21stInstructors:Majd Sakr and Khaled HarrasCarnegie 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 tablesCarnegie Mellon Programs refer to virtual memory addresses movl (%ecx),%eax Conceptually very large array of bytes Each byte has its own address Actually implemented with hierarchy of different memory types System provides address space private to particular “process” Allocation: Compiler and run‐time system Where different program objects should be stored All allocation within single virtual address space But why virtual memory? Why not physical memory?Virtual Memory (Previous Lectures)00······0FF······FCarnegie 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 Indirection Each process gets its own private memory space Solves the previous problemsPhysical memoryVirtual memoryVirtual memoryProcess 1Process nmappingCarnegie MellonAddress Spaces Linear address space: Ordered set of contiguous non‐negative integer addresses:{0, 1, 2, 3 …} Virtual addres s space: Set of N = 2nvirtual addresses{0, 1, 2, 3, …, N‐1} Physical address space: Set of M = 2mphysical 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 addressesCarnegie MellonA System Using Physical Addressing Used 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 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 MellonWhy Virtual Memory (VM)? Efficient use of limited main memory (RAM) Use RAM as a cache for the parts of a virtual address space some non‐cached parts stored on disk some (unallocated) non‐cached parts stored nowhere Keep only active areas of virtual address space in memory transfer data back and forth as needed Simplifies memory management for programmers Each process gets the same full, private linear address space Isolates address spaces One process can’t interfe re with another’s memory because they operate in different address spaces User process cannot access privileged information different sections of address spaces have different permissionsCarnegie 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 tablesCarnegie 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‐10⊇Virtual pages (VP's) stored on diskPhysical pages (PP's) cached in DRAMDiskCarnegie MellonMemory Hierarchy: Core 2 DuoDiskMain MemoryL2 unified cacheL1 I‐cacheL1 D‐cacheCPUReg1 B/30 cyclesmillions~4 MB32 KB~4 GB ~500 GBL1/L2 cache: 64 B blocks2 B/cycle8 B/cycle16 B/cycleThroughput:Latency: 100 cycles14 cycles3 cyclesNot drawn to scale Miss penalty (latency): 30xMiss penalty (latency): 10,000xCarnegie
View Full Document