GATE Overflow Test Series | Operating Systems | Test 2 | Question: 26

Question

Consider a computer system with twenty physical page frames. The system is provided with an access sequence $(a_{1}, a_{2},\ldots,a_{2021}, a_{1}, a_{2},\ldots,a_{2021})$, 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 ________

Answer 1

In LIFO we will first have $2021$ page faults for first $2021$ page accesses followed by $19$ page hits and then $2002$ page faults. So, total page faults $ = 2021 + 2002 = 4023.$

In optimal page replacement, the page frame which is going to be accessed the furthest will be replaced next. For the first $2021$ page frames, we have $2021$ page faults like for LIFO. Then, we have $19$ page hits. Then when $a_{20}$ comes instead of replacing $a_{2021}$ as in LIFO, here it'll replace $a_1$ and this means for $a_{2021}$ we will get a hit instead of a miss as for LIFO. So, the optimal page replacement strategy will have $1$ page fault less than that of LIFO.