Explain Page-replacement with any one page replacement algorithm.
The page replacement algorithm decides which memory page is to be replaced. The process of replacement is sometimes called swap out or write to disk. Page replacement is done when the requested page is not found in the main memory (page fault).
It is very important to have the optimal frame allocation and page replacement algorithm. Frame allocation is all about how many frames are to be allocated to the process while the page replacement is all about determining the page number, which needs to be replaced in order to make space for the requested page.
Types of Page Replacement Algorithms:
There are various page replacement algorithms. Each algorithm has a different method by which the pages can be replaced.
⦁ Optimal Page Replacement algorithm → this algorithms replaces the page, which will not be referred for so long in future. Although it cannot be practically
implementable but it can be used as a benchmark. Other algorithms are
compared to this in terms of optimality.
⦁ Least recent used (LRU) page replacement algorithm → this algorithm
replaces the page, which has not been referred for a long time. This algorithm
is just opposite to the optimal page replacement algorithm. In this, we look at
the past instead of staring at future.
⦁ FIFO → in this algorithm, a queue is maintained. The page, which is assigned the frame first, will be replaced first. In other words, the page, which resides at the rare end of the queue, will be replaced on the every page fault.
First In First Out (FIFO):
This is the simplest page replacement algorithm. In this algorithm, the operating
system keeps track of all pages in the memory in a queue; the oldest page is in the
front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
Example-1:
Consider page reference string 1, 3, 0, 3, 5, 6 with 3 page frames. Find number of page faults.
Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3 Page Faults.
when 3 comes, it is already in memory so —> 0 Page Faults.
Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e
1. —>1 Page Fault.
6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3
—>1 Page Fault.
Finally, when 3 come it is not available so it replaces 0 1 page fault
Belady’s anomaly – Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm. For example, if we consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.
