Page Replacement Algorithms in OS

There are four types of Page Replacement Algorithms are given as follows:
1. FIFO Algorithm
2. LRU Algorithm
3. Optimal Page Replacement Algorithm
4. LFU Algorithm

FIFO (First-in-First-out) Algorithm:

FIFO is the simplest page replacement algorithm. The basic idea behind this is ” Replace a page that page is the oldest page of all the pages of main memory” or ” Replace the page that has been in memory longest“. FIFO focuses on the length of time a page has been in memory rather than how much the page is being used.
To illustrate the page replacement algorithm, we use the reference string for memory with 3 frames:

0  1  2  3  0  1  2  3  0  1  2  3  4  5  6  7

FIFO

This example incurs 16 pages of faults. The symbol “*” indicates the new page in the memory. The symbol “✔” indicates the page fault. The performance of the page replacement algorithm measured through the page fault rate.

Page fault rate = Number of page faults/Number of bits in the reference string
Page fault rate = 16/16 = 100%

LRU (Least Recently Used) Algorithm:

The criteria of this algorithm is that ” Replace a page that hasn’t been used for the longest period of time“. This algorithm strategy is that ” The page replacement looking backwards in time rather than forward.
To illustrate the page replacement algorithm, we use the reference string for memory with 3 frames:

0  1  2  3  0  1  2  3  0  1  2  3  4  5  6  7

LRU

Page fault rate = 16/16 = 100%

Optimal Page Replacement Algorithm:

The Optimal Page Replacement Algorithm has the lowest page-fault rate of all algorithms. The criteria of this algorithm are ” Replace a page that will not be used for the longest period time“.
To illustrate the page replacement algorithm, we use the reference string for memory with 4 frames:

1  2  3  2  5  6  3  4  6  3  7  3  1  5  3  6  3  4  2  4  3  4  5  1

Optimal

Page fault rate = 11/16 = 68.75%

LFU (Least Frequently Used) Algorithm:

Least Frequently Used Algorithm basic idea is that ” Selects a page for a replacement if the page has not been used often in the past ” or ” Replace page that has the smallest count“. For this algorithm, each page maintains a counter which counters value shows the least count, replace that page. The reason for this selection is that an actively used page should have a large reference count, So don’t replace the actively used page. The frequent counter is reset each time a page is loaded.
To illustrate the page replacement algorithm, we use the reference string for memory with 3 frames:

0  1  2  3  0  1  2  3  0  1  2  3  4  5  6  7

LFU

Page fault rate = 12/16 = 75%