Explain Page-replacement with any one-page replacement algorithm.
FIFO Page replacement : Refer the Prev Question
LRU Page Replacement Algorithm
⦁ As the name suggests, this algorithm works on the principle of “Least Recently Used“.
⦁ It replaces the page that has not been referred by the CPU for the longest time.
Example:
⦁ Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 4 page frames. Find number of page faults.
Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4
Page faults
0 is already their 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 takes 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:
⦁ This algorithm replaces for the longest time.
the page that will not be referred
by the CPU in future
⦁ It is practically impossible to implement this algorithm.
⦁ This is because the pages that will not be used in future cannot be predicted.
for the longest time
⦁ However, it is the best-known algorithm and gives the least number of page faults.
⦁ Hence, it is used as a performance measure criterion for other algorithms.
Example-2:Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, with 4 page frame. Find number of page fault.
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 —> 0 Page fault.. 4 will takes 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. The use of Optimal Page replacement is to set
up a benchmark so that other replacement algorithms can be analyzed against it.
