Virtual Memory October 29, 2007A System Using Physical AddressingA System Using Virtual AddressingAddress SpacesWhy Virtual Memory?(1) VM as a Tool for CachingDRAM Cache OrganizationPage TablesPage HitsPage FaultsPage Faults (cont)Servicing a Page FaultAllocating Virtual PagesLocality to the Rescue(2) VM as a Tool for Memory MgmtSimplifying Sharing and AllocationSimplifying Linking and Loading(3)VM as a Tool for Memory ProtectionVM Address TranslationAddress Translation with a Page TableAddress Translation: Page HitAddress Translation: Page FaultIntegrating VM and CacheSpeeding up Translation with a TLBTLB HitTLB MissSimple Memory System ExampleSimple Memory System Page TableSimple Memory System TLBSimple Memory System CacheAddress Translation Example #1Slide 32Slide 33Slide 34Address Translation Example #2Slide 36Slide 37Address Translation Example #3Multi-Level Page TablesA Two-Level Page Table HierarchyTranslating with a k-level Page TableSummaryVirtual MemoryOctober 29, 2007Virtual MemoryOctober 29, 2007TopicsAddress spacesMotivations for virtual memoryAddress translationAccelerating translation with TLBsclass16.ppt15-21315-213, F’07– 2 –15-213, F’0615-213, F’07A System Using Physical AddressingA System Using Physical AddressingUsed by many digital signal processors and embedded Used by many digital signal processors and embedded microcontrollers in devices like phones and PDAs.microcontrollers in devices like phones and PDAs.0:1:M -1:Main memoryPhysical address(PA)CPU2:3:4:5:6:7:4Data word8:...– 3 –15-213, F’0615-213, F’07A System Using Virtual AddressingA System Using Virtual AddressingOne of the great ideas in computer science. Used by all One of the great ideas in computer science. Used by all modern desktop and laptop microprocessors.modern desktop and laptop microprocessors.MMUPhysicaladdress(PA)...0:1:M-1:Main memoryVirtualaddress(VA)CPU2:3:4:5:6:7:4100Data word4CPU chipAddresstranslation– 4 –15-213, F’0615-213, F’07Address SpacesAddress SpacesA A linear address space linear address space is an ordered set of contiguous nonnegative is an ordered set of contiguous nonnegative integer addresses: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 memory In a system based on virtual addressing, each byte of main memory has a virtual address has a virtual address andand a physical address. a physical address.– 5 –15-213, F’0615-213, F’07Why Virtual Memory?Why 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.– 6 –15-213, F’0615-213, F’07(1) VM as a Tool for Caching(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 physical memory (DRAM cache)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 DRAM– 7 –15-213, F’0615-213, F’07DRAM Cache OrganizationDRAM Cache OrganizationDRAM cache organization driven by the enormous miss DRAM cache organization driven by the enormous miss penaltypenaltyDRAM 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 pageHighly sophisticated replacement algorithmsWrite-back rather than write-through– 8 –15-213, F’0615-213, F’07Page TablesPage 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 3– 9 –15-213, F’0615-213, F’07Page HitsPage 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 3– 10 –15-213, F’0615-213, F’07Page FaultsPage 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. Example: A instruction references a word contained in VP 3, a miss that triggers a page fault exceptionnullnullMemory 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 3– 11 –15-213, F’0615-213, F’07Page Faults (cont)Page Faults (cont)nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 3Virtual memory(disk)Valid01100101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7Virtual addressVP 3The kernel’s page fault handler selects VP 4 as the victim and replaces it with a copy of VP 3 from disk (demand paging)When the offending instruction restarts, it executes normally, without generating an exception..– 12
View Full Document