CS 152 Computer Architecture and Engineering Lecture 11 Virtual Memory and Caches Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http www eecs berkeley edu krste http inst eecs berkeley edu cs152 Today is a review of last two lectures Translation Protection Virtual Memory This is complex material often takes several passes before the concepts sink in Try to take a different path through concepts today 3 5 2009 CS152 Spring 09 2 VM features track historical uses Bare machine only physical addresses One program owned entire machine Batch style multiprogramming Several programs sharing CPU while waiting for I O Base bound translation and protection between programs not virtual memory Problem with external fragmentation holes in memory needed occasional memory defragmentation as new jobs arrived Time sharing More interactive programs waiting for user Also more jobs second Motivated move to fixed size page translation and protection no external fragmentation but now internal fragmentation wasted bytes in page Motivated adoption of virtual memory to allow more jobs to share limited physical memory resources while holding working set in memory Virtual Machine Monitors Run multiple operating systems on one machine Idea from 1970s IBM mainframes now common on laptops e g run Windows XP on top of Mac OS X Hardware support for two levels of translation protection Guest OS virtual Guest OS physical Host machine physical 3 5 2009 3 CS152 Spring 09 Bare Machine PC Physical Address Inst Cache Physical Address D Decode E M Physical Address Data Cache Memory Controller W Physical Address Physical Address Main Memory DRAM In a bare machine the only kind of address is a physical address 3 5 2009 CS152 Spring 09 4 Data Bound Register Mem Address Logical Register Address Load X Program Address Space Bounds Violation Data Base Register Physical Address Program Bound Register Bounds Violation Program Counter Logical Address Program Base Register data segment program segment Physical Address Logical address is what user software sees Translated to physical address by adding base register 3 5 2009 5 CS152 Spring 09 Base and Bound Machine Prog Bound Register Logical Address PC Data Bound Register Bounds Violation Inst Cache D Logical Address Decode E M Physical Address Program Base Register Bounds Violation Data Cache W Physical Address Physical Address Data Base Register Memory Controller Physical Address Physical Address Main Memory DRAM Can fold addition of base register into base offset calculation using a carry save adder sum three numbers with only a few gate delays more than adding two numbers 3 5 2009 CS152 Spring 09 6 Main Memory Base and Bound Scheme Memory Fragmentation OS Space Users 4 5 arrive OS Space free Users 2 5 leave OS Space user 1 16K user 1 16K user 2 24K user 2 user 4 24K 16K 8K user 4 32K user 3 32K 16K 8K user 3 32K 24K user 5 24K 24K user 3 user 1 16K 24K 24K As users come and go the storage is fragmented Therefore at some stage programs have to be moved around to compact the storage 3 5 2009 7 CS152 Spring 09 Paged Memory Systems Processor generated address can be interpreted as a pair page number offset page number offset A page table contains the physical address of the base of each page 0 1 2 3 Address Space of User 1 1 0 0 1 2 3 3 Page Table of User 1 2 Page tables make it possible to store the pages of a program non contiguously 3 5 2009 CS152 Spring 09 8 Private Address Space per User VA1 Physical Memory User 1 Page Table User 2 OS pages VA1 Page Table User 3 VA1 Page Table free Each user has a page table Page table contains an entry for each user page 3 5 2009 9 CS152 Spring 09 Linear Page Table Page Table Entry PTE contains A bit to indicate if a page exists PPN physical page number for a memory resident page DPN disk page number for a page on the disk Status bits for protection and usage OS sets the Page Table Base Register whenever active user process changes PT Base Register 3 5 2009 Data Pages Page Table CS152 Spring 09 PPN PPN DPN PPN Data word Offset DPN PPN PPN DPN DPN VPN DPN PPN PPN VPN Offset Virtual address 10 Page Tables in Physical Memory PT User 1 VA1 PT User 2 User 1 VA1 User 2 3 5 2009 CS152 Spring 09 11 Size of Linear Page Table With 32 bit addresses 4 KB pages 4 byte PTEs 220 PTEs i e 4 MB page table per user 4 GB of swap needed to back up full virtual address space Larger pages Internal fragmentation Not all memory in a page is used Larger page fault penalty more time to read from disk What about 64 bit virtual address space Even 1MB pages would require 244 8 byte PTEs 35 TB What is the saving grace sparsity of virtual address usage 3 5 2009 CS152 Spring 09 12 Hierarchical Two Level Page Table Virtual Address 31 22 21 p1 0 12 11 p2 offset 10 bit 10 bit L1 index L2 index offset Root of the Current Page Table 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 3 5 2009 Data Pages CS152 Spring 09 13 Two Level Page Tables in Physical Memory Physical Virtual Address Spaces Memory Level 1 PT User 1 VA1 Level 1 PT User 2 User 1 User2 VA1 User1 VA1 VA1 User 2 Level 2 PT User 2 3 5 2009 CS152 Spring 09 14 Address Translation Protection Virtual Address Virtual Page No VPN offset Kernel User Mode Read Write Protection Check Address Translation Exception Physical Address 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 3 5 2009 15 CS152 Spring 09 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 3 5 2009 physical address CS152 Spring 09 PPN offset 16 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 an exception for the original instruction 3 5 2009 17 CS152 Spring 09 Demand Paged Memory Machine
View Full Document
Unlocking...