Page Replacement Algorithm in Operating System:
Definition and Explanation:
The algorithms used to select the page to be replaced are called page replacement policies. The main three policies are:
1. First-In First-Out (FIFO):
The First-in First-out policy removes the page that has been resident in memory for the longest time. It assumes mat such a page is no longer in use. It is also very simple to implement. In spite of being frequently required, the FIFO method, will periodically remove pages. It causes another early page fault.
Example:
| 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
| 7- - | 70 - | 70 1 | 20 1 | 23 1 | 23 0 | 43 0 | 42 0 | 42 3 | 02 3 | 01 3 | 01 2 | 71 2 | 70 2 | 70 1 |
In the above example, we have three empty frames and first three references (7,0,1) are brought in these frames. Now the next reference (2) replaces page 7 because it came first. The next reference is 0 that is already in the memory so no page fault occurs. This process continues as shown in the figure. Whenever a page fault occurs, we replace the page that entered the memory first of all.
2. Page Optimal Replacement:
This algorithm produces lowest page fault rate. It replaces the page that will not be used for the longer period of time.
3. Least Recently Used (LRU):
Least Recently Used policy replaces the page whose time since last reference is greater. This requires a time stamp (marker) recording for a page frame at the time of each reference. The selected page for replaced would then, have the oldest time. The overhead in such a system is that of maintaining all the time stamps (generally a linked-list) and the time taken to find the oldest value.
4. Not Recently Used (NRU):
Not Recently Used algorithm associates a page reference bit' with each page frame. This policy selects an interval of time during which the page reference bit is set to 1 if the page is referenced during this time. After the interval terminates, all the bits are reset and a new interval of time is set. Thus if a page has its page reference bit set to 1, it indicates that this page has been used during the current interval. The NRU policy simply selects for replacement any page with a page-referenced bit of 0.
5. LRU Approximation Algorithms:
There are three LRU approximation page replacement algorithms. All make use of a reference bit associated with each entry in the page table. Initially the reference bit is set to 0. When the page is accessed (either read or write), the reference bit is set to 1. After some time the bits are checked and from this we know which pages have been used since the last check.
1 Additional-Reference Bits Algorithm:
In this algorithm an S-bit byte for each page is kept in a table in memory. At regular time intervals, the reference bits for each page are shifted into the high-order bit of its 8-bit byte, shifting the other bits right 1 bit and discarding the low-order bit. Then the reference bit is cleared. These 8-bit shift registers contain the history for the page use for the last eight time periods. If a page was recently used,, the page will have a register like 10000000. If a page has not been used at all, it will have a register like 00000000. If the registers are interpreted as an unsigned integer, the page with the lowest number is the LRU page. If more than one page has the same LRU value then we can either swap all pages with that value or use a FIFO selection.
2. Second-Chance Algorithm:
This algorithm is a FIFO replacement algorithm with consideration given to the reference bit. When a page has been selected for replacement, its reference bit is inspected. If it is set to 0, then it hasn't been used recently and it is replaced. If the reference bit is set to 1, then it is given a second chance and move on to the next FIFO page. When a page is given a second chance, its reference bit is cleared and its arrival time reset to the current time. This can easily be implemented using a circular queue. If all reference bits are set to 1 then the algorithm degenerates to FIFO.
3. Enhanced Second-Chance Algorithm:
In this algorithm, the method is the same as for second chance but the reference bit and the modify bit are used as an ordered pair. This gives 4 classes of pages:
1. (0,0) - Neither recently used nor modified - best replacement choice.
2. (0,1) - Not recently used by modified - not quite as good as the page will need to be written out before replacement.
3. (1,0) - Recently used but clean - it will probably be used again soon.
4. (1,1) - Recently used and modified - it will probably be used again soon and it needs to be written out before replacement.
When a page replacement is called for, a page will belong to one of these four classes. The page selected is the first one encountered in the lowest non-empty class. So when we are looking for a page to replace, we may need to cycle through the circular array several times before we find a page to be replaced. First time through, if encounter a page in a class (1,x) then give a second chance and reset the reference bit. When a (0,x) class page is found (i) and if it is (0,0) then replace. If it is (0,1) then may mark it and look further to see if there is a (0,0).
