Virtual Memory Announcements TA Swap Tyler Steele is a 415 TA Rohit Doshi is a 414 TA My office hours today 3 25 4 25 2 Review Memory Hierarchy of a Modern Computer System Take advantage of the principle of locality to Present as much memory as in the cheapest technology Provide access at speed offered by the fastest technology Processor Control On Chip Cache Registers Datapath Second Level Cache SRAM Speed ns 1s 10s 100s Size bytes 100s Ks Ms Main Memory DRAM 100s Ms Secondary Storage Disk Tertiary Storage Tape 10 000 000 10 000 000 000 s s 10s ms 10s sec 3 Gs Ts Review A Summary on Sources of Cache Misses Compulsory cold start first reference to a block Cold fact of life not a whole lot you can do about it Note When running billions of instruction Compulsory Misses are insignificant Capacity Cache cannot contain all blocks access by the program Solution increase cache size Conflict collision Multiple memory locations mapped to same cache location Solutions increase cache size or increase associativity Two others Coherence Invalidation other process e g I O updates memory Policy Due to non optimal replacement policy 4 Review Where does a Block Get Placed in a Cache Example Block 12 placed in 8 block cache 32 Block Address Space Block no Block no 1111111111222222222233 01234567890123456789012345678901 Direct mapped Set associative Fully associative block 12 can go only into block 4 12 mod 8 block 12 can go anywhere in set 0 12 mod 4 block 12 can go anywhere 01234567 Block no 01234567 Set Set Set Set 0 1 2 3 Block no 01234567 5 Review Other Caching Questions What line gets replaced on cache miss Easy for Direct Mapped Only one possibility Set Associative or Fully Associative Random LRU Least Recently Used What happens on a write Write through The information is written to both the cache and to the block in the lower level memory Write back The information is written only to the block in the cache Modified cache block is written to main memory only when it is replaced Question is block clean or dirty 6 Caching Applied to Address Translation CPU Virtual Address TLB Cached Yes No Physical Address e t v l a u S s e R Translate MMU Physical Memory Data Read or Write untranslated Question is one of page locality does it exist Instruction accesses spend a lot of time on the same page since accesses sequential Stack accesses have definite locality of reference Data accesses have less page locality but still some Can we have a TLB hierarchy Sure multiple levels at different sizes speeds 7 What Actually Happens on a TLB Miss Hardware traversed page tables On TLB miss hardware in MMU looks at current page table to fill TLB may walk multiple levels If PTE valid hardware fills TLB and processor never knows If PTE marked as invalid causes Page Fault after which kernel decides what to do afterwards Software traversed Page tables like MIPS On TLB miss processor receives TLB fault Kernel traverses page table to find PTE If PTE valid fills TLB and returns from fault If PTE marked as invalid internally calls Page Fault handler Most chip sets provide hardware traversal Modern operating systems tend to have more TLB faults since they use translation for many things Examples shared segments user level portions of an operating system 8 Goals for Today Virtual memory How does it work Page faults Resuming after page faults When to fetch What to replace Page replacement algorithms FIFO OPT LRU Clock Page Buffering Allocating Pages to processes 9 What is virtual memory Each process has illusion of large address space 232 for 32 bit addressing However physical memory is much smaller How do we give this illusion to multiple processes Virtual Memory some addresses reside in disk page 0 page 1 page 2 page 3 page 4 page N Virtual memory disk page table Physical memory 10 Virtual Memory Separates users logical memory from physical memory Only part of the program needs to be in memory for execution Logical address space can therefore be much larger than physical address space Allows address spaces to be shared by several processes Allows for more efficient process creation 11 Virtual Memory Load entire process in memory swapping run it exit Is slow for big processes Wasteful might not require everything Solutions partial residency Paging only bring in pages not all pages of process Demand paging bring only pages that are required Where to fetch page from Have a contiguous space in disk swap file pagefile sys 12 How does VM work Modify Page Tables with another bit valid If page in memory valid 1 else valid 0 If page is in memory translation works as before If page is not in memory translation causes a page fault 0 32 V 1 1 4183 V 0 2 177 V 1 3 5721 V 0 Page Table Disk Mem 13 Page Faults On a page fault OS finds a free frame or evicts one from memory which one Want knowledge of the future Issues disk request to fetch data for page what to fetch Just the requested page or more Block current process context switch to new process how Process might be executing an instruction When disk completes set valid bit to 1 and current process in ready queue 14 Steps in Handling a Page Fault 15 Resuming after a page fault Should be able to restart the instruction For RISC processors this is simple Instructions are idempotent until references are done More complicated for CISC E g move 256 bytes from one location to another Possible Solutions Ensure pages are in memory before the instruction executes 16 Page Fault Cont Restart instruction block move auto increment decrement location 17 When to fetch Just before the page is used Need to know the future Demand paging Fetch a page when it faults Prepaging Get the page on fault some of its neighbors or Get all pages in use last time process was swapped 18 Performance of Demand Paging Page Fault Rate 0 p 1 0 if p 0 no page faults if p 1 every reference is a fault Effective Access Time EAT EAT 1 p x memory access p page fault overhead swap page out swap page in restart overhead 19 Demand Paging Example Memory access time 200 nanoseconds Average page fault service time 8 milliseconds EAT 1 p x 200 p 8 milliseconds 1 p x 200 p x 8 000 000 200 p x 7 999 800 If one access out of 1 000 causes a page fault EAT 8 2 microseconds This is a slowdown by a factor of 40 20 What to replace What happens if there is no free frame find some page in memory but not really in use swap it out Page Replacement When process has used up all frames it is allowed to use OS must select a page to eject from
View Full Document
Unlocking...