CS 152 Computer Architecture and Engineering Lecture 9 Virtual Memory Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http www eecs berkeley edu krste http inst eecs berkeley edu cs152 February 23 2011 CS152 Spring 2011 Last time in Lecture 9 Protection and translation required for multiprogramming Base and bounds was early simple scheme Page based translation and protection avoids need for memory compaction easy allocation by OS But need to indirect in large page table on every access Address spaces accessed sparsely Can use multi level page table to hold translation protection information but implies multiple memory accesses per reference Address space access with locality Can use translation lookaside buffer TLB to cache address translations sometimes known as address translation cache Still have to walk page tables on TLB miss can be hardware or software talk Virtual memory uses DRAM as a cache of disk memory allows very cheap main memory February 23 2011 CS152 Spring 2011 2 Modern Virtual Memory Systems Illusion of a large private uniform store Protection Privacy OS several users each with their private address space and one or more shared address spaces page table name space Demand Paging Provides the ability to run programs larger than the primary memory useri Primary Memory Swapping Store Hides differences in machine configurations The price is address translation on each memory reference February 23 2011 CS152 Spring 2011 VA mapping PA TLB 3 Hierarchical Page Table Virtual Address 22 21 p1 0 12 11 p2 offset 10 bit 10 bit L1 index L2 index offset Root of the Current Page Table Physical Memory 31 p2 p1 Processor Register Level 1 Page Table page in primary memory page in secondary memory Level 2 Page Tables PTE of a nonexistent page February 23 2011 CS152 Spring 2011 Data Pages 4 Page Based Virtual Memory Machine Hardware Page Table Walk Page Fault Page Fault Protection violation Virtual Physical Address Address PC Inst TLB Inst Cache Protection violation Virtual Physical Address Address D Decode E Data TLB M Data Cache W Miss Miss Page Table Base Register Physical Address Hardware Page Table Walker Memory Controller Physical Address Physical Address Main Memory DRAM Assumes page tables held in untranslated physical memory February 23 2011 CS152 Spring 2011 5 Address Translation putting it all together Virtual Address Restart instruction hardware hardware or software software TLB Lookup miss hit Protection Check Page Table Walk the page is memory memory Page Fault OS loads page Update TLB denied Protection Fault permitted Physical Address to cache SEGFAULT February 23 2011 CS152 Spring 2011 6 Handling VM related exceptions PC Inst TLB Inst Cache TLB miss Page Fault Protection violation D Decode E M Data TLB Data Cache W TLB miss Page Fault Protection violation Handling a TLB miss needs a hardware or software mechanism to refill TLB Handling a page fault e g page is on disk needs a restartable exception so software handler can resume after retrieving page Precise exceptions are easy to restart Can be imprecise but restartable but this complicates OS software Handling protection violation may abort process But often handled the same as a page fault February 23 2011 CS152 Spring 2011 7 Address Translation in CPU Pipeline PC Inst TLB Inst Cache TLB miss Page Fault Protection violation D Decode E M Data TLB Data Cache W TLB miss Page Fault Protection violation Need to cope with additional latency of TLB slow down the clock pipeline the TLB and cache access virtual address caches parallel TLB cache access February 23 2011 CS152 Spring 2011 8 Virtual Address Caches PA CPU VA TLB Physical Cache Primary Memory Alternative place the cache before the TLB VA CPU Virtual Cache TLB PA Primary Memory StrongARM one step process in case of a hit cache needs to be flushed on a context switch unless address space identifiers ASIDs included in tags aliasing problems due to the sharing of pages maintaining cache coherence see later in course February 23 2011 CS152 Spring 2011 9 Virtually Addressed Cache Virtual Index Virtual Tag Virtual Address Virtual Address PC Inst Cache Miss D Decode E M Data Cache W Miss Inst TLB Page Table Base Register Hardware Page Table Walker Physical Address Instruction data Memory Controller Data TLB Physical Address Physical Address Main Memory DRAM Translate on miss February 23 2011 CS152 Spring 2011 10 Aliasing in Virtual Address Caches VA1 Page Table Data Pages PA VA2 Two virtual pages share one physical page Tag Data VA1 1st Copy of Data at PA VA2 2nd Copy of Data at PA Virtual cache can have two copies of same physical data Writes to one copy not visible to reads of other General Solution Prevent aliases coexisting in cache Software i e OS solution for direct mapped cache VAs of shared pages must agree in cache index bits this ensures all VAs accessing same PA will conflict in directmapped cache early SPARCs February 23 2011 CS152 Spring 2011 11 CS152 Administrivia February 23 2011 CS152 Spring 2011 12 Quiz Results February 23 2011 CS152 Spring 2011 13 Quiz Results February 23 2011 CS152 Spring 2011 14 Quiz Results February 23 2011 CS152 Spring 2011 15 Quiz Results February 23 2011 CS152 Spring 2011 16 Concurrent Access to TLB Cache Virtual Index Physical Tag VA VPN L TLB PA PPN b k Page Offset Tag hit Virtual Index Direct map Cache 2L blocks 2b byte block Physical Tag Data Index L is available without consulting the TLB cache and TLB accesses can begin simultaneously Tag comparison is made after both accesses are completed Cases L b k L b k L b k February 23 2011 CS152 Spring 2011 17 Virtual Index Physical Tag Caches Associative Organization VA VPN TLB PA PPN a L k b k Virtual Index 2a b Direct map 2L blocks Direct map 2L blocks Phy Tag Page Offset Tag hit 2a Data After the PPN is known 2a physical tags are compared How does this scheme scale to larger caches February 23 2011 CS152 Spring 2011 18 Concurrent Access to TLB Large L1 The problem with L1 Page size Virtual Index VA VPN a Page Offset TLB PA PPN Page Offset L1 PA cache Direct map b VA1 PPNa Data VA2 PPNa Data hit b Tag Can VA1 and VA2 both map to PA February 23 2011 CS152 Spring 2011 19 A solution via Second Level Cache L1 Instruction Cache CPU RF Memory Unified L2 Cache L1 Data Cache Memory Memory Memory Usually a common L2 cache backs up both Instruction and Data L1 caches L2 is inclusive of both Instruction and Data caches Inclusive means L2 has
View Full Document
Unlocking...