Whenever a page fault occurs, then the OS has to choose a page just to remove from the memory to make room for that page which has to be brought in.
It must be re-written to disk just to bring disk copy up to date, if in case, the page to be removed has been modified or edited while in memory.
There is no any need to rewrite, in case, if the page hasn't been changed or modified. In this case, the disk copy is already up to date.
To evict at each page fault, just pick a random page. If a page is chosen that is not heavily used then the system performance becomes much better. If a page is removed which is heavily used, then it will have to be brought back in quickly resulting in extra overhead.
A lot of work has been done on page replacement algorithm experimentally and theoretically.
Here are the list of most important page replacement algorithms:
Now, let's take a brief look at all these different-different most important page replacement algorithm.
The optimal page replacement algorithm replaces the page referenced last among the current pages.
But there is no any way to specify that which page will be last, therefore in practical this algorithm can't be used, however this page replacement algorithm is useful as a benchmark against which other page replacement algorithms can be measured.
The not recently used (NRU) page replacement algorithm divides pages into 4 classes depending on the state of R and M bits.
From the lowest numbered class, a random page is chosen.
It is easy to implement this page replacement algorithm, but is very crude. Therefore better ones exist.
The first-in first-out (FIFO) page replacement algorithm keeps track of the order pages were loaded into memory just by keeping them in a linked list.
In FIFO algorithm, removing the oldest page then becomes trivial but the page might still be in use, therefore this page replacement algorithm is not a good choice.
In the second chance page replacement algorithm, a modification to first-in first-out that checks whether a page is in use before removing it. If it is then the page is spared. This modification improves the performance of the system.
The clock page replacement algorithm is basically a different implementation of the second chance page replacement algorithm. It has the same performance properties, but it takes less time to execute the algorithm.
The least recently used (LRU) page replacement algorithm is an excellent algorithm.
This page replacement algorithm can't be implemented without special hardware.
The not frequently used (NRU) page replacement algorithm is a crude attempt to approximate least recently used.
The aging page replacement algorithm is a better approximation to least recently used (LRU) page replacement algorithm and can be implemented efficiently.
The working set page replacement algorithm is expensive to implement but has reasonable performance.
The WSClock page replacement algorithm is a variant to the working set page replacement algorithm, that is, this page replacement algorithm not only gives good performance but is also efficient to implement.
The table given below summarises all the page replacement algorithm one by one.
This table lists all the algorithm along with their description.
|Page Replacement Algorithm||Short Description|
|Optimal||Not implementable but is useful as benchmark.|
|FIFO||Might throw out important pages.|
|Second Choice||Improvement over FIFO.|
|LRU||Difficult to implement but it's an excellent page replacement algorithm.|
|NFU||Fairly crude approximation to LRU.|
|Aging||Efficient algorithm that approximates LRU well.|
|Working Set||Somewhat expensive to implement.|
|WSClock||Good efficient page replacement algorithm.|
From all of the page replacement algorithm, these two are the best page replacement algorithm:
Both the above two page replacement algorithm gives good paging performance and can be implemented efficiently.