Virtual Memory November 2, 2007Why Virtual Memory?Motivation 1: DRAM a “Cache” for DiskLevels in Memory HierarchyDRAM vs. SRAM as a “Cache”Impact of These Properties on DesignLocating an Object in a “Cache”A System with Physical Memory OnlyA System with Virtual MemoryPage Faults (Similar to “Cache Misses”)Servicing a Page FaultLocality to the Rescue(2) VM as a Tool for Memory MgmtSimplifying Sharing and AllocationSimplifying Linking and Loading(3)VM as a Tool for Memory ProtectionAddress SpacesVM Address TranslationAddress Translation with a Page TableAddress Translation: Page HitAddress Translation: Page FaultIntegrating VM and CacheSpeeding 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 #3Multi-Level Page TablesA Two-Level Page Table HierarchyTranslating with a k-level Page TableSummaryVirtual MemoryNovember 2, 2007Virtual MemoryNovember 2, 2007TopicsMotivations for virtual memoryAddress translationAccelerating translation with TLBsclass19.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, F’07Why Virtual Memory?Why Virtual Memory?(1) VM uses main memory efficiently Main memory is a cache for the contents of a virtual address space stored on disk.Keep only active areas of virtual address space in memoryTransfer data back and forth as needed.(2) VM simplifies memory management Each process gets the same linear address space.(3) VM protects address spacesOne process can’t interfere with another.Because they operate in different address spaces.User process cannot access privileged informationDifferent sections of address spaces have different permissions.– 3 –15-213, F’07Motivation 1: DRAM a “Cache” for DiskMotivation 1: DRAM a “Cache” for DiskThe full address space is quite large:The full address space is quite large:32-bit addresses: ~4,000,000,000 (4 billion) bytes64-bit addresses: ~16,000,000,000,000,000,000 (16 quintillion) bytesDisk storage is ~100X cheaper than DRAM storageDisk storage is ~100X cheaper than DRAM storage1 TB of DRAM: ~ $30,0001 TB of disk: ~ $300To access large amounts of data in a cost-effective To access large amounts of data in a cost-effective manner, the bulk of the data must be stored on diskmanner, the bulk of the data must be stored on disk1 TB: ~$3008 GB: ~$300 4 MB: ~$300DiskDRAMSRAM– 4 –15-213, F’07Levels in Memory HierarchyLevels in Memory Hierarchyregisterson-chip L1cache (SRAM)main memory(DRAM)local secondary storage(local disks)Larger, slower, and cheaper (per byte)storagedevicesremote secondary storage(tapes, distributed file systems, Web servers)Local disks hold files retrieved from disks on remote network servers.Main memory holds disk blocks retrieved from local disks.off-chip L2cache (SRAM)L1 cache holds cache lines retrieved from the L2 cache memory.CPU registers hold words retrieved from L1 cache.L2 cache holds cache lines retrieved from main memory.L0:L1:L2:L3:L4:L5:Smaller,faster,and costlier(per byte)storage devices– 5 –15-213, F’07DRAM vs. SRAM as a “Cache”DRAM vs. SRAM as a “Cache”DRAM vs. disk is more extreme than SRAM vs. DRAMDRAM vs. disk is more extreme than SRAM vs. DRAMaccess latencies:DRAM is ~10X slower than SRAMdisk is ~100,000X slower than DRAMimportance of exploiting spatial locality:first byte is ~100,000X slower than successive bytes on disk»vs. ~4X improvement for page-mode vs. regular accesses to DRAM“cache” size:main memory is ~1000X larger than an SRAM cacheaddressing for disk is based on sector address, not memory addressDRAMSRAMDisk– 6 –15-213, F’07Impact of These Properties on DesignImpact of These Properties on DesignIf DRAM was to be organized similar to an SRAM cache, If DRAM was to be organized similar to an SRAM cache, how would we set the following design parameters?how would we set the following design parameters?Line size?Associativity?Replacement policy (if associative)?Write through or write back?What would the impact of these choices be on:What would the impact of these choices be on:miss ratehit timemiss latencytag overhead– 7 –15-213, F’07Locating an Object in a “Cache”Locating an Object in a “Cache”1. Search for matching tag1. Search for matching tagSRAM cacheXObject NameTag DataD 243X 17J 105••••••0:1:N-1:= X?“Cache”2. Use indirection to look up actual object location2. Use indirection to look up actual object locationvirtual memoryData243 17105•••0:1:N-1:XObject NameLocation•••D:J:X: 10N-1“Cache”Lookup Table– 8 –15-213, F’07A System with Physical Memory OnlyA System with Physical Memory OnlyExamples:Examples:most Cray machines, early PCs, nearly all embedded systems (phones, PDAs, etc.)CPU0:1:N-1:MemoryStore 0x10Load 0xf0CPU’s load or store addresses used directly to access memory.– 9 –15-213, F’07A System with Virtual MemoryA System with Virtual MemoryExamples:Examples:laptops, servers, modern PCs, etc.Address Translation: the hardware converts virtual addresses into physical addresses via an OS-managed lookup table (page table)CPU0:1:N-1:MemoryLoad 0xf00:1:P-1:Page Table (MMU)Store 0x10DiskVirtualAddressesPhysicalAddresses– 10 –15-213, F’07Page Faults (Similar to “Cache Misses”)Page Faults (Similar to “Cache Misses”)What if an object is on disk rather than in memory?What if an object is on disk rather than in memory?Page table entry indicates that the virtual address is not in memoryAn OS trap handler is invoked, moving data from disk into memorycurrent process suspends, others can resumeOS has full control over placement, etc.CPU0:1:N-1:MemoryLoad 0x050:1:P-1:Page Table (MMU)Store 0xf8DiskVirtualAddressesPhysicalAddresses– 11 –15-213, F’07Servicing a Page FaultServicing a Page Fault(1) Processor signals controllerRead block of length P starting at disk address X and store starting at memory address Y(2) Read occursDirect Memory Access (DMA)Under control of I/O controller(3) Controller signals completionInterrupt processorOS resumes suspended process diskDiskdiskDiskMemory-I/O busMemory-I/O busProcessorProcessorCacheCacheMemoryMemoryI/OcontrollerI/OcontrollerReg(2) DMA Transfer(1)
View Full Document