Virtual Memory October 14, 2008AnnouncementsByte-Oriented Memory OrganizationSimple Addressing ModesLets think on this: physical memory?So, we add a level of indirectionAddress SpacesA System Using Physical AddressingA System Using Virtual AddressingWhy Virtual Memory?(1) VM as a Tool for CachingDRAM Cache OrganizationReminder: MMU checks the cacheHow? Page TablesAddress Translation with a Page TablePage HitsPage FaultsHandling a Page FaultWhy does it work? Locality(2) VM as a Tool for Memory MgmtSimplifying Sharing and AllocationIA32 Linux Memory LayoutSimplifying Linking and Loading(3)VM as a Tool for Memory ProtectionSlide 25Address Translation: Page HitAddress Translation: Page FaultSpeeding up Translation with a TLBTLB HitTLB MissSimple Memory System ExampleSimple Memory System Page TableSimple Memory System TLBSimple Memory System CacheAddress Translation Example #1Address Translation Example #2Address Translation Example #3SummaryAllocating Virtual PagesMulti-Level Page TablesA Two-Level Page Table HierarchyTranslating with a k-level Page TableServicing a Page FaultVirtual MemoryOctober 14, 2008TopicsAddress spacesMotivations for virtual memoryAddress translationAccelerating translation with TLBslecture-14.ppt15-213“The course that gives CMU its Zip!”215-213, S’08AnnouncementsAutolab outageAutolab outageThe autolab machine was hacked on Saturdaynot the autolab programs, but the underlying OSrebuilt and brought back online MondayShould not block your progress on shelllaball files needed were made available on class website (under docs link)fish machines are working fineRe-submit tshlab, if you finished before the outageas always, there was a time gap between last backup and the breakin315-213, S’08Programs Refer to Virtual Memory AddressesPrograms Refer to Virtual Memory AddressesConceptually very large array of bytesActually implemented with hierarchy of different memory typesSystem provides address space private to particular “process”Program being executedProgram can clobber its own data, but not that of othersCompiler + Run-Time System Control AllocationCompiler + Run-Time System Control AllocationWhere different program objects should be storedAll allocation within single virtual address spaceByte-Oriented Memory Organization• • •00•••0FF•••FFrom class02.ppt415-213, S’08Simple Addressing ModesNormalNormal(R)(R)Mem[Reg[R]]Mem[Reg[R]]Register R specifies memory addressmovl (%ecx),%eaxDisplacementDisplacementD(R)D(R)Mem[Reg[R]+D]Mem[Reg[R]+D]Register R specifies start of memory regionConstant 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) bytes64-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 problemsEach process gets its own private image of memoryappears to be a full-sized private memory rangeThis fixes “how to choose” and “others shouldn’t mess w/yours”surprisingly, it also fixes “making everything fit”Implementation: translate addresses transparentlyadd a mapping functionto map private addresses to physical addressesdo 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 space is a set of N = 2 is a set of N = 2nn virtual addressesvirtual addresses::{0, 1, 2, …, N-1}{0, 1, 2, …, N-1}A A physical address spacephysical address space is a set of M = 2 is a set of M = 2mm (for convenience) (for convenience) physical addressesphysical addresses::{0, 1, 2, …, M-1}{0, 1, 2, …, M-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 andand a 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 spacesome non-cached parts stored on disksome (unallocated) non-cached parts stored nowhereKeep only active areas of virtual address space in memorytransfer data back and forth as needed(2) VM simplifies memory management for programmersEach process gets a full, private linear address space(3) VM isolates address spacesOne process can’t interfere with another’s memorybecause they operate in different address spacesUser process cannot access privileged informationdifferent 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 memoryUnallocated CachedUncachedUnallocated
View Full Document