Virtual Memory Oct. 29, 2002Motivations for Virtual MemoryWhy VM Works?Motivation #1: DRAM a “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 “Cache” (cont.)A System with Physical Memory OnlyA System with Virtual MemoryPage Faults (like “Cache Misses”)Servicing a Page FaultMotivation #2: Memory ManagementSolution: Separate Virt. Addr. SpacesContrast: Macintosh Memory ModelMacintosh Memory ManagementMac vs. VM-Based Memory MgmtMAC OS XMotivation #3: ProtectionVM Address TranslationVM Address Translation: HitVM Address Translation: MissSlide 24Page TablesAddress Translation via Page TablePage Table OperationSlide 28Slide 29Integrating VM and CacheSpeeding up Translation with a TLBAddress Translation with a TLBSimple Memory System ExampleSimple Memory System Page TableSimple Memory System TLBSimple Memory System CacheAddress Translation Example #1Address Translation Example #2Address Translation Example #3Multi-Level Page TablesMain ThemesVirtual MemoryOct. 29, 2002TopicsMotivations for VMAddress translationAccelerating translation with TLBsclass18.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, S’03Motivations for Virtual MemoryUse 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 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 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 –15-213, S’03Why VM Works?It is not used.– 4 –15-213, S’03Motivation #1: DRAM a “Cache” for DiskFull 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 storage80 GB of DRAM: ~ $33,00080 GB of disk: ~ $110To access large amounts of data in a cost-effective manner, the bulk of the data must be stored on disk1GB: ~$200 80 GB: ~$1104 MB: ~$500DiskDRAMSRAM– 5 –15-213, S’03Levels in Memory HierarchyCPUCPUregsCacheMemoryMemorydiskdisksize:speed:$/Mbyte:line size:32 B1 ns8 BRegister Cache Memory Disk Memory32 KB-4MB2 ns$125/MB32 B1024 MB30 ns$0.20/MB4 KB100 GB8 ms$0.001/MBlarger, slower, cheaper8 B 32 B 4 KBcache virtual memory– 6 –15-213, S’03DRAM vs. SRAM as a “Cache”DRAM 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– 7 –15-213, S’03Impact of Properties on DesignIf DRAM was to be organized similar to an SRAM cache, how would 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:miss rateExtremely low. << 1%hit timeMust match cache/DRAM performancemiss latencyVery high. ~20mstag storage overheadLow, relative to block size– 8 –15-213, S’03Locating an Object in a “Cache”SRAM CacheTag stored with cache lineMaps from cache block to memory blocksFrom cached to uncached formSave a few bits by only storing tagNo tag for block not in cacheHardware retrieves informationcan quickly match against multiple tagsXObject NameTag DataD 243X 17J 105••••••0:1:N-1:= X?“Cache”– 9 –15-213, S’03Locating an Object in “Cache” (cont.)Data243 17105•••0:1:N-1:XObject NameLocation•••D:J:X: 10On Disk“Cache”Page TableDRAM CacheEach allocated page of virtual memory has entry in page tableMapping from virtual pages to physical pagesFrom uncached form to cached formPage table entry even if page not in memorySpecifies disk addressOnly way to indicate where to find pageOS retrieves information– 10 –15-213, S’03A System with Physical Memory OnlyExamples: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– 11 –15-213, S’03A System with Virtual MemoryExamples: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– 12 –15-213, S’03Page Faults (like “Cache Misses”)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 memorycurrent process suspends, others can resumeOS has full control over placement, etc.CPUMemoryPage TableDiskVirtualAddressesPhysicalAddressesCPUMemoryPage TableDiskVirtualAddressesPhysicalAddressesBefore faultAfter fault– 13 –15-213, S’03Servicing a Page FaultProcessor Signals ControllerRead block of length P starting at disk address X and store starting at memory address YRead OccursDirect Memory Access (DMA)Under control of I/O controllerI / O Controller Signals CompletionInterrupt processorOS resumes suspended process diskDiskdiskDiskMemory-I/O busMemory-I/O busProcessorProcessorCacheCacheMemoryMemoryI/OcontrollerI/OcontrollerReg(2) DMA Transfer(1) Initiate Block Read(3) Read Done– 14 –15-213, S’03Motivation #2: Memory ManagementMultiple processes can reside in physical memory.How do we resolve address conflicts?what if two processes access something at the same address?kernel virtual memoryMemory mapped region forshared librariesruntime heap (via malloc)program text (.text)initialized data (.data)uninitialized data
View Full Document
Unlocking...