Page 1–1–15-740, F’07Virtual MemoryCS 740October 23, 2007TopicsTopics Virtual Memory:z motivationz mechanisms Accelerating translation with TLBs–2–15-740, F’07Why 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 memory Transfer data back and forth as needed.(2) VM simplifies memory management Each process gets the same linear address space.(3) VM protects address spaces One process can’t interfere with another.z Because they operate in different address spaces. User process cannot access privileged informationz Different sections of address spaces have different permissions.–3–15-740, F’07Motivation 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) bytes 64-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 storage 1 TB of DRAM: ~ $30,000 1 TB of disk: ~ $300To access large amounts of data in a costTo access large amounts of data in a cost--effective manner, the effective manner, the bulk of the data must be stored on diskbulk of the data must be stored on disk1 TB: ~$3008 GB: ~$300 4 MB: ~$300DiskDRAMSRAM–4–15-740, F’07Levels 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 devicesPage 2–5–15-740, F’07DRAM vs. SRAM as a “Cache”DRAM vs. disk is more extreme than SRAM vs. DRAMDRAM vs. disk is more extreme than SRAM vs. DRAM access latencies:z DRAM is ~10X slower than SRAMz disk is ~100,000X slower than DRAM importance of exploiting spatial locality:z first byte is ~100,000X slower than successive bytes on disk» vs. ~4X improvement for page-mode vs. regular accesses to DRAM “cache” size:z main memory is ~1000X larger than an SRAM cache addressing for disk is based on sector address, not memory addressDRAMSRAMDisk–6–15-740, F’07Impact 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 rate hit time miss latency tag overhead–7–15-740, F’07Locating an Object in a “Cache”1. Search for matching tag1. Search for matching tag SRAM cacheXObject NameTag DataD243X17J105••••••0:1:N-1:= X?“Cache”2. Use indirection to look up actual object location2. Use indirection to look up actual object location virtual memoryData24317105•••0:1:N-1:XObject NameLocation•••D:J:X: 10N-1“Cache”Lookup Table–8–15-740, F’07A 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.Page 3–9–15-740, F’07A System with Virtual MemoryExamples:Examples: laptops, servers, modern PCs, etc.Address Translation:the hardware converts virtual addressesinto 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-740, F’07Page 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 memory An OS trap handler is invoked, moving data from disk into memoryz current process suspends, others can resumez OS has full control over placement, etc.CPU0:1:N-1:MemoryLoad 0x050:1:P-1:Page Table (MMU)Store 0xf8DiskVirtualAddressesPhysicalAddresses–11–15-740, F’07Servicing a Page Fault(1) Processor signals controller Read block of length P starting at disk address X and store starting at memory address Y(2) Read occurs Direct Memory Access (DMA) Under control of I/O controller(3) Controller signals completion Interrupt processor OS resumes suspended process diskDiskdiskDiskMemory-I/O busMemory-I/O busProcessorProcessorCacheCacheMemoryMemoryI/OcontrollerI/OcontrollerReg(2) DMA Transfer(1) Initiate Block Read(3) Read Done–12–15-740, F’07Locality to the RescueVirtual memory works because of locality.Virtual memory works because of locality.At any point in time, programs tend to access a set At any point in time, programs tend to access a set of active virtual pages called the of active virtual pages called the working setworking set. . Programs with better temporal locality will have smaller working sets.If working set size < main memory size If working set size < main memory size Good performance after initial compulsory misses.If working set size > main memory size If working set size > main memory size Thrashing: Performance meltdown where pages are swapped (copied) in and out continuouslyPage 4–13–15-740, F’07(2) VM as a Tool for Memory MgmtKey idea: Each process has its own virtual address space Simplifies memory allocation, sharing, linking, and loading.Virtual Address Space for Process 1:Physical Address Space (DRAM)VP 1VP 2PP 2Address Translation00N-10N-1M-1VP 1VP 2PP 7PP 10(e.g., read/only library code)......Virtual Address Space for Process 2:–14–15-740, F’07Simplifying Sharing and AllocationSharing code and data among processes Map virtual pages to the same physical page (PP 7)Memory allocation Virtual page can be mapped to any physical pageVirtual Address Space for Process 1:Physical Address Space
View Full Document
Unlocking...