Recall Levels of the Memory Hierarchy Upper Level Capacity Access Time Cost CS152 Computer Architecture and Engineering Lecture 23 Virtual Memory cont Buses and I O 1 Staging Xfer Unit CPU Registers 100s Bytes 10s ns Registers Cache K Bytes 10 100 ns 01 001 bit Cache Instr Operands Blocks November 21st 2001 John Kubiatowicz http cs berkeley edu kubitron lecture slides http www inst eecs berkeley edu cs152 11 21 01 CS152 Kubiatowicz Lec23 1 UCB Fall 2001 Recall What is virtual memory Virtual Address Space Physical Address Space V Access Rights PA table located in physical P page no memory Virtual memory treat memory as a cache for the disk Terminology blocks in this cache are called Pages Typical size of a page 1K 8K Page table maps virtual page numbers to physical frames PTE Page Table Entry UCB Fall 2001 Disk Tape infinite sec min 10 6 Pages OS 512 4K bytes Files user operator Mbytes Tape 11 21 01 UCB Fall 2001 Larger Lower Level CS152 Kubiatowicz Lec23 2 Protection offset 10 Physical Address 11 21 01 Disk G Bytes ms 4 3 10 10 cents cache cntl 8 128 bytes Program can be given consistent view of memory even though physical memory is scrambled Makes multithreading reasonable now used a lot Only the most important part of program Working Set must be in physical memory Contiguous structures like stacks use only as much physical memory as necessary yet still grow later 10 offset Page Table Page Table Base Reg index into page table Memory prog compiler 1 8 bytes Recall Three Advantages of Virtual Memory Translation Virtual Address V page no Main Memory M Bytes 100ns 1us 01 001 faster CS152 Kubiatowicz Lec23 3 Different threads or processes protected from each other Different pages can be given special behavior Read Only Invisible to user programs etc Kernel data protected from User programs Very important for protection from malicious programs Far more viruses under Microsoft Windows Sharing Can map same physical page to multiple users memory UCB Fall 2001 Shared 11 21 01 CS152 Kubiatowicz Lec23 4 Recall Reducing Misses via a Victim Cache How to combine fast hit time of direct mapped yet still avoid conflict misses Add buffer to place data discarded from cache Jouppi 1990 4 entry victim cache removed 20 to 95 of conflicts for a 4 KB direct mapped data cache Used in Alpha HP machines Recall Large Address Spaces Hierarchical PT Two level Page Tables TAGS DATA 1K PTEs 32 bit address 10 P1 index Tag and Comparator One Cache line of Data Tag and Comparator One Cache line of Data Tag and Comparator One Cache line of Data Tag and Comparator One Cache line of Data 4 MB of PTE2 To Next Lower Level In Hierarchy 4 KB of PTE1 10 P2 index 4KB 12 page offest 4 bytes 2 GB virtual address space paged holes 4 bytes What about a 48 64 bit address space 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Lec23 5 11 21 01 Virtual Address and a Cache Step backward Recall Inverted Page Tables VA IBM System 38 AS400 implements 64 bit addresses 48 bits translated start of object contains a 12 bit tag Virtual Page hash CS152 Kubiatowicz Lec23 6 UCB Fall 2001 V Page P Frame CPU miss PA Translation Cache Main Memory hit data Virtual memory seems to be really slow Must access memory on load store even cache hits Worse if translation not completely in memory may need to go to disk before hitting in cache Solution Caching surprise Keep track of most common translations and place them in a Translation Lookaside Buffer TLB TLBs or virtually addressed caches are critical 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Lec23 7 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Lec23 8 TLB organization include protection Making address translation practical TLB Virtual memory memory acts like a cache for the disk Page table maps virtual page numbers to physical frames Translation Look aside Buffer TLB is a cache translations Virtual Address Physical Address Dirty Ref Valid Access ASID 0xFA00 0x0040 0x0041 virtual address Virtual Address Space page Physical Memory Space 0x0003 0x0010 0x0011 Y N N N Y Y Y Y Y R W R R 34 0 0 off Page Table TLB usually organized as fully associative cache 2 Lookup is by Virtual Address Returns Physical Address other info 0 1 3 physical address page TLB off frame page 2 2 0 5 11 21 01 CS152 Kubiatowicz Lec23 9 UCB Fall 2001 Example R3000 pipeline includes TLB stages MIPS R3000 Pipeline Dcd Reg Inst Fetch TLB I Cache RF ALU E A Memory Operation E A TLB Write Reg Dirty Page modified Y N Ref Page touched Y N Valid TLB entry valid Y N Access Read Write ASID Which User 11 21 01 Hardware table walk Sparc among others WB Virtual Address Space 20 Offset 12 What if missing Entry is not in page table pick a page to discard possibly writing it to disk start loading the page in from disk schedule some other process to run Note possible that parts of page table are not even in memory I e paged out Allows context switching among 64 user processes without TLB flush UCB Fall 2001 Lots of flexibility Can be expensive with modern operating systems This is called a Page Fault requested virtual page is not in memory Operating system must take over CS162 0xx User segment caching based on PT TLB entry 100 Kernel physical space cached 101 Kernel physical space uncached 11x Kernel virtual space 11 21 01 Structure of page table must be known to hardware Software table walk MIPS was one of the first D Cache 64 entry on chip fully associative software TLB fault handler V Page Number CS152 Kubiatowicz Lec23 10 What is the replacement policy for TLBs On a TLB miss we check the page table for an entry Two architectural possibilities TLB ASID 6 UCB Fall 2001 The root of the page table always pegged in memory CS152 Kubiatowicz Lec23 11 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Lec23 12 Page Replacement Not Recently Used 1 bit LRU Clock Page Replacement Not Recently Used 1 bit LRU Clock Associated with each page is a used flag such that used flag 1 if the page has been referenced in recent past 0 otherwise Tail pointer Mark pages as not used recently if replacement is necessary choose any page frame such that its reference bit is 0 This is a page that has not been referenced in the recent past Set of all pages in Memory Freelist Head pointer Place pages on free list if they are still marked as not used Schedule dirty pages for writing to disk 11 21 01 Free Pages CS152 Kubiatowicz Lec23 13 UCB Fall 2001 page table entry 1 1 0 1 0 0 0 1 1 0 page table entry last replaced pointer lrp if replacement is to take place advance lrp to next entry mod table
View Full Document
Unlocking...