Page Replacement Algorithms | Important Results

Page Replacement Algorithms-

 

Before you go through this article, make sure that you have gone through the previous article on Page Replacement Algorithms.

 

We have discussed-

  • When a page fault occurs, the required page has to be brought from the secondary memory.
  • If all the frames of main memory are already occupied, then a page has to be replaced.
  • Page replacement algorithms help to decide which page should be replaced.

 

In this article, we will discuss some important results.

 

Important Results-

 

Result-01: For a Reference String Consisting Of Repeated Sequence Of Page Numbers-

 

For such a reference string,

  • Optimal page replacement algorithm replaces the most recently used page to minimize the page faults.
  • This is because most recently page will be required after the longest time.
  • Thus, Optimal page replacement algorithm acts as Most Recently Used (MRU) page replacement algorithm.

 

In other words,

  • MRU page replacement algorithm will behave as Optimal page replacement algorithm.
  • MRU page replacement algorithm gives the optimal performance.

 

Example-

 

Consider the following reference string consisting of a repeated sequence of page numbers-

1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6

 

Here,

  • Both Optimal and MRU page replacement algorithm replaces the most recently used page.
  • Most recently used page will be required after the longest time.
  • Hence, both these algorithms give the optimal performance.

 

 

Total number of page faults occurred = 12

 

NOTES-

 

Note-01:

 

  • These are the minimum number of page faults that are possible.
  • If any other page replacement algorithm is used, it will surely give rise to more number of page faults.
  • FIFO and LRU page replacement algorithm give rise to 24 number of page faults.

 

Note-02:

 

  • CPU may generate such a reference string when executing loops.
  • This is because while executing loops, same set of instructions have to be executed again and again.

 

Note-03:

 

  • Principle of locality states that the next reference would be most probably from the most recently used pages.
  • Here, the behavior of Optimal page replacement algorithm contradicts with the principle of locality.
  • Here, Optimal algorithm replaces the most recently used page to give the optimal performance.
  • So, from here we can infer that principle of locality does not hold true in certain scenarios.

 

Result-02: For a Reference String Where First Half String Is a Mirror Image Of Other Half-

 

For such a reference string,

  • Optimal page replacement algorithm replaces the least recently used page or firstly arrived page to minimize page faults.
  • This is because such a page will be required after the longest time.
  • Thus, Optimal page replacement algorithm acts as LRU and FIFO page replacement algorithm.

 

In other words,

  • LRU and FIFO page replacement algorithm will behave as Optimal page replacement algorithm.
  • LRU and FIFO page replacement algorithm gives the optimal performance.

 

Example-

 

Consider the following reference string where first half string is a mirror image of other half string-

1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1

 

Here,

  • Optimal, LRU and FIFO page replacement algorithms replaces the least recently used or firstly arrived page.
  • Least recently used or firstly arrived page will be required after the longest time.
  • Hence, all these algorithms give the optimal performance.

 

 

Total number of page faults occurred = 14

 

  • These are the minimum number of page faults that are possible.
  • If any other page replacement algorithm is used, it will surely give rise to more number of page faults.

 

Remember-

 

  • Optimal page replacement algorithm always gives the best performance in every scenario.
  • This is because it foresees the future and takes the form of an algorithm which gives the best performance in that scenario.

 

Next Article- Segmentation in OS

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Page Replacement Algorithms | Important Results
Article Name
Page Replacement Algorithms | Important Results
Description
Page replacement algorithms help to decide which page should be replaced when a page fault occurs and main memory is full. FIFO Page Replacement Algorithm, LRU Page Replacement Algorithm, Optimal Page Replacement Algorithm are famous page replacement algorithms.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-