Chapter 9.2: Virtual MemoryChapter 9: Virtual MemoryPage ReplacementPage Replacement - moreBasic Page ReplacementSlide 6Slide 7More on PhilosophySlide 9Graph of Page Faults Versus The Number of FramesFirst-In-First-Out (FIFO) AlgorithmFIFO Illustrating Belady’s AnomalyFIFO Page ReplacementOptimal AlgorithmOptimal Page ReplacementSlide 16Least Recently Used (LRU) AlgorithmLRU Algorithm - CountersLRU Algorithm - StackUsing the Stack to Record The Most Recent Page ReferencesLRU Approximation AlgorithmsAdditional Reference BitsSecond-Chance (Clock) Page-Replacement AlgorithmSecond-Chance (clock) Page-Replacement AlgorithmEnhanced Second-Chance AlgorithmCounting AlgorithmsThere are MoreHomeworkEnd of Chapter 9.2Chapter 9.2: Virtual MemoryChapter 9.2: Virtual Memory9.2Silberschatz, Galvin and Gagne ©2005Operating System ConceptsChapter 9: Virtual MemoryChapter 9: Virtual MemoryChapter 9.1BackgroundDemand PagingProcess CreationChapter 9.2Page ReplacementChapter 9.3Allocation of Frames ThrashingMemory Mapped FilesChapter 9.4Allocating Kernel MemoryDemand SegmentationOperating System Examples9.3Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPage ReplacementPage ReplacementPage Replacement is a major topic in memory management and many factors come to bear on exactly how page replacement is implemented.Clearly, since we do not have to load all pages for a process into memory, we can increase the degree of multiprogramming because more room is available for more pages from additional processes.This may be likened to overbooking on aircraft flights. We don’t think everyone is going to show up. If they do, we have problems, even though normally this is not the case. There are many parameters used to determine how much memory to initially allocate to program pages (Chapter 9.3) which includes space for buffers for reading / writing data from storage devices. Then, just how is the determination made to replace pages one the process is executing?? (Chapter 9.2)9.4Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPage Replacement - moreWhen a process needs some (one or more) of its pages to be brought into memory, if there is no free space available in memory, we may well have to replace a page from some other existing process. . First glances at solutions are frequently not the best:1. terminate some other process – but this reduces the amount of multiprogramming and may make the user aware of paging – something we wish to avoid.Would you want this terminated process to be yours??2. We could swap out a process entirely; this too reduces multiprogramming.So good memory management schemes demands a carefully implemented page replacement policy.We will consider several9.5Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBasic Page ReplacementBasic Page Replacement1. Page Fault approach:1. Look for an available frame. (available space for a page in memory)2. If none is available, we free up a frame by writing its contents to a swap space and change page table to indicate that this page is no longer in memory. 3. Freed up frame will now hold new page for which process was faulted.2. Let us modify our approach to include a page replacement algorithm…in a bit more detail….1. Find the location of the desired page on disk2. Find a free frame:- If there is a free frame, use it- If there is no free frame, use a page replacement algorithm to select a victim frameand write victim frame to disk; change page table and available frame tables…3. Read the desired page into the (newly) free frame. 4. Update the page and frame tables.5. Restart the process(Of course, finding that victim frame is a real problem – later!!)9.6Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPage ReplacementPage ReplacementCan easily see how this works.Note: if no page frame is available, two page transfers are needed…One for writing victim frame to disk; one for bringing in new page.Don’t forget all the updating too!9.7Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPage ReplacementPage ReplacementCan use a ‘dirty bit to assist in selecting a page, if available.This indicates (in page table) if the page or frame has been modified.If bit is set, then page must be swapped out to disk.But if page has not been modified, then this page need not be swapped to disk.This represents significant savings! Don’t forget, however, that the page table must still be modified to reflect that this page is no longer in memory…9.8Silberschatz, Galvin and Gagne ©2005Operating System ConceptsMore on PhilosophyRecognize that demand paging totally changes the degree of multiprogramming available, since an entire process need not be in memory to run.The physical size of memory is not a constraint (although it will have some impact as to just how many processes can be in memory….).The need for an absent frame ‘merely’ causes a page fault.Of course, there are many issues surrounding the notion of a page fault and how to select a victim!We must solve two major problems in demand paging:1. developing a frame-allocation algorithm (Chapter 9.3), and2. selecting a page replacement algorithm. (here)Frame allocation refers to the number of frames allocated to a process, while the page replacement issue centers around the selection of a frame to write back to disk (if necessary). We certainly want to avoid any kind of … ‘thrashing.’Selection of a suitable page replacement strategy is extremely important, as we do not want to select one that causes a high page-fault rate.9.9Silberschatz, Galvin and Gagne ©2005Operating System ConceptsMore on PhilosophyAvailability of page frames: As the number of page frames available increases, the number of page faults will decrease. Adding more memory will result in a higher availability of page frames too – unless this is used to increase degree of multiprogramming..But we want to clearly minimize the number of page faults.So considerable effort will go into selection of the ‘best’ page replacement algorithm….A visual on the relationship between number of page faults and number of available frames is provided on the next slide.9.10Silberschatz, Galvin and Gagne ©2005Operating System ConceptsGraph of Page Faults Versus The Number of