Page Replacement Algorithm

In operating systems, that use paging for memory management, page replacement algorithms are needed to decide which page needed to be replaced when a new page comes in. Whenever a new page is referred to and not present in memory, a page fault occurs and the Operating System replaces one of the existing pages with a newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace.
Some of the algorithm used for page replacement algorithm is:

First In First out (FIFO) algorithm

• Oldest page in main memory is the one which will be selected for replacement.
• Easy to implement, keep a list, replace pages from the tail and add new pages at the head.

Belady’s Anomaly
Normally, one would expect that with the total number of frames increasing, the number of page fault decreases. However, for FIFO, there are cases where this generalization fails. This is called Belady’s Anomaly.

Optimal Page algorithm

• An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms. An optimal page-replacement algorithm exists and has been called OPT or MIN.
• Replace the page that will not be used for the longest period of time. Use the time when a page is to be used.

The least Recently Used (LRU) algorithm

• The page which has not been used for the longest time in the main memory is the one that will be selected for replacement.
• Easy to implement, keep a list, replace pages by looking back into time.
• The page with the smallest count is the one that will be selected for replacement.
• This algorithm suffers from the situation in which a page is used heavily during the initial phase of a process but then is never used again.

The Not Recently Used

The not recently used (NRU) page replacement algorithm is an algorithm that favors keeping pages in memory that have been recently used. This algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as reference. Similarly, when a page is modified (written to), a modified bit is set. The setting of the bits is usually done by the hardware, although it is possible to do so on the software level as well.
At a certain fixed time interval, a timer interrupts triggers and clears the referenced bit of all the pages, so only pages referenced within the current timer interval are marked with a referenced bit.
When a page needs to be replaced, the operating system divides the pages into four classes:
3. referenced, modified
2. referenced, not modified
1. Not referenced, modified
0. Not referenced, not modified
Although it does not seem possible for a page to be modified yet not referenced, this happens when a class 3 page has its referenced bit cleared by the timer interrupt. The NRU algorithm picks a random page from the lowest category for removal. So out of the above four-page categories, the NRU algorithm will replace a not-referenced, not-modified page if such a page exists. Note that this algorithm implies that a modified but not-referenced (within the last timer interval) page is less important than a not-modified page that is intensely referenced.

Clock

The clock is a more efficient version of FIFO than Second-chance because pages don't have to be constantly pushed to the back of the list, but it performs the same general function as Second Chance. The clock algorithm keeps a circular list of pages in memory, with the "hand" (iterator) pointing to the last examined page frame in the list. When a page fault occurs and no empty frames exist, then the R (referenced) bit is inspected at the hand's location. If R is 0, the new page is put in place of the page the "hand" points to. Otherwise, the R bit is cleared, then the clock hand is incremented and the process is repeated until a page is replaced.

Thrashing

Thrashing is a term referred to as a high paging activity. A process is thrashing if it is spending more of its time paging than actually executing.
Consider a process that currently needs some more frames. Currently, all the frames are occupied. So it will have to swap with certain pages; however, since all the pages are actively being used, there would be a need for an immediate page replacement after this. Such a scenario is called thrashing. It results in serious performance problems.