Optimal Page Replacement Algorithm in Operating System - CodeTextPro


optimal page replacement algorithm in os
optimal page replacement algorithm


What is Page fault? / page fault in os -

When a processor needs to execute a particular page, that page is not available in the main memory, this situation is said to be “page fault”. When page fault happens, the page replacement will be needed.

The word “page replacement” means select a victim page in the main memory, replace that page with the required page from the backing store. (Disk). There is so many page replacement policy. Some popular page replacement algorithms are as follows.



1. FIFO (First in first out) page replacement algorithm.
2. LRU (Least recently used) page replacement algorithm
3. Optimal page replacement algorithm





FIFO algorithm/ FIFO page replacement algorithm :

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 the page in the front of the queue is selected for removal.

For example, consider page reference string 1, 3, 0, 3, 5, 6 and 3 page slots.

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.

Finally, 6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3 —>1 Page Fault.





LRU algorithm/ LRU page replacement algorithm :

In this algorithm, the page will be replaced which is least recently used.

Let say the page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2. Initially we have 4 page slots empty. 

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults 0 is already there so —> 0 Page fault. 

When 3 came it will take the place of 7 because it is least recently used —>1 Page fault 0 is already in memory so —> 0 Page fault. 

4 will take place of 1 —> 1 Page Fault Now for the further page reference string —> 0 Page fault because they are already available in the memory.







OPTIMAL page replacement algorithm:

In this algorithm, pages are replaced which are not used for the longest duration of time in the
future.

Let us consider page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 and 4 page slots.

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
0 is already there so —> 0 Page fault. 

When 3 came it will take the place of 7 because it is not
used for the longest duration of time in the future.—>1 Page fault. 0 is already there so —> Page fault.. 4 will take place of 1 —> 1 Page Fault. 

Now for the further page reference string
—> 0 Page fault because they are already available in the memory.
Optimal page replacement is perfect, but not possible in practice as the operating system cannot know future requests.



Post a Comment

0 Comments