**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.**