学年计算机方向课程大二上ics课件20-vm concepts

1、Virtual Memory: ConceptsIntroduction to Computer Systems20th Lecture, Nov. 28, 2013Instructors: Xiangqun Chen，Junlin LuGuangyu Sun，Xuetao GuanTodayAddress spacesVM as a tool for cachingVM as a tool for memory managementVM as a tool for memory protectionAddress translationA System Using Physical Addr

2、essingUsed in “simple” systems like embedded microcontrollers in devices like cars, elevators, and digital picture frames0:1:M-1:Main memoryCPU2:3:4:5:6:7:Physical address(PA)Data word8:.4A System Using Virtual AddressingUsed in all modern servers, desktops, and laptopsOne of the great ideas in comp

3、uter science0:1:M-1:Main memoryMMU2:3:4:5:6:7:Physical address(PA)Data word8:.CPUVirtual address(VA)CPU Chip44100Address SpacesLinear address space: Ordered set of contiguous non-negative integer addresses:0, 1, 2, 3 Virtual address space: Set of N = 2n virtual addresses0, 1, 2, 3, , N-1Physical add

4、ress space: Set of M = 2m physical addresses0, 1, 2, 3, , M-1Clean distinction between data (bytes) and their attributes (addresses)Each object can now have multiple addressesEvery byte in main memory: one physical address, one (or more) virtual addressesWhy Virtual Memory (VM)?Uses main memory effi

5、cientlyUse DRAM as a cache for the parts of a virtual address spaceSimplifies memory managementEach process gets the same uniform linear address spaceIsolates address spacesOne process cant interfere with anothers memoryUser program cannot access privileged kernel informationTodayAddress spacesVM as

6、 a tool for cachingVM as a tool for memory managementVM as a tool for memory protectionAddress translationVM as a Tool for CachingVirtual memory is an array of N contiguous bytes stored on disk. The contents of the array on disk are cached in physical memory (DRAM cache)These cache blocks are called

7、 pages (size is P = 2p bytes)PP 2m-p-1Physical memoryEmptyEmptyUncachedVP 0VP 1VP 2n-p-1Virtual memoryUnallocatedCachedUncachedUnallocatedCachedUncachedPP 0PP 1EmptyCached0N-1M-10Virtual pages (VPs) stored on diskPhysical pages (PPs) cached in DRAMDRAM Cache OrganizationDRAM cache organization drive

8、n by the enormous miss penaltyDRAM is about 10 x slower than SRAMDisk is about 10,000 x slower than DRAMConsequencesLarge page (block) size: typically 4-8 KB, sometimes 4 MBFully associative Any VP can be placed in any PPRequires a “large” mapping function different from CPU cachesHighly sophisticat

9、ed, expensive replacement algorithmsToo complicated and open-ended to be implemented in hardwareWrite-back rather than write-throughPage TablesA page table is an array of page table entries (PTEs) that maps virtual pages to physical pages. Per-process kernel data structure in DRAMnullnullMemory resi

10、dentpage 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 3Page HitPage hit: reference to VM word that is in physical memory (DRAM cache hit)nullnullMemory residentpage table(DRAM)Physical mem

11、ory(DRAM)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressPage FaultPage fault: reference to VM word that is not in physical memory (DRAM cache miss)nullnullMemory residentpage table(DRAM)Physical memory(DRAM

12、)VP 7VP 4Virtual memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressHandling Page FaultPage miss causes page fault (an exception)nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtual memory(disk)Valid0101

13、0101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressHandling Page FaultPage miss causes page fault (an exception)Page fault handler selects a victim to be evicted (here VP 4)nullnullMemory residentpage table(DRAM)Physical memory(DRAM)VP 7VP 4Virtua

14、l memory(disk)Valid01010101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressHandling Page FaultPage miss causes page fault (an exception)Page fault handler selects a victim to be evicted (here VP 4)nullnullMemory residentpage table(DRAM)Physical mem

15、ory(DRAM)VP 7VP 3Virtual memory(disk)Valid01100101Physical pagenumber or disk addressPTE 0PTE 7PP 0VP 2VP 1PP 3VP 1VP 2VP 4VP 6VP 7VP 3Virtual addressHandling Page FaultPage miss causes page fault (an exception)Page fault handler selects a victim to be evicted (here VP 4)Offending instruction is res

16、tarted: page hit!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 7VP 3Virtual addressLocality to the Rescue Again!Virtual memory works because of localityAt any point

17、in time, programs tend to access a set of active virtual pages called the working setPrograms with better temporal locality will have smaller working setsIf (working set size main memory size ) Thrashing: Performance meltdown where pages are swapped (copied) in and out continuouslyTodayAddress space

18、sVM as a tool for cachingVM as a tool for memory managementVM as a tool for memory protectionAddress translationVM as a Tool for Memory ManagementKey idea: each process has its own virtual address spaceIt can view memory as a simple linear arrayMapping function scatters addresses through physical me

