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.
