MadeEasy Test Series 2018: Operating System - Page Replacement

Question

Consider a computer system having 20 physical page frames numbered from 1 to 20 which are initially empty. Now, a program accesses the pages numbered 1, 2 ..........100 twice. The number of page fault generated by optimal page replacement policy is __________.

Comments

1 to 19 can be replaced, even you can replace any single location(among 1 to 19).

---

yes, before second turn pages which are already present are 1..19 and 100 so anyhow 100 is going to be used though it is last optimal will keep it in the frame.

---

check similar question https://gateoverflow.in/70912/gate-made-easy-mock-test

Answer 1

Initially 1 to 20 will be present (20 page fault)

now 20 will be replaced till end of first scan so at end of first scan we will have

1,2,3...19,100. (80 miss)

now 1 to 19 will be hit and for 20 we will replace 1 and so one

note that 100 will not be replaced as we are using optimal

so from 20 till 99 page fault and for 100 page hit

Total fault : 100+80=180

Total Hit: 20  (for 1,2,..19,100)