Summary of Page Replacement Algorithms

Summary of Page Replacement Algorithms

We have now considered a variety of page replacement algorithms. In this section we will briefly summarize them. The list of algorithms discussed is given in Figure 1.

Page replacement algorithms

The most favorable algorithm removes the page that will be referenced furthest in the future. Unfortunately, there is no way to find out which page this is, so in fact this algorithm cannot be used. It is useful as a benchmark against which other algorithms can be measured, however.

The NRU algorithm divides pages into four classes depending on the state of the R and M bits. A random page from the lowest-numbered class is chosen. This algorithm is easy to implement, but it is very simple. Better ones exist.

FIFO keeps track of the order in which pages were loaded into memory by keeping them in a linked list. Removing the oldest page then becomes unimportant, but that page might still be in use, so FIFO is a bad choice.

Second chance is a modification to FIFO that checks if a page is in use before removing it. If it is, the page is spared. This modification very much improves the performance. Clock is simply a different implementation of second chance. It has the same performance properties, but takes a little less time to implement the algorithm.

LRU is an excellent algorithm, but it cannot be executed without special hardware. If this hardware is not available, it cannot be used. NFU is a simple attempt to approximate LRU. It is not very good. On the other hand, aging is a much better approximation to LRU and can be executed efficiently. It is a good choice.

The last two algorithms use the working set. The working set algorithm gives reasonable performance, but it is somewhat expensive to implement. WSClock is a variant that not only gives good performance but is also efficient to implement.

On the whole, 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 executed efficiently. A few other algorithms exist, but these two are perhaps the most important in practice.


Tags

algorithm, wsclock, memory