FOR FREE YEAR SOLVED

Some other Page Replacement algorithms

Prerequisite:  Optimal page replacement algorithm, Least Recently Used (LRU) algorithm, FIFO page replacement algorithm, Second Chance page replacement algorithm.

Most popularly used page replacement algorithms:

(i)   Optimal page replacement algorithm

(ii)  FIFO page replacement algorithm

(iii) Least Recently Used (LRU) algorithm

Some systems optimize their page cache by using different replacement algorithms, depending on the access type of the file.

There are more page replacement algorithms 

(i)  Most Recently Used (MRU) algorithm.

(ii) Least Frequently Used (LFU) algorithm.

(iii) Aging

(iv) Most frequently Used (MFU) algorithm.

(v) Second chance algorithm  (a modified version of FIFO). (Discussed in the previous chapter)

(vi) Clock page replacement.

(i) Most Recently Used (MRU) algorithm: 

In MRU, the page will be replaced which is recently used. It is exactly just opposite to LRU.

Some systems preferred MRU, instate of LRU, depending on the access type of the file. A file being read or written sequentially should not have its pages replaced in LRU order, because the most recently used page will be used last, or perhaps never again.

(ii) Least Frequently Used (LFU) algorithm: 

The Least Frequently Used (LFU) page-replacement algorithm requires that the page with the smallest count be replaced i.e. page will be replaced, which is not frequently used.

This page replacement algorithm needed when an actively used page should have a large reference count. 

But one disadvantage, when a page is used heavily during the initial phase of a process but then is never used again since it was used heavily; it has a large count and remains in memory even though it is no longer needed.

One solution is to shift the counts right by 1 bit at regular intervals, forming an exponentially decaying average usage count. This is modification can form of aging page replacement algorithm.

(iii) Aging: Aging is a modified version of the LFU algorithm with instead of just incrementing the counters of page references, putting the page recent uses by shifting and masking the reference bits. The reference bit has a limited memory which determined using a refresh parameter (reference counter length).

(iv) Most frequently Used (MFU) algorithm:

In MFU, the page replacement algorithm based on the condition that the page with the smallest count was probably just brought in and has yet to be used.

So, the most frequent page (highest count) will be replaced. It is opposite to Least Frequently Used (LFU).

But, neither MFU nor LFU replacement is commonly used. The implementation of these algorithms is expensive, and they do not approximate optimal replacement well.

(v) Clock page replacement:

Before you see the Clock page replacement, please follow the data structure of the second chance algorithm, Second Chance page replacement algorithm

Clock page replacement is not a different page replacement algorithm; it is a better data-structure than second chance algorithm.

If we see the previous data-structure of the second chance algorithm, it is implemented by a linked list, but the problem of linked is time-consuming. Unnecessarily extra time needed because it is constantly moving pages around on its list.

To overcome it, we can use a circular queue (using a linked list) in the form of a clock. A pointer (that is, a hand on the clock) indicates which page is to be replaced next.