inst eecs berkeley edu cs61c CS61C Machine Structures Cache design choices Lecture 36 VM II size of cache speed v capacity direct mapped v associative for N way set assoc choice of N block replacement policy 2nd level cache Write through v write back 2004 11 22 Lecturer PSOE Dan Garcia www cs berkeley edu ddgarcia 4 Bears crush Stanford 9th longest In the rivalry in the US we get the most dominant win 41 6 since 1930 JJ Arrington ran for 169yds a school record for a single season and is now the only RB in the US to have run for 100yds in every game this season We now must best Southern Miss on Dec 4 Garcia Fall 2004 U CB Virtual to Physical Addr Translation Program operates in its virtual address space virtual address inst fetch load store HW mapping physical address inst fetch load store Physical memory incl caches Each program operates in its own virtual address space only program running Each is protected from the other OS can decide where each goes in memory Hardware HW provides virtual physical mapping CS61C L36 V M II 3 Garcia Fall 2004 U CB Simple Example Base and Bound Reg User C base bound User B base User A Use performance model to pick between choices depending on programs technology budget Virtual Memory calbears collegesports com sports m footbl recaps 112004aac html CS61C L36 V M II 1 Review Enough space for User D but discontinuous fragmentation problem Want discontinuous mapping Predates caches each process thinks it has all the memory to itself protection CS61C L36 V M II 2 Garcia Fall 2004 U CB Analogy Book title like virtual address Library of Congress call number like physical address Card catalogue like page table mapping from book title to call On card for book in local library vs in another branch like valid bit indicating in main memory vs on disk On card available for 2 hour in library use vs 2 week checkout like access rights CS61C L36 V M II 4 Garcia Fall 2004 U CB Mapping Virtual Memory to Physical Memory Virtual Memory Divide into equal sized chunks about 4 KB 8 KB Stack Any chunk of Virtual Memory assigned to any chuck of Physical Memory page 64 MB Physical Memory Heap Process size mem Static Addition not enough 0 CS61C L36 V M II 5 OS use Indirection Garcia Fall 2004 U CB 0 CS61C L36 V M II 6 Code 0 Garcia Fall 2004 U CB Paging Organization assume 1 KB pages Page is unit Virtual Physical of mapping Address Address 0 page 0 1K page 0 1K 0 page 1 1K 1024 1K Addr 1024 page 1 2048 page 2 1K Trans MAP 7168 page 7 1K Physical 31744 page 31 1K Memory Page also unit of Virtual transfer from disk to physical memory Memory CS61C L36 V M II 7 Garcia Fall 2004 U CB Virtual Memory Mapping Function Cannot have simple function to predict arbitrary mapping Use table lookup of mappings Page Number Offset Use table lookup Page Table for mappings Page number is index Virtual Memory Mapping Function Physical Offset Virtual Offset Physical Page Number PageTable Virtual Page Number P P N also called Page Frame CS61C L36 V M II 8 Garcia Fall 2004 U CB Address Mapping Page Table Page Table Virtual Address page no offset A page table is an operating system structure which contains the mapping of virtual addresses to physical locations Page Table Base Reg index into page table Page Table V A R P P A Val Access Physical id Rights Page Address Physical Memory Address Page Table located in physical memory CS61C L36 V M II 9 Garcia Fall 2004 U CB There are several different ways all up to the operating system to keep this data around Each process running in the operating system has its own page table State of process is PC all registers plus page table OS changes page tables by changing contents of Page Table Base Register CS61C L36 V M II 10 Garcia Fall 2004 U CB Requirements revisited Page Table Entry PTE Format Remember the motivation for VM Contains either Physical Page Number or indication not in Main Memory Sharing memory with protection Different physical pages can be allocated to different processes sharing A process can only touch pages in its own page table protection OS maps to disk if Not Valid V 0 Page Table Separate address spaces Since programs work only with virtual addresses different programs can have different data code at the same address What about the memory hierarchy CS61C L36 V M II 11 Garcia Fall 2004 U CB V A R P P N Val Access Physical id Rights Page Number V A R P P N P T E If valid also check if have permission to use page Access Rights A R may be Read Only Read Write Executable CS61C L36 V M II 12 Garcia Fall 2004 U CB Paging Virtual Memory Multiple Processes User A Virtual Memory User B Virtual Memory Stack Stack Physical Memory 64 MB 0 Code A Page 0 Table Block or Line Page Miss Page Fault Block Size 32 64B Page Size 4K 8KB Heap Static Comparing the 2 levels of hierarchy Cache Version Virtual Memory vers Heap Placement Fully Associative Direct Mapped N way Set Associative Static Replacement LRU or Random B Page Code Table 0 CS61C L36 V M II 13 Garcia Fall 2004 U CB Notes on Page Table Least Recently Used LRU Write Thru or Back Write Back CS61C L36 V M II 14 Garcia Fall 2004 U CB Administrivia Solves Fragmentation problem all chunks same size so all holes can be used OS must reserve Swap Space on disk for each process To grow a process ask Operating System If unused pages OS uses them first If not OS swaps some old pages to disk Least Recently Used to pick pages to swap Each process has own Page Table Will add details but Page Table is essence of Virtual Memory CS61C L36 V M II 15 Garcia Fall 2004 U CB Virtual Memory Problem 1 CS61C L36 V M II 16 Translation Look Aside Buffers TLBs Map every address 1 indirection via Page Table in memory per virtual address 1 virtual memory accesses 2 physical memory accesses SLOW Observation since locality in pages of data there must be locality in virtual address translations of those pages TLBs usually small typically 128 256 entries Like any other cache the TLB can be direct mapped set associative or fully associative VA Processor Since small is fast why not use a small cache of virtual to physical address translations to make translation fast For historical reasons cache is called a Translation Lookaside Buffer or TLB CS61C L36 V M II 17 Garcia Fall 2004 U CB Garcia Fall 2004 U CB hit PA miss TLB Main Cache Lookup Memory miss hit Translation data On TLB miss get page table entry from main memory CS61C L36 V M II 18 Garcia Fall 2004 U CB What if not in TLB Typical …
View Full Document
Unlocking...