Virtual MemoryMotivations for Virtual MemoryMotivation #1: DRAM As “Cache” for DiskLevels in Memory HierarchyDRAM vs. SRAM as a “Cache”Impact of Properties on DesignLocating an Object in a “Cache”Locating an Object in a “Cache”A System with Physical Memory OnlyA System with Virtual MemoryPage Faults (like “Cache Misses”)Servicing a Page FaultMotivation #2: Memory MgmtSolution: Separate Virtual Address SpacesContrast: Macintosh Memory ModelMacintosh Memory ManagementMac vs. VM-Based Memory ManagementMAC OS XMotivation #3: ProtectionVM Address TranslationVM Address Translation: HitVM Address Translation: MissSlide 23Page TablesAddress Translation via Page TablePage Table OperationSlide 27Slide 28Integrating VM and CacheSpeeding up Translation with a TLBAddress Translation with a TLBMulti-Level Page TablesMain ThemesVirtual MemoryVirtual MemoryTopicsTopicsMotivations for VMAddress translationAccelerating translation with TLBsVM1CS 105“Tour of the Black Holes of Computing!”– 2 –CS 105Motivations for Virtual MemoryMotivations for Virtual MemoryUse Physical DRAM as a Cache for the DiskUse Physical DRAM as a Cache for the DiskAddress space of a process can exceed physical memory sizeSum of address spaces of multiple processes can exceed physical memorySimplify Memory ManagementSimplify Memory ManagementMultiple processes resident in main memory.Each process with its own address spaceOnly “active” code and data is actually in memoryAllocate more memory to process as needed.Provide ProtectionProvide ProtectionOne 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 –CS 105Motivation #1: DRAM As“Cache” for DiskMotivation #1: DRAM As“Cache” for DiskFull address space is quite large: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 ~300X cheaper than DRAM storageDisk storage is ~300X cheaper than DRAM storage250 GB of DRAM: ~ $25,000 (667 MHz, late 2006 prices)250 GB of disk: ~ $55To access large amounts of data in a cost-effective manner, To access large amounts of data in a cost-effective manner, the bulk of the data must be stored on diskthe bulk of the data must be stored on disk1GB: ~$110 250 GB: ~$554 MB: ~$250DiskDRAMSRAM– 4 –CS 105Levels in Memory HierarchyLevels in Memory HierarchyCPUCPUregsregsCacheMemoryMemorydiskdisksize:speed:$/Mbyte:line size:32 B0.3 ns8 BRegister Cache Memory Disk Memory32 KB-4MB2 ns?$65/MB32 B2048 MB7.5 ns$0.10/MB4 KB250 GB8 ms$0.0002/MBlarger, slower, cheaper8 B 32 B 4 KBcache virtual memory– 5 –CS 105DRAM 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 ~10X slower than SRAMDisk ~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 DRAMBottom line: Design decisions made for DRAM caches driven by enormous cost of missesDRAMSRAMDisk– 6 –CS 105Impact of Properties on DesignImpact of Properties on DesignIf DRAM was to be organized similar to an SRAM cache, how would If DRAM was to be organized similar to an SRAM cache, how would we set the following design parameters?we set the following design parameters?Line size?Large, since disk better at transferring large blocksAssociativity?High, to mimimize miss rateWrite through or write back?Write back, since can’t afford to perform small writes to diskWhat would the impact of these choices be on:What would the impact of these choices be on:miss rateExtremely low. << 1%hit timeMust match cache/DRAM performancemiss latencyVery high. ~20mstag storage overheadLow, relative to block size– 7 –CS 105Locating an Object in a “Cache”Locating an Object in a “Cache”SRAM CacheSRAM CacheTag stored with cache lineMaps from cache block to memory blocksFrom cached to uncached formSave a few bits by only storing tag of data blocks in cacheNo tag for block not in cacheHardware retrieves informationCan quickly match against multiple tagsXObject NameTag DataD 243X 17J 105••••••0:1:N-1:= X?“Cache”– 8 –CS 105Locating an Object in a “Cache” Locating an Object in a “Cache” Data243 17105•••0:1:N-1:XObject NameLocation•••D:J:X: 10On Disk“Cache”Page TableDRAM CacheDRAM CacheEach allocated page of virtual memory has entry in page tableMapping from virtual pages to physical pagesFrom uncached form to cached formPage table entry (tag) even if page not in memorySpecifies disk addressOnly way to indicate where to find pageOS retrieves information– 9 –CS 105A System withPhysical Memory OnlyA System withPhysical Memory OnlyExamples:Examples:Most Cray machines, early PCs, nearly all embedded systems, etc.Addresses generated by the CPU correspond directly to bytes in physical memoryCPU0:1:N-1:MemoryPhysicalAddresses– 10 –CS 105A System with Virtual MemoryA System with Virtual MemoryExamples:Examples:Workstations, servers, modern PCs, etc.Address Translation: Hardware converts virtual addresses to physical addresses via OS-managed lookup table (page table)CPU0:1:N-1:Memory0:1:P-1:Page TableDiskVirtualAddressesPhysicalAddresses– 11 –CS 105Page Faults (like “Cache Misses”)Page Faults (like “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 virtual address not in memoryOS exception handler invoked to move data from disk into memory - VM and Multiprogramming are symbioticCurrent process suspends, others can resumeOS has full control over placement, etc.CPUMemoryPage TableDiskVirtualAddressesPhysicalAddressesCPUMemoryPage TableDiskVirtualAddressesPhysicalAddressesBefore faultAfter fault– 12 –CS 105Servicing a Page FaultServicing a Page FaultProcessor Signals ControllerProcessor Signals ControllerRead block of length P starting at disk address X and store starting at memory address YRead OccursRead
View Full Document
Unlocking...