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

## Question:

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 is a distinct virtual page number. The difference in the number of page faults between the last-in-ﬁrst-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) →
a1 to a10 will result in page faults = 10 page faults,
Then a11 will replace a10 (last in is a10), a12 replace a11 and ...till a20 = 10-page faults 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.
So total faults will be 10+10+11 = 31.
Second Optimal Page Replacement Policy →
a1 to a10 = 10 page faults,
a11 will replace a10 because among a1 to a10, a10 will be used later, a12 will replace a11 and so on = 10 page faults.
a20 will be top of stack and a9…a1 are remained as such.
a1 to a9 = 0 page fault. a10 will replace a1 because it will not be used afterward and so on, a10 to a19 will have 10-page faults.
So no page fault for a20.
Total = 10+ 10 +10 = 30.
So the difference between LIFO - Optimal = 1

Thank You