GATE CSE 2016 | Set 1 | Question: 49

Question

Consider a computer system with ten physical page frames. The system is provided with an access sequence $(a_{1}, a_{2},....,a_{20}, a_{1}, a_{2},...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_________.

Comments

if in place of LIFO it is LRU then the difference is 10, just a mental exercise.

---

can visualise like this : 

---

In this question, I have tried a method myself, like here 20 unique elements are having 10 frames, so i scaled down and used a 20/5= 4 unique elements with 10/5=2 frames, hence I have considered the sequence like {1,2,3,4,1,2,3,4} and got LIFO=7 and Optimal fage faults=6 and hence difference as 1. So is it a correct analogy to solve this type of question?

Answer 1

Answer is $1$.

In LIFO first $20$ are page faults followed by next $9$ hits then next $11$ page faults. (After $a_{10}$, $a_{11}$ replaces $a_{10}, a_{12} $ replaces $a_{11}$ and so on)

In optimal first $20$ are page faults followed by next $9$ hits then next $10$ page faults followed by last page hit.

Comments

I have a doubt on this one, in LIFO after the first 20 page faults and 9 hits, then the 10th one will replace the 9th page i guess as it is last in first out?

---

last in was 20th page. 9th was just a page hit

---

But in FIFO when a hit occurs , we replace that page last.

So, why here we will not think which hit last replaces first?

---

@srestha sorry. did not get your question.

---

Sir I have answered it at last. R u getting it?

---

It can also be solved taking a smaller example like 1,2,3,4,1,2,3,4.

Here we can consider the number of physical page frame as 2.

---

Amazing

Answer 2

the answer is $31-30=1$

Comments

Yes will replace a11 with a2, a12 with a3 and so on according to FIFO Order

---

Thankyou

---

nice explanation 👏

Answer 3

In LIFO last access page will be replaces first

In LIFO we replace Last access page  First . As here First put a1 , then a2.......then a10 . As here 10 frames. Now replaces a10 with a11 to a20.

Now we are getting a1 to a9 hit as those are already in first 9 frames. Next a10 will be replace a9 as it is last access frame. And others will replace a10 , a11 will replace a10...........So, a20 will be hit .

Same with optimal too 

Comments

@srestha mam

plz edit the LIFO definition and ans it may create wrong concept who will not see comment.

---

@Arjun sir @srestha ma'am
what about MRU 
does it follow Last Access or Last In.?

---

when a10 comes the second time, it'll replace a20 not a9

Answer 4

YES as you see the que and start solving it you will get the illusion that answer is 0 but if solve question fully...answer will come 1.

Comments

Absolutely right. In optimal one fault is less and that is becoz of a20.
a20 is hit in a optimal which is miss is LIFO.

Answer 5

Correct Answer : 1.

LIFO Page Faults ==> 20 + 11 = 31

OPTIMAL Algo Page Faults ==> 20+10 = 30

Difference between {LIFO , OPTIMAL} Page Faults = 31-30 = 1.

Second Approach:

Difference Between Total Hits.

Hits in LIFO = 1.

Hits in OPTIMAL Algo = 1+1 = 2.

Difference between {LIFO , OPTIMAL} Page Faults = 2-1 = 1.

Answer 6

It can also be solved taking a smaller example like 1,2,3,4,1,2,3,4.

Here we can consider the number of physical page frame as 2.

Thus in LIFO, it comes out to be 7 page fault and in Optimal it is 6.

Hence difference is 7- 6 = 1.