Page Replacement Algorithms in OS

Page Replacement Algorithms

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.

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

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.

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

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.