Replacement Algorithms

Replacement Algorithms

1. optimal algorithm

   • At the moment that a page fault occurs, some set of pages is in memory.   One of these pages will be referenced on the very next instruction.  Other pages may not be referenced until 10, 100, 1000 instructions later. Each page can be labeled with the number of instructions that will be executed before that page is first referenced.

2. NRU

   • When a page fault occurs, the operating system inspects all the pages and divided them into four categories based on the current values of their R and M bits: 0. not referenced, not modified. 1.not referenced, modified 2.referenced, not modified 3.referenced, modified 
   • The Not Recently Used algorithm removes a page at random from the lowest numbered nonempty class.

3. FIFO

4. second chance

   • Inspect the R bit of the oldest page. If it is 0, the page is both old and unused, so it is replaced immediately. If the R bit is 1, the bit is cleared, the page is put onto the end of the list of pages, and its load time is updated as though it had just arrived in memory.  Then the search continues. 

5. clock alogrithm

   • Although second chance is a reasonable algorithm it is unnecessarily inefficient because it is constantly moving pages around on its list. 
   • When a page fault occurs, the page being pointed to by the hand is inspected. If its R bit is 0, the page is evicted, the new page is inserted into the clock in it s place, and the hand is advanced one position. If R is 1, it is cleared and the hand is advanced to the next page. 

6. LRU

   • To fully implement LRU, it is necessary to maintain a linked list of all pages in memory, with the most recently used page at the front and the least recently used page at the rear.  The difficulty is that the list must be updated on every memory reference.  
   • The other way with special hardware. It requires equipping the hardware with a 64-bit counter that is automatically incremented after each instruction. Furthermore, each page table entry must also have a field large enough to count the counter.    After each memory reference, the current value of C is stored in the page table entry for the page just referenced. When a page fault occurs, the operating system examines all the counters in the page table to find the lowest one. 

7. NFU

   • It requires a software counter associated with each page, initially zero. At each clock interrupt, the opeating system scans all the pages in memory. For each page, teh R bit is added to the counter. The counter roughly keep track of how often each page has been referenced. When a page fault occurs, the page with the lowest counter is chosen for replacement. 
   • Main problem, it never forgets anything.   The operating system can remove useful pages instead of pages no longer in use. 
   • aging
     • It is a modified version of NFU to avoid the storage of old values and to simulate LRU. 
     • 1.The counters are each shifted right 1 bit before the R bit is added in. 2.The R bit is added to the leftmost rather than the rightmost bit. When a page fault occurs, the page whose counter is the lowest is removed.  

8. trashing

   • A program causing page faults every few instructions.

9. demand paging

   • As soon as the CPU tries to fetch the first instruction, it gets a page fault, causing the operating system to bring in the page containing the first instruction. After a while, the process has most of the pages it needs and settles down to run with relatively few page faults.  

10. locality of reference

    • During any phrase of execution, the process references only a relatively small fraction of its pages. Like mutipass compiler.

11. working set

    • The set of pages used by the k most recent memory references. Another approach is: the set of pages used during the past 100 msec of execution time. (for each process its own execution time counts)
    • Working set of a process: The set of pages that a process is currently using,   Another approach: The set of pages it has referenced during the past (tau) seconds of the virtual time 
    • replacement algorithm
      • The basic is to find a page that is not in the working set and evict it. The hardware is assumed to set teh R and M bits as discussed earlier. Similarly, a periodic clock interrupt is assumed to cause software to run that clears teh Referenced bit on every clock tick. On every page fault, the page table is scanned to look for a suitable page to evict. 
      • As each entry is processed, the R bit is examined, If ti is 1, the current virtual time is written into the Time of last use field in the page table, indicating that the page was in use at the time the fault occurred.  Since the page has been referenced during the current clock tick,  it is clearly in the working set and is not a candidate for removal. If R is 0, the page has not been referenced during teh current clock tick and may be a candidate for removal. To see whether or not it should be removed, its age is computed and compared to (tau). If the age is greater than (tau), the page is no longer in the working set and the new page replaces it. The scan continues updating the remaining entries. However, if R is 0 but the age is less than or equal to (tau) the page is still in the working set.
    • WSClock algorithm
      • It uses clock hand instead of scanning the entire page table. And it uses the same algorithm but if the page pointed has R = 0, with age greater than (tau) and is dirty, it cannot be claimed immediately since no valid copy is present on disk. To avoid process switch, the write to disk is scheduled, but the hand is advanced and the algorithm continues with the next page. After all, there might be an old, clean page further down the line that can be use immediately. 
      • What happens if the hand comes all the way around and back to its staring point ? There are two cases we have to consider: 1.At least one write has been scheduled. The hand just keep moving, looking fro a clean page. Since one or more writes have been scheduled, eventually some write will complete and its page will be marked as clean. The first clean page encountered is evicted. This page is not necessarily the first write scheduled because the disk driver may reorder writes in order to optimize disk performance.   2.No writes have been scheduled.  All pages are in the working set, otherwise at least one write would have been scheduled. Lacking additional information, the simplest thing to do is claim any clean page and use it.