inst eecs berkeley edu cs61c Review Caches CS61C Machine Structures Cache design choices Lecture 35 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 Lecturer PSOE Dan Garcia www cs berkeley edu ddgarcia Happy 40th Moore s law Yesterday marked the 40th anniversary of the moment Gordon Moore offered a predication based on trends he d seen about the semiconductor industry It has served as an important yardstick www intel com pressroom kits events moores law 40th www macworld com news 2005 04 19 problem CS61C L35 V M I 1 Garcia U CB Thus far Next Virtual Memory Upper Level Faster L2 Cache Blocks Memory Pages Disk Files Tape CS61C L35 V M I 2 If Principle of Locality allows caches to offer close to speed of cache memory with size of DRAM memory then recursively why not use at next level to give speed of DRAM memory size of Disk memory While we re at it what other things do we need from our memory system Larger Lower Level CS61C L35 V M I 3 Garcia U CB CS61C L35 V M I 4 Memory Hierarchy Requirements Virtual Memory Share memory between multiple processes but still provide protection don t let one program read write memory from another Called Virtual Memory Address space give each program the illusion that it has its own private memory Today more important for protection vs just another level of memory hierarchy Garcia U CB Also allows OS to share memory protect programs from each other Suppose code starts at address 0x40000000 But different processes have different code both residing at the same address So each program has a different view of memory CS61C L35 V M I 5 Garcia U CB Memory Hierarchy Requirements Another View of the Memory Hierarchy Regs Instr Operands Cache Blocks Use performance model to pick between choices depending on programs technology budget Each process thinks it has all the memory to itself Historically it predates caches Garcia U CB CS61C L35 V M I 6 Garcia 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 Analogy 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 L35 V M I 7 Garcia U CB Simple Example Base and Bound Reg User C base bound User B base User A Enough space for User D but discontinuous fragmentation problem Want discontinuous mapping 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 L35 V M I 8 Garcia 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 L35 V M I 9 OS use Indirection Garcia 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 L35 V M I 11 Code 0 Garcia U CB CS61C L35 V M I 10 0 Garcia 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 L35 V M I 12 Garcia 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 Page Table Base Reg V A R P P A Val Access Physical id Rights Page Address Physical Memory Address index into page table 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 Page Table located in physical memory CS61C L35 V M I 13 There are several different ways all up to the operating system to keep this data around Garcia U CB CS61C L35 V M I 14 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 L35 V M I 15 Garcia U CB Paging Virtual Memory Multiple Processes User A Virtual Memory User B Virtual Memory Stack Stack Physical Memory 64 MB Heap Static 0 Garcia U CB Code CS61C L35 V M I 17 A Page 0 Table 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 L35 V M I 16 Garcia U CB Comparing the 2 levels of hierarchy Cache Version Virtual Memory vers Block or Line Page Miss Page Fault Block Size 32 64B Page Size 4K 8KB Heap Placement Fully Associative Direct Mapped N way Set Associative Static Replacement LRU or Random B Page Code Table 0 Least Recently Used LRU Write Thru or Back Write Back Garcia U CB CS61C L35 V M I 18 Garcia U CB Notes on Page Table Administrivia Solves Fragmentation problem all chunks same size so all holes can be used Friday office hours will be moved OS must reserve Swap Space on disk for each process Project is out due next Wednesday Cache simulator with a cool GUI 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
View Full Document
Unlocking...