Page 1Virtual MemoryOctober 2, 2002Topics• Motivations for VM• Address Translation• Accelerating with TLBs• Alpha 21X64 memory systemCS740CS 740 S’99–2– CS 740 F’02Motivation 1: DRAM a “Cache” for DiskThe 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 ~30X cheaper than DRAM storage• 8 GB of DRAM: ~ $12,000• 8 GB of disk: ~ $200To access large amounts of data in a cost-effective manner, the bulk of the data must be stored on disk20 GB: ~$400256 MB: ~$400 4 MB: ~$400DiskDRAMSRAMPage 2CS 740 S’99–3– CS 740 F’02Levels in Memory HierarchyCPUCPUregsregsCacheMemoryMemorydiskdisksize:speed:$/Mbyte:block size:200 B3 ns8 BRegister Cache Memory Disk Memory32 KB / 4MB6 ns$100/MB32 B128 MB60 ns$1.50/MB8 KB20 GB8 ms$0.05/MBlarger, slower, cheaper8 B 32 B 8 KBcache virtual memoryCS 740 S’99–4– CS 740 F’02DRAM vs. SRAM as a “Cache”DRAM vs. disk is more extreme than SRAM vs. DRAM• access latencies:– DRAM is ~10X slower than SRAM– disk is ~100,000X slower than DRAM• importance 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 ~100X larger than an SRAM cache• addressing for disk is based on sector address, not memory addressDRAMSRAMDiskPage 3CS 740 S’99–5– CS 740 F’02Impact of These Properties on DesignIf DRAM was to be organized similar to an SRAM cache, 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:• miss rate• hit time• miss latency• tag overheadCS 740 S’99–6– CS 740 F’02Locating an Object in a “Cache”1. Search for matching tag• SRAM cacheXObject Name2. Use indirection to look up actual object location• virtual memoryData24317105•••0:1:N-1:XObject NameLocation•••D:J:X:10N-1Tag DataD243X17J105••••••0:1:N-1:= X?“Cache”“Cache”Lookup TablePage 4CS 740 S’99–7– CS 740 F’02A System with Physical Memory OnlyExamples:• most Cray machines, early PCs, nearly all embedded systems, etc.CPU0:1:N-1:MemoryStore 0x10Load 0xf0CPU’s load or store addresses used directly to access memory.CS 740 S’99–8– CS 740 F’02A System with Virtual MemoryExamples:• workstations, 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 TableStore 0x10DiskVirtualAddressesPhysicalAddressesPage 5CS 740 S’99–9– CS 740 F’02Page Faults (Similar to “Cache Misses”)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 memory– current process suspends, others can resume– OS has full control over placement, etc.CPU0:1:N-1:MemoryLoad 0x050:1:P-1:Page TableStore 0xf8DiskVirtualAddressesPhysicalAddressesCS 740 S’99–10– CS 740 F’02Servicing a Page FaultProcessor Signals Controller• Read block of length P starting at disk address X and store starting at memory address YRead Occurs• Direct Memory Access• Under control of I/O controllerI / O Controller Signals Completion• Interrupt processor• Can resume suspended process diskDiskdiskDiskMemory-I/O busMemory-I/O busProcessorProcessorCacheCacheMemoryMemoryI/OcontrollerI/OcontrollerReg(2) DMA Transfer(1) Initiate Block Read(3) Read DonePage 6CS 740 S’99–11– CS 740 F’02Motivation #2: Memory ManagementMultiple processes can reside in physical memory.How do we resolve address conflicts?ReservedText (Code)Static DataNot yet allocatedStackDynamic Data0000 03FF 8000 0000ReservedNot yet allocated0000 0001 2000 00000000 0000 0001 0000$gp$spe.g., what if two different Alpha processes access their stacks at address 0x11fffff80 at the same time?(Virtual) Memory Image for Alpha ProcessCS 740 S’99–12– CS 740 F’02Process 1:Virtual AddressesPhysical AddressesVP 1VP 2Process 2:PP 2Address Translation00N-10N-1M-1VP 1VP 2PP 7PP 10(Read-only library code)Soln: Separate Virtual Addr. Spaces• Virtual and physical address spaces divided into equal-sized blocks– “Pages” (both virtual and physical)• Each process has its own virtual address space– operating system controls how virtual pages as assigned to physical memoryPage 7CS 740 S’99–13– CS 740 F’02Motivation #3: ProtectionPage table entry contains access rights information• hardware enforces this protection (trap into OS if violation occurs)Page TablesProcess i:Physical AddrRead? Write?PP 9Yes NoPP 4Yes YesXXXXXXXNo NoVP 0:VP 1:VP 2:•••••••••Process j:0:1:N-1:MemoryPhysical AddrRead? Write?PP 6Yes YesPP 9Yes NoXXXXXXXNo No•••••••••VP 0:VP 1:VP 2:CS 740 S’99–14– CS 740 F’02VM Address TranslationV = {0, 1, . . . , N–1} virtual address spaceP = {0, 1, . . . , M–1} physical address spaceMAP: V → P U {∅} address mapping functionN > MMAP(a) = a' if data at virtual address ais present at physical address a'in P= ∅ if data at virtual address a is not present in PProcessorAddr TransMechanismfaulthandlerMainMemorySecondary memoryaa'∅missing item faultphysical addressOS performsthis transfer(only if miss)Page 8CS 740 S’99–15– CS 740 F’02virtual page number page offsetvirtual addressphysical page number page offsetphysical address0p–1address translationpm–1n–1 0p–1pNotice that the page offset bits don't change as a result of translationVM Address TranslationParameters• P = 2p= page size (bytes). Typically 1KB–16KB• N = 2n= Virtual address limit• M = 2m= Physical address limitCS 740 S’99–16– CS 740 F’02Page TablesPage Table(physical page or disk address)Physical MemoryDisk StorageValid1111111000Virtual PageNumberPage 9CS 740 S’99–17– CS 740 F’02Address Translation via Page Tablevirtual page number page offsetvirtual addressphysical page number page offsetphysical address0p–1pm–1n–1 0p–1ppage table base registerif valid=0then pagenot in memoryvalidphysical page numberaccessVPN acts astable indexAddressCS 740 S’99–18– CS 740 F’02Page Table
View Full Document
Unlocking...