Gate Made Easy Mock Test

Question

A system uses optimal policy for a page replacement. It has 4 page frames with no pages loaded to begin with. Consider the following scenario
Case-1: System first accesses 200 distinct pages in sequential order and then access same 200 distinct pages in same order.
Case-2: System first accesses 200 distinct pages in sequential order and then access same 200 distinct page in reverse order.
The difference in the number of faults occurred in both case are _________.

Comments

Is $0$ answer ?

---

Yes 0 is the answer

Answer 1

consider the pages are 1,2,3,.....200

case 1:

1,2,3,.....200 ....1,2,3,.....200

after 1,2,3,4 pages 4 page faults

now 4 will be replaced by 5 as it is optimal policy...so there will be 200 page faults

after 200 pages the memory contents are

[1][2][3][200]....now again 1,2,3,.....200  are accessed for 1,2,3 there will be no page faults and the last 200 will not be replaced as it is required in future so 200-3(hits of 1,2,3)-1(hit of 200)=196

total page faults in case1:396

case 2:

1,2,3,.....200 ..200,199,...2,1

this will exactly behave as FIFO

so 200 page faults for first 1,2,3,.....200 pages

so when they are accessed in reverse order 200,199,....2,1

there will be hits on 200,199,198,197-----------4 hits

so total number of page faults in case2: 200+196=396 page faults

 

so the difference will be 0(Answer)

Comments

In case 1, why 4 didn't replaced 200?

In case 2,why FIFO page replacement policy is used when it is given in the question to use optimal page replacement policy?