19、moryWell chosen mappings simplify memory allocation and managementVirtual Address Space for Process 1:Physical Address Space (DRAM)0N-1(e.g., read-only library code)Virtual Address Space for Process 2:VP 1VP 2.0N-1VP 1VP 2.PP 2PP 6PP 8.0M-1Address translationVM as a Tool for Memory ManagementMemory

20、allocationEach virtual page can be mapped to any physical pageA virtual page can be stored in different physical pages at different timesSharing code and data among processesMap virtual pages to the same physical page (here: PP 6)Virtual Address Space for Process 1:Physical Address Space (DRAM)0N-1(

21、e.g., read-only library code)Virtual Address Space for Process 2:VP 1VP 2.0N-1VP 1VP 2.PP 2PP 6PP 8.0M-1Address translationSimplifying Linking and LoadingLinking Each program has similar virtual address spaceCode, stack, and shared libraries always start at the same addressLoading execve() allocates

22、 virtual pages for .text and .data sections = creates PTEs marked as invalidThe .text and .data sections are copied, page by page, on demand by the virtual memory systemKernel virtual memoryMemory-mapped region forshared librariesRun-time heap(created by malloc)User stack(created at runtime)Unused0%

23、esp (stack pointer)Memoryinvisible touser codebrk0 xc00000000 x080480000 x40000000Read/write segment(.data, .bss)Read-only segment(.init, .text, .rodata)Loaded from the executable fileTodayAddress spacesVM as a tool for cachingVM as a tool for memory managementVM as a tool for memory protectionAddre

24、ss translationVM as a Tool for Memory ProtectionExtend PTEs with permission bitsPage fault handler checks these before remappingIf violated, send process SIGSEGV (segmentation fault)Process i:AddressREADWRITEPP 6YesNoPP 4YesYesPP 2YesVP 0:VP 1:VP 2:Process j:YesSUPNoNoYesAddressREADWRITEPP 9YesNoPP

25、6YesYesPP 11YesYesSUPNoYesNoVP 0:VP 1:VP 2:Physical Address SpacePP 2PP 4PP 6PP 8PP 9PP 11TodayAddress spacesVM as a tool for cachingVM as a tool for memory managementVM as a tool for memory protectionAddress translationVM Address TranslationVirtual Address SpaceV = 0, 1, , N1Physical Address SpaceP

26、 = 0, 1, , M1Address TranslationMAP: V P U For virtual address a:MAP(a) = a if data at virtual address a is at physical address a in PMAP(a) = if data at virtual address a is not in physical memoryEither invalid or stored on diskSummary of Address Translation SymbolsBasic ParametersN = 2n : Number o

27、f addresses in virtual address spaceM = 2m : Number of addresses in physical address spaceP = 2p : Page size (bytes)Components of the virtual address (VA)TLBI: TLB indexTLBT: TLB tagVPO: Virtual page offset VPN: Virtual page number Components of the physical address (PA)PPO: Physical page offset (sa

28、me as VPO)PPN: Physical page numberCO: Byte offset within cache lineCI: Cache indexCT: Cache tagAddress Translation With a Page TableVirtual page number (VPN)Virtual page offset (VPO)Physical page number (PPN)Physical page offset (PPO)Virtual addressPhysical addressValidPhysical page number (PPN)Pag

29、e table base register(PTBR)Page table Page table address for processValid bit = 0:page not in memory(page fault)0p-1pn-10p-1pm-1Address Translation: Page Hit1) Processor sends virtual address to MMU 2-3) MMU fetches PTE from page table in memory4) MMU sends physical address to cache/memory5) Cache/m

30、emory sends data word to processorMMUCache/MemoryPADataCPUVACPU ChipPTEAPTE12345Address Translation: Page Fault1) Processor sends virtual address to MMU 2-3) MMU fetches PTE from page table in memory4) Valid bit is zero, so MMU triggers page fault exception5) Handler identifies victim (and, if dirty

31、, pages it out to disk)6) Handler pages in new page and updates PTE in memory7) Handler returns to original process, restarting faulting instructionMMUCache/MemoryCPUVACPU ChipPTEAPTE12345DiskPage fault handlerVictim pageNew pageException67Integrating VM and CacheVACPUMMUPTEAPTEPADataMemoryPAPAmissP

32、TEAPTEAmissPTEA hitPA hitDataPTEL1cacheCPU ChipVA: virtual address, PA: physical address, PTE: page table entry, PTEA = PTE addressSpeeding up Translation with a TLBPage table entries (PTEs) are cached in L1 like any other memory wordPTEs may be evicted by other data referencesPTE hit still requires

33、 a small L1 delaySolution: Translation Lookaside Buffer (TLB)Small hardware cache in MMUMaps virtual page numbers to physical page numbersContains complete page table entries for small number of pagesTLB HitMMUCache/MemoryPADataCPUVACPU ChipPTE1245A TLB hit eliminates a memory accessTLBVPN3TLB MissMMUCache/MemoryPADataCPUVACPU ChipPTE1256TLBVPN4PTEA3A TLB miss incurs an additional memory access (the PTE)Fortunately, TLB misses are rare. Why?Multi-Level Page TablesSuppose:4KB (212) page size, 48-bit address space, 8-byte PTE Problem:Would ne