GATE - 2016 | OS | Consider a computer system with ten physical page frames. The system

GATE - 2016 [Operating System]

Question:

Consider a computer system with ten physical page frames. The system is provided with an access sequence (a₁,a₂,…,a₂₀,a₁,a₂,…,a₂₀), 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 ___________.

A	1
B	2
C	3
D	4

Solution:

Option (A) is Correct

We have to calculate the difference between the last-in-first-out page replacement policy and the optimal page replacement policy.
First, we can consider LIFO (Last In First Out) →
a₁ to a₁₀ will result in page faults = 10 page faults,
Then a₁₁ will replace a₁₀ (last in is a₁₀), a₁₂ replace a₁₁ and ...till a₂₀ = 10-page faults and a₂₀ will be top of stack and a₉…a₁ are remained as such.
Then a₁ to a₉ are already there.
So, 0-page faults from a₁ to a₉.
a₁₀ will replace a₂₀, a₁₁ will replace a₁₀ and so on = So 11 page faults.
So total faults will be 10+10+11 = 31.
Second Optimal Page Replacement Policy →
a₁ to a₁₀ = 10 page faults,
a₁₁ will replace a₁₀ because among a₁ to a₁₀, a₁₀ will be used later, a₁₂ will replace a₁₁ and so on = 10 page faults.
a₂₀ will be top of stack and a₉…a₁ are remained as such.
a₁ to a₉ = 0 page fault. a₁₀ will replace a₁ because it will not be used afterward and so on, a₁₀ to a₁₉ will have 10-page faults.
So no page fault for a₂₀.
Total = 10+ 10 +10 = 30.
So the difference between LIFO - Optimal = 1

Thank You