FIFO Page-replacement algorithm
The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm. A FIFO replacement algorithm associates with each page the time when that page was brought into memory.
When a page must be replaced, the oldest page is chosen.
We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory, we insert it at the tail of the queue.
In above example, The first three references (7, 0, 1) cause page faults and are brought into these empty frames.
The next reference (2) replaces page 7, because page 7 was brought in first. Since 0 is the next reference and 0 is already in memory, we have no fault for this reference.
The first reference to 3 results in replacement of page 0, since it is now first in line.
Because of this replacement, the next reference, to 0, will fault. Page 1 is then replaced by page 0. This process continues as shown in Figure above. Every time a fault occurs, we show which pages are in our three frames. There are fifteen faults altogether.
Sometimes the number of faults for more frames is greater than the number of faults for less frames. This most unexpected result is known as for some page-replacement algorithms as Belady Anamoly, the page-fault rate may increase as the number of allocated frames increases.
Optimal Page Replacement Algorithm
Replace the page that will not be used for the longest period of time is the strategy here. Such a strategy shall never have Belady Anamoly. Use of this page-replacement algorithm guarantees the lowest possible page fault rate for a fixed number of frames.
The first three references cause faults that fill the three empty frames. The reference to page 2 replaces page 7, because page 7 will not be used until reference 18, whereas page 0 will be used at 5, and page 1 at 14.
The reference to page 3 replaces page 1, as page 1 will be the last of the three pages in memory to be referenced again. No replacement algorithm can process this reference string in the same number of frames with fewer faults.
Unfortunately, the optimal page-replacement algorithm is difficult to implement, because it requires future knowledge of the reference string.
LRU Page Replacement
If we use the recent past as an approximation of the near future, then we can replace the page that has not been used for the longest period of time. This approach is the Least recently used algorithm.
LRU replacement associates with each page the time of that page's last use.
When a page must be replaced, LRU chooses the page that has not been used for the longest period of time. We can think of this strategy as the optimal page-replacement algorithm looking backward in time, rather than forward.
If we let "sR" be the reverse of a reference string "S", then the page-fault rate for the Optimal algorithm on "S" is the same as the page-fault rate for the Optimal algorithm on "sR". Similarly, the page-fault rate for the LRU algorithm on "S" is the same as the page-fault rate for the LRU algorithm on "sR".
Like optimal replacement, LRU replacement does not suffer from Belady's anomaly.
Second-Chance Algorithm
Every page has an additional bit called Reference bit.
When a page has been selected, however, we inspect its reference bit. If the value is 0, we proceed to replace this page; but if the reference bit is set to 1, we give the page a second chance and move on to select the next FIFO page.
When a page gets a second chance, its reference bit is cleared, and its arrival time is reset to the current time. Thus, a page that is given a second chance will not be replaced until all other pages have been replaced (or given second chances).
One way to implement the second-chance algorithm (sometimes referred to as the clock algorithm) is as a circular queue.
A poi11ter (that is, a hand on the clock) indicates which page is to be replaced next. When a frame is needed, the pointer advances until it finds a page with a 0 reference bit. As it advances, it clears the reference bits.
Once a victim page is found, the page is replaced, and the new page is inserted in the circular queue in that position.
Notice that, in the worst case, when all bits are set, the pointer cycles through the whole queue, giving each page a second chance. It clears all the reference bits before selecting the next page for replacement. Second-chance replacement degenerates to FIFO replacement if all bits are set.
Enhanced Second-Chance Algorithm
Each page has the reference bit and the modify bit which indicates when the page was replaced.
With these two bits, we have the following four possible classes:
(0, 0) neither recently used nor modified - best page to replace
(0, 1) not recently used hut modified-not quite as good, because the page will need to be written out before replacement
(1, 0) recently used but clean-probably will be used again soon
(1, 1) recently used and modified -probably will be used again soon, and the page will be need to be written out to disk before it can be replaced
Each page is in one of these four classes. When page replacement is called for, we use the same scheme as in the clock algorithm; but instead of examining whether the page to which we are pointing has the reference bit set to 1, we examine the class to which that page belongs.
We replace the first page encountered in the lowest nonempty class. Notice that we may have to scan the circular queue several times before we find a page to be replaced.