Virtual MemoryOctober 14, 2008Topics Address spaces Motivations for virtual memory Address translation Accelerating translation with TLBslecture-14.ppt15-213“The course that gives CMU its Zip!”215-213, S’08AnnouncementsAutolabAutolaboutageoutage The autolab machine was hacked on Saturday not the autolab programs, but the underlying OS rebuilt and brought back online Monday Should not block your progress on shelllab all files needed were made available on class website (under docs link) fish machines are working fine Re-submit tshlab, if you finished before the outage as always, there was a time gap between last backup and the breakin315-213, S’08Programs Refer to Virtual Memory AddressesPrograms Refer to Virtual Memory Addresses Conceptually very large array of bytes Actually implemented with hierarchy of different memory types System provides address space private to particular “process” Program being executed Program can clobber its own data, but not that of othersCompiler + RunCompiler + Run--Time System Control AllocationTime System Control Allocation Where different program objects should be stored All allocation within single virtual address spaceByte-Oriented Memory Organization•••00•••0FF•••FFrom class02.ppt415-213, S’08Simple Addressing ModesNormalNormal(R)(R)Mem[Reg[RMem[Reg[R]]]] Register R specifies memory addressmovl (%ecx),%eaxDisplacementDisplacementD(R)D(R)Mem[Reg[R]+DMem[Reg[R]+D]] Register R specifies start of memory region Constant displacement D specifies offsetmovl 8(%ebp),%edxFrom class04.ppt515-213, S’08How does everything fit?How does everything fit? 32-bit addresses: ~4,000,000,000 (4 billion) bytes 64-bit addresses: ~16,000,000,000,000,000,000 (16 quintillion) bytesHow to decide which memory to use in your program?How to decide which memory to use in your program? How about after a fork()?What if another process stores data into your memory?What if another process stores data into your memory? How could you debug your program?Lets think on this: physical memory?•••00•••0FF•••F615-213, S’08So, we add a level of indirectionOne simple trick solves all three problemsOne simple trick solves all three problems Each process gets its own private image of memory appears to be a full-sized private memory range This fixes “how to choose” and “others shouldn’t mess w/yours” surprisingly, it also fixes “making everything fit” Implementation: translate addresses transparently add a mapping function to map private addresses to physical addresses do the mapping on every load or storeThis mapping trick is the heart of This mapping trick is the heart of virtual memoryvirtual memory715-213, S’08Address SpacesA A linear address space linear address space is an ordered set of contiguous is an ordered set of contiguous nonnegative integer addresses:nonnegative integer addresses:{0, 1, 2, 3, {0, 1, 2, 3, ……}}A A virtual address spacevirtual address spaceis a set of N = 2is a set of N = 2nnvirtual addressesvirtual addresses::{0, 1, 2, {0, 1, 2, ……, N, N--1}1}A A physical address spacephysical address spaceis a set of M = 2is a set of M = 2mm(for convenience) (for convenience) physical addressesphysical addresses::{0, 1, 2, {0, 1, 2, ……, M, M--1}1}In a system based on virtual addressing, each byte of main In a system based on virtual addressing, each byte of main memory has a physical address memory has a physical address andanda virtual address (or more)a virtual address (or more)815-213, S’08A System Using Physical AddressingUsed by many embedded microcontrollers in devices Used by many embedded microcontrollers in devices like cars, elevators, and digital picture frameslike cars, elevators, and digital picture frames0:1:M -1:Main memoryCPU2:3:4:5:6:7:Physical address(PA)4Data word8:...915-213, S’08A System Using Virtual AddressingOne of the great ideas in computer scienceOne of the great ideas in computer scienceused by all modern desktop and laptop microprocessors...0:1:M-1:Main memoryCPU2:3:4:5:6:7:Virtualaddress(VA)4100Data wordPhysicaladdress(PA)4CPU chipMMUAddresstranslation1015-213, S’08Why Virtual Memory?(1) VM allows efficient use of limited main memory (RAM) Use RAM as a cache for the parts of a virtual address space some non-cached parts stored on disk some (unallocated) non-cached parts stored nowhere Keep only active areas of virtual address space in memory transfer data back and forth as needed(2) VM simplifies memory management for programmers Each process gets a full, private linear address space(3) VM isolates address spaces One process can’t interfere with another’s memory because they operate in different address spaces User process cannot access privileged information different sections of address spaces have different permissions1115-213, S’08(1) VM as a Tool for CachingVirtual memory Virtual memory is an array of N contiguous bytesis an array of N contiguous bytesthink of the array as being stored on diskThe contents of the array on disk are cached in The contents of the array on disk are cached in physical memory (DRAM cache)physical memory (DRAM cache)PP 2m-p-1Physical memoryEmptyEmptyUncachedVP 0VP 1VP 2n-p-1Virtual memoryUnallocatedCachedUncachedUnallocatedCachedUncachedPP 0PP 1EmptyCached0N-1M-10Virtual pages (VP's) stored on diskPhysical pages (PP's) cached in DRAM1215-213, S’08DRAM Cache OrganizationDRAM cache organization driven by the enormous DRAM cache organization driven by the enormous miss penaltymiss penalty DRAM is about 10x slower than SRAM Disk is about 100,000x slower than a DRAM to get first byte, though fast for next byteDRAM cache propertiesDRAM cache properties Large page (block) size (typically 4-8 KB) Fully associative Any virtual page can be placed in any physical page Requires a “large” mapping function – different from CPU caches Highly sophisticated replacement algorithms Too complicated and open-ended to be implemented in hardware Write-back rather than write-through1315-213, S’08Reminder: MMU checks the cacheOne of the great ideas in computer scienceOne of the great ideas in computer scienceused by all modern desktop and laptop microprocessorsMMUPhysicaladdress(PA)...0:1:M-1:Main
View Full Document