operating system os

OS Page Replacement Algorithms

« Previous Tutorial Next Tutorial »

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.

Optimal 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.

Not Recently Used (NRU) Page Replacement Algorithm

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.

First-In First-Out (FIFO) Page Replacement Algorithm

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.

Second Chance Page Replacement Algorithm

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.

Clock Page Replacement Algorithm

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.

Least Recently Used (LRU) Page Replacement Algorithm

The least recently used (LRU) page replacement algorithm is an excellent algorithm.

This page replacement algorithm can't be implemented without special hardware.

Not Frequently Used (NRU) Page Replacement Algorithm

The not frequently used (NRU) page replacement algorithm is a crude attempt to approximate least recently used.

Aging Page Replacement Algorithm

The aging page replacement algorithm is a better approximation to least recently used (LRU) page replacement algorithm and can be implemented efficiently.

Working Set Page Replacement Algorithm

The working set page replacement algorithm is expensive to implement but has reasonable performance.

WSClock Page Replacement Algorithm

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.

Summary of Page Replacement Algorithm

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.
NRU Very crude.
FIFO Might throw out important pages.
Second Choice Improvement over FIFO.
Clock Realistic
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.

« Previous Tutorial Next Tutorial »


Quick Links
Signup - Login - Give Online Test