Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Virtual MemoryMarch 18, 2007TopicsAddress spacesMotivations for virtual memoryAddress translationAccelerating translation with TLBsclass16.ppt15-213“The course that gives CMU its Zip!”215-213, S’08All About MemoryHow memory worksHow memory worksCapacitors, magnetic domainsRow address, column address, row buffer, supercellWe covered this back in mid-FebruaryWhat memory What memory doesdoes Store stuff!More formallyfetch: address ⇒ datastore: address, data ⇒ . The world is imperfect, so...fetch: address ⇒ {data ∪☹ }store: address, data ⇒ { . ∪ ☹ }315-213, S’08ComplaintsThis kind of memory has problemsThis kind of memory has problemsIt has finite sizeA single program might need more memory than is availableEach system has only one memoryIf we will run multiple programs, each program needs a simple way to know which memory it should useProgrammer A doesn't want mistakes made by Programmer B to inflict un-debuggable random crashes on herWe need a way to stop programs from accidentally using the wrong memoryBut it's the only kind of memory we haveBut it's the only kind of memory we have415-213, S’08Happiness via MathematicsOne simple trick solves all three problemsOne simple trick solves all three problemsImagine per-process private memoriesprocess-id ⇒ fetch: (address ⇒ data)process-id ⇒ store: (address, data ⇒ . )This would fix “how to share” and “don't use the wrong memory”Surprisingly, it also fixes “finite size”Implementation is a little differentprocess-id ⇒ map: (process-address ⇒ {physical-address ∪ ☹ })mfetch: fetch(map(address)) ⇒ {data ∪ ☹ }mstore: store(map(address), data) ⇒ { . ∪ ☹ }This mapping trick is the heart of This mapping trick is the heart of virtual memoryvirtual memory515-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).615-213, S’08A System Using Physical AddressingUsed by many digital signal processors and Used by many digital signal processors and embedded microcontrollers in devices like phones embedded microcontrollers in devices like phones and PDAs.and PDAs.0:1:M -1:Main memoryPhysical address(PA)CPU2:3:4:5:6:7:4Data word8:...715-213, S’08A System Using Virtual AddressingOne of the great ideas in computer science. Used by One of the great ideas in computer science. Used by all modern desktop and laptop microprocessors.all modern desktop and laptop microprocessors.MMUPhysicaladdress(PA)...0:1:M-1:Main memoryVirtualaddress(VA)CPU2:3:4:5:6:7:4100Data word4CPU chipAddresstranslation815-213, S’08Why 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 memoryTransfer data back and forth as needed.(2) VM simplifies memory management Each process gets the same linear address space.(3) VM protects address spacesOne 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.915-213, S’08(1) VM as a Tool for CachingVirtual memory Virtual memory is an array of N contiguous bytes is an array of N contiguous bytes stored on disk. stored on disk. The 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 CachedUncachedPP 0PP 1EmptyCached0N-1M-10Virtual pages (VP's) stored on diskPhysical pages (PP's) cached in DRAM1015-213, S’08DRAM Cache OrganizationDRAM cache organization driven by the enormous DRAM cache organization driven by the enormous miss penaltymiss penaltyDRAM is about 10x slower than SRAMDisk is about 100,000x slower than a DRAMDRAM cache propertiesDRAM cache propertiesLarge page (block) size (typically 4-8 KB)Fully associative Any virtual page can be placed in any physical pageThis requires a “large” mapping function – different from other cachesHighly sophisticated replacement algorithmsToo complicated and open-ended to be implemented in hardwareWrite-back rather than write-through1115-213, S’08Page TablesA A page table page table is an array of page table entries (PTEs) is an array of page table entries (PTEs) that maps virtual pages to physical pages.that maps virtual pages to physical pages.Kernel data structure in DRAMnullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 31215-213, S’08Page HitsA A page hitpage hit is a reference to a VM word that is in is a reference to a VM word that is in physical (main) memory.physical (main) memory.nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7Virtual addressVP 31315-213, S’08Page FaultsA A page faultpage fault is caused by a reference to a VM word that is not in is caused by a reference to a VM word that is not in physical (main) memory. physical (main) memory.
View Full Document