Virtual MemoryReviewUseful termsOutline for this topicDemand Paging PerformanceDemand Paging Performance (continued)Performance ExamplePerformance Example (continued)Working Set SizeObject LessonClass DiscussionTLB fault performanceSlide 14TLB fault performance (continued)Summary of this TopicNext topicCaching issuesPhysical Memory is a Cache of Virtual Memory, so …Physical Memory as cache of Virtual MemoryVM Page ReplacementPage Replacement AlgorithmsThe Best Page to ReplacePage Replacement – NRU (Not Recently Used)Page Replacement – FIFO (First In, First Out)FIFO Illustrating Belady’s AnomalySecond ChanceClock Replacement (A slight variation of Second Chance)Clock Algorithm (illustrated)Enhanced Clock AlgorithmLeast Recently Used (LRU)LRULRU ApproximationsWhen to Evict Pages (Cleaning Policy)Slide 35What to Page inWorking SetSlide 38Working Set ExampleWorking Set Page ReplacementWSClock (combines Clock and WS algorithms)Review of Page Replacement AlgorithmsMore on SegmentationOS Design Issue — Where does Kernel execute?Kernel Memory RequirementsKernel Memory AllocationBuddy SystemBuddy System (illustrated)Slab AllocationSlab Allocation (illustrated)Unix VMLinux VMWindows NTVM SummaryReading AssignmentVirtual MemoryCS-502 Fall 2007 1Virtual MemoryCS-502, Operating SystemsFall 2007(Slides include materials from Operating System Concepts, 7th ed., by Silbershatz, Galvin, & Gagne and from Modern Operating Systems, 2nd ed., by Tanenbaum)Virtual MemoryCS-502 Fall 2007 2Review•Virtual Memory — the address space in which a process “thinks”•As distinguished from Physical Memory, the address space of the hardware memory system•Multiple forms •Base and Limit registers•Paging•Memory Management Unit (MMU)•Present in most modern processors•Converts all virtual addresses to physical addresses•Transparent to execution of (almost all) programsVirtual MemoryCS-502 Fall 2007 4Useful terms•Thrashing•Too many page faults per unit time •Results from insufficient physical memory to support the working set•System spends most of its time swapping pages in and out, rather than executing process•Working set•The set of pages needed to keep a process from thrashing•Caching•The art and science of keeping the most active elements in fast storage for better execution speed•Depends upon locality of referencesVirtual MemoryCS-502 Fall 2007 5Outline for this topic•Performance metrics•Swap-in strategies•Page replacement strategies•Miscellaneous topics–More on segmentation–Kernel memory allocation–VM summary: Linux & WindowsVirtual MemoryCS-502 Fall 2007 6Demand Paging Performance•Page Fault Rate (p)0 < p < 1.0 (measured in average number of faults / reference)•Page Fault Overhead= fault service time + read page time + restart process time•Fault service time ~ 0.1–10 sec•Restart process time ~ 0.1–10–100 sec•Read page time ~ 8-20 milliseconds!•Dominated by time to read page in from disk!Virtual MemoryCS-502 Fall 2007 7Demand Paging Performance (continued)•Effective Access Time (EAT)= (1-p) * (memory access time) + p * (page fault overhead)•Want EAT to degrade no more than, say, 10% from true memory access time–i.e., EAT < (1 + 10%) * memory access timeVirtual MemoryCS-502 Fall 2007 8Performance Example•Memory access time = 100 nanosec = 10-7•Page fault overhead = 25 millisec = 0.025•Page fault rate = 1/1000 = 10-3•EAT = (1-p) * 10-7 + p * (0.025)= (0.999) * 10-7 + 10-3 * 0.025 25 microseconds per reference!•I.e.,250 * memory access time!Virtual MemoryCS-502 Fall 2007 9Performance Example (continued)•Goal: achieve less than 10% degradation(1-p) * 10-7 + p * (0.025) < 1.1 * 10-7i.e.,p < (0.1 * 10-7) / (0.025 - 10-7) 0.0000004 •I.e.,1 fault in 2,500,000 accesses!Virtual MemoryCS-502 Fall 2007 10Working Set Size•Assume average swap time of 25 millisec.•For memory access time = 100 nanoseconds•Require < 1 page fault per 2,500,000 accesses•For memory access time = 1 microsecond•Require < 1 page fault per 250,000 accesses•For memory access time = 10 microseconds•Require < 1 page fault per 25,000 accessesVirtual MemoryCS-502 Fall 2007 11Object Lesson•Working sets must get larger in proportion to memory speed!•Disk speed ~ constant (nearly)•I.e., faster computers need larger physical memories to exploit the speed!Virtual MemoryCS-502 Fall 2007 12Class Discussion1. What is first thing to do when the PC you bought last year becomes too slow?2. What else might help?3. Can we do the same analysis on TLB performance?Virtual MemoryCS-502 Fall 2007 13TLB fault performance•Assumptions–m = memory access time = 100 nsec–t = TLB load time from memory = 300 nsec= 3 * m•Goal is < 5% penalty for TLB misses–I.e., EAT < 1.05 * m•How low does TLB fault rate need to be?Virtual MemoryCS-502 Fall 2007 14TLB fault performance•Assumptions–m = memory access time = 100 nsec–t = TLB load time from memory = 300 nsec= 3 * m•Goal is < 5% penalty for TLB misses–I.e., EAT < 1.05 * m•EAT = (1-p) * m + p * t < 1.05 *m  < (0.05 * m) / (t – m)= 0.05 * m / 2 * m = 0.025•I.e., TLB fault rate should be < 1 per 40 accesses!Virtual MemoryCS-502 Fall 2007 15TLB fault performance (continued)•Q: How large should TLB be so that TLB faults are not onerous, in these circumstances?•A: Somewhat less than 40 entries•Assuming a reasonable degree of locality!Virtual MemoryCS-502 Fall 2007 16Summary of this Topic•A quantitative way of estimating how large the cache needs to be to avoid excessive thrashing, where–Cache = Working set in physical memory–Cache = TLB size in hardware•Applicable to all forms of cachingVirtual MemoryCS-502 Fall 2007 17Next topicVirtual MemoryCS-502 Fall 2007 18Caching issues•When to put something in the cache•What to throw out to create cache space for new items•How to keep cached item and stored item in sync after one or the other is updated•How to keep multiple caches in sync across processors or machines•Size of cache needed to be effective•Size of cache items for efficiency•…From previous topicVirtual MemoryCS-502 Fall 2007 19Physical Memory is a Cache of Virtual Memory, so …•When to swap in a page•On demand? or in anticipation?•What to throw out•Page Replacement Policy•Keeping dirty pages in sync with disk•Flushing strategy•Keeping pages in sync across processors or machines•Defer to another time•Size of physical memory