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

it will cause 180 page faults.

$1,2,3,.....100,\  20,21,22.....99$

total page faults = $100+99-20+1=180$

---

Page Faut for [1-100] + [20-99] = 180

---

Yes 180 miss

sequence of pages = 1,2,3,4...100,1,2,3,...100

Hence optimal page replacement will cause all 100 miss initially but due to future requests it never replace initial 1-19 pages.

Hence those 19 will be hit and then 100th page will be hit.

hence total 20 hits 180 miss.

---

Thank you everyone!

I was wondering why 100 wouldn't be replace?

Since in second 1 to 100 sequence 100 is going to be used although last,is never replaced.

and 1 to 19 will be replaced.Am I right?

---

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)