CS 152 Computer Architecture and Engineering Lecture 10 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 2010 CS152 Spring 2010 Last time in Lecture 9 Protection and translation required for multiprogramming Base and bounds 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 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 February 23 2010 CS152 Springmain 2010 memory 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 2010 VA mapping TLB CS152 Spring 2010 Hierarchical Page Table Virtual Address 31 22 21 p1 0 12 11 p2 offset 10 bit 10 bit L1 index L2 index Root of the Current Page Table offset 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 2010 CS152 Spring 2010 Data Pages PA Address Translation Protection Virtual Address Virtual Page No VPN offset Kernel User Mode Read Write Protection Check Exception Physical Address Address Translation Physical Page No PPN offset Every instruction and data access needs address translation and protection checks A good VM design needs to be fast one cycle and space efficient February 23 2010 CS152 Spring 2010 Translation Lookaside Buffers Address translation is very expensive In a two level page table each reference becomes several memory accesses Solution Cache translations in TLB TLB hit TLB miss Single Cycle Translation Page Table Walk to refill virtual address VRWD tag PPN VPN offset VPN virtual page number PPN physical page number hit February 23 2010 physical address CS152 Spring 2010 PPN offset Handling a TLB Miss Software MIPS Alpha TLB miss causes an exception and the operating system walks the page tables and reloads TLB A privileged untranslated addressing mode used for walk Hardware SPARC v8 x86 PowerPC A memory management unit MMU walks the page tables and reloads the TLB If a missing data or PT page is encountered during the TLB reloading MMU gives up and signals a Page Fault exception for the original instruction February 23 2010 CS152 Spring 2010 Translation for Page Tables Can references to page tables cause TLB misses Can this go on forever User PTE Base System PTE Base February 23 2010 User Page Table in virtual space System Page Table in physical space Data Pages CS152 Spring 2010 Variable Sized Page Support Virtual Address 31 22 21 p1 0 12 11 p2 offset 10 bit 10 bit L1 index L2 index Root of the Current Page Table offset p2 p1 Processor Register Level 1 Page Table Level 2 Page Tables page in primary memory large page in primary memory page in secondary memory PTE of a nonexistent page February 23 2010 CS152 Spring 2010 Data Pages Variable Size Page TLB Some systems support multiple page sizes virtual address V R WD Tag PPN VPN offset PPN offset L hit physical address February 23 2010 CS152 Spring 2010 Address Translation putting it all together Virtual Address Restart instruction hardware hardware or software software TLB Lookup miss hit Page Table Walk Protection Check the page is memory memory Page Fault OS loads page denied permitted Protection Fault Update TLB Physical Address to cache SEGFAULT February 23 2010 CS152 Spring 2010 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 Software handlers need restartable exception on page fault or protection violation Handling a TLB miss needs a hardware or software mechanism to refill TLB Need mechanisms to cope with the additional latency of a TLB slow down the clock pipeline the TLB and cache access virtual address caches 2010 parallel TLB cache CS152 accessSpring 2010 February 23 Virtual Address Caches CPU VA PA Physical Cache TLB Primary Memory Alternative place the cache before the TLB VA CPU Virtual Cache TLB PA Primary StrongARM Memory 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 2010 CS152 Spring 2010 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 Disallow aliases to coexist 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 2010 CS152 Spring 2010 CS152 Administrivia Quiz 2 Tuesday March 3 Covers Lectures 6 8 PS2 and Lab 2 February 23 2010 CS152 Spring 2010 Concurrent Access to TLB Cache VA VPN L TLB PA PPN b k Page Offset Tag hit Virtual Index Direct map Cache 2L blocks b 2 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 2010 CS152 Spring 2010 Virtual Index Physical Tag Caches Associative Organization VA VPN a L k b TLB PA Direct map 2L blocks k PPN Virtual Index 2a b 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 2010 CS152 Spring 2010 Concurrent Access to TLB Large L1 The problem with
View Full Document
Unlocking...