GATE Overflow Test Series | Mock GATE | Test 4 | Question: 41

Question

Consider the following page reference string:
$$7, 2, 3, 1, 2, 5, 3, 4, 6, 7,7,1$$
Assume demand paging with three frames, and all frames being initially empty, so the first unique page access cause a page fault.
If $\alpha$ is the number of page faults in optimal page replacement and $\beta$ is the number of page faults in LRU page replacement, the value of $\alpha - \beta$ is _________

Answer 1

Reference string $:7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1$

$\textbf{Optimal page replacement:}$

1.$7,2,3-3$ page faults

2.$1,2,3$

3.$1,5,3$

4.$1,5,4$

5.$1,5,6$

6.$1,5,7$

Total $8$ page faults.

$\textbf{LRU:}$

1.$7,2,3-3$ page faults

2.$1,2,3$

3.$1,2,5$

4.$3,2,5$

5.$3,4,5$

6.$3,4,6$

7.$7,4,6$

8.$7,1,6$

Total $10$ page faults.

$\therefore$ The value of $\alpha - \beta = 8 - 10 = -2.$

Comments

@gatecse @Deepak Poonia @Sachin Mittal 1 sir in this optimal page replacement policy while replacing 6 we not have 4,5 used in future so can we replace any of them or is there any rule?

Here in solution after 1,5,4 they have taken 1,5,6 so if we take 1,6,4 instead of 1,5,6 then it is valid or not?

---

@pankil2501 Both are fine. We will get the same number of page faults in both cases.