Summary of page replacement algorithms
Algorithm | Comments |
Optimal | Give optimal solution, but not implementable, use as a benchmark. |
Least Recently Used (LRU) | Efficient, but it is difficult to implement exactly. |
Most Recently Used (MRU) | Not efficient for all types of processes. |
FIFO (First-In, First-Out) | Might replace important page (most recently and frequently used page). |
Second chance | Good modification of FIFO and better performance. |
Clock Replacement algorithm | Second Chance with Circular list; efficient data structure and realistic. |
Not Recently Used (NRU) | Very basic approximation of LRU. |
Least Frequently Used (LFU) | A fairly crude approximation of LRU, expensive to implement. |
Working Set | Somewhat expensive to implement. |
WSClock | Most efficient algorithm. |
Aging | Efficient algorithm that approximates LRU well. |
All in all, the two best algorithms are aging and WSClock. They are based on LRU and the working set, respectively. Both give good paging performance and can be implemented efficiently.
A few other good algorithms exist, but these two are probably the most important in practice.