CS152 Computer Architecture and Engineering Lecture 23 Virtual Memory cont Buses and I O 1 November 21st 2001 John Kubiatowicz http cs berkeley edu kubitron lecture slides http www inst eecs berkeley edu cs152 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Recall Levels of the Memory Hierarchy Capacity Access Time Cost Staging Xfer Unit CPU Registers 100s Bytes 10s ns Registers Cache K Bytes 10 100 ns 01 001 bit Cache Instr Operands Blocks Main Memory M Bytes 100ns 1us 01 001 Memory Disk G Bytes ms 4 3 10 10 cents Disk Tape infinite sec min 10 6 11 21 01 Upper Level faster prog compiler 1 8 bytes cache cntl 8 128 bytes Pages OS 512 4K bytes Files user operator Mbytes Tape UCB Fall 2001 Larger Lower Level CS152 Kubiatowicz Recall What is virtual memory Virtual Physical Address Space Address Space Virtual Address 10 offset V page no Page Table Base Reg index into page table Page Table V Access Rights PA table located in physical P page no memory offset 10 Physical Address 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 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Recall Three Advantages of Virtual Memory Translation 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 Protection 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 Shared memory 11 21 01 UCB Fall 2001 CS152 Kubiatowicz 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 TAGS 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 Tag and Comparator One Cache line of Data To Next Lower Level In Hierarchy 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Recall Large Address Spaces Hierarchical PT Two level Page Tables 1K PTEs 32 bit address 10 P1 index 10 P2 index 4KB 12 page offest 4 bytes 2 GB virtual address space 4 MB of PTE2 paged holes 4 KB of PTE1 4 bytes What about a 48 64 bit address space 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Recall Inverted Page Tables IBM System 38 AS400 implements 64 bit addresses 48 bits translated start of object contains a 12 bit tag Virtual Page hash V Page P Frame TLBs or virtually addressed caches are critical 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Virtual Address and a Cache Step backward VA 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 11 21 01 UCB Fall 2001 CS152 Kubiatowicz 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 Virtual Address Space Physical Memory Space page off Page Table 2 0 1 3 TLB physical address page off frame page 2 2 0 5 11 21 01 UCB Fall 2001 CS152 Kubiatowicz TLB organization include protection Virtual Address Physical Address Dirty Ref Valid Access ASID 0xFA00 0x0040 0x0041 0x0003 0x0010 0x0011 Y N N N Y Y Y Y Y R W R R 34 0 0 TLB usually organized as fully associative cache Lookup is by Virtual Address Returns Physical Address other info 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 UCB Fall 2001 CS152 Kubiatowicz 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 WB D Cache TLB 64 entry on chip fully associative software TLB fault handler Virtual Address Space ASID 6 V Page Number 20 Offset 12 0xx User segment caching based on PT TLB entry 100 Kernel physical space cached 101 Kernel physical space uncached 11x Kernel virtual space Allows context switching among 64 user processes without TLB flush 11 21 01 UCB Fall 2001 CS152 Kubiatowicz What is the replacement policy for TLBs On a TLB miss we check the page table for an entry Two architectural possibilities Hardware table walk Sparc among others Structure of page table must be known to hardware Software table walk MIPS was one of the first Lots of flexibility Can be expensive with modern operating systems What if missing Entry is not in page table This is called a Page Fault requested virtual page is not in memory Operating system must take over CS162 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 The root of the page table always pegged in memory 11 21 01 UCB Fall 2001 CS152 Kubiatowicz Page Replacement Not Recently Used 1 bit LRU Clock Tail pointer Mark pages as not used recently 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 UCB Fall 2001 Free Pages CS152 Kubiatowicz 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 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 page fault handler dirty used 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 size until one with a 0 bit is found this is the target for replacement As a
View Full Document
Unlocking...