GATE 2016 CS – Question 59
Consider a computer system with ten physical page frames. The system is provided with an access sequence $(a_1, a_2, \ldots, a_{20}, a_1, a_2, \ldots, a_{20})$, where each $a_i$ is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 1
Explanation
Both policies fault on the first 20 references. After that, both end up holding $a_1, \ldots, a_9$ and $a_{20}$ in the frames. In the second round, $a_1, \ldots, a_9$ are hits. For $a_{10}$, last-in-first-out replaces the newest page $a_{20}$, and then each of $a_{10}$ to $a_{20}$ faults in turn, which is 11 more faults, so 31 in total. The optimal policy instead evicts one of $a_1, \ldots, a_9$, which are never needed again, keeps $a_{20}$, and so $a_{20}$ is a hit. That gives 10 faults in the second round and 30 in total. The difference is $31 - 30 = 1$.