Virtual MemoryOctober 25, 2006Virtual MemoryOctober 25, 2006Topics Address spaces Motivations for virtual memory Address translation Accelerating translation with TLBsclass16.ppt15-213“The course that gives CMU its Zip!”–2–15-213, F’06A 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 microcontrollers in devices like phones and PDAsPDAs..0:1:M -1:Main memoryPhysical address(PA)CPU2:3:4:5:6:7:4Data word8:...–3–15-213, F’06A 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’06Address SpacesAddress 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 virtual address memory has a virtual address andanda physical address.a physical address.–5–15-213, F’06Why 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 memory Transfer data back and forth as needed.(2) VM simplifies memory management Each process gets the same linear address space.(3) VM protects address spaces One process can’t interfere with another.z Because they operate in different address spaces. User process cannot access privileged informationz Different sections of address spaces have different permissions.–6–15-213, F’06(1) VM as a Tool for Caching(1) VM as a Tool for CachingVirtual memory Virtual memory is an array of N contiguous bytes stored is an array of N contiguous bytes stored on disk. 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 memoryUnallocatedCachedUncachedUnallocatedCachedUncachedPP 0PP 1EmptyCached0N-1M-10Virtual pages (VP's) stored on diskPhysical pages (PP's) cached in DRAM–7–15-213, F’06DRAM Cache OrganizationDRAM Cache OrganizationDRAM cache organization driven by the enormous miss DRAM cache organization driven by the enormous miss penaltypenalty DRAM is about 10x slower than SRAM Disk is about 100,000x slower than a DRAMDRAM cache propertiesDRAM cache properties Large page (block) size (typically 4-8 KB) Fully associative z Any virtual page can be placed in any physical page Highly sophisticated replacement algorithms Write-back rather than write-through–8–15-213, F’06Page TablesPage TablesA A page table page table is an array of page table entries (is an array of page table entries (PTEsPTEs) ) 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’06Page HitsPage HitsA A page hitpage hitis 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’06Page FaultsPage FaultsA A page faultpage faultis 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’06Page 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–15-213, F’06Servicing a Page FaultServicing a Page Fault(1) Processor signals controller Read block of length P starting at disk address X and store starting at memory address Y(2) Read occurs Direct Memory Access (DMA) Under control of I/O controller(3) Controller signals completion Interrupt processor OS resumes suspended process diskDiskdiskDiskMemory-I/O busMemory-I/O busProcessorProcessorCacheCacheMemoryMemoryI/OcontrollerI/OcontrollerReg(2) DMA Transfer(1) Initiate Block Read(3) Read Done–13–15-213, F’06Allocating Virtual PagesAllocating Virtual PagesExample: Allocating new virtual page VP5Example: Allocating new virtual page VP5 Kernel allocates VP 5 on disk and points PTE 5 to this new location.nullMemory 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 7VP 3VP 5–14–15-213, F’06Locality to the RescueLocality to the RescueVirtual memory works because of locality.Virtual memory works because of locality.At any point in time, programs
View Full Document