GATE | GATE-CS-2016 (Set 1) | Question 59

Consider a computer system with ten physical page frames. The system is provided with an access sequence a1, a2, …, a20, a1, a2, …, a20), where each ai 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 __________

[Note that this question was originally Fill-in-the-Blanks question] (A) 0
(B) 1
(C) 2
(D) 3

Answer: (B)

Explanation: LIFO stands for last in, first out
a1 to a10 will result in page faults, So 10 page faults from a1 to a10.
Then a11 will replace a10(last in is a10), a12 will replace a11 and so on till a20, so 10 page faults from a11 to a20 and a20 will be top of stack and a9…a1 are remained as such.
Then a1 to a9 are already there. So 0 page faults from a1 to a9.
a10 will replace a20, a11 will replace a10 and so on. So 11 page faults from a10 to a20. So total faults will be 10+10+11 = 31.

Optimal
a1 to a10 will result in page faults, So 10 page faults from a1 to a10.
Then a11 will replace a10 because among a1 to a10, a10 will be used later, a12 will replace a11 and so on. So 10 page faults from a11 to a20 and a20 will be top of stack and a9…a1 are remained as such.
Then a1 to a9 are already there. So 0 page faults from a1 to a9.
a10 will replace a1 because it will not be used afterwards and so on, a10 to a19 will have 10 page faults.
a20 is already there, so no page fault for a20.
Total faults 10+10+10 = 30.
Difference = 1

Leave a Reply

Your email address will not be published. Required fields are marked *