GATE CSE 2010 | Question: 24

Question

A system uses FIFO policy for system replacement. It has $4$ page frames with no pages loaded to begin with. The system first accesses $100$ distinct pages in some order and then accesses the same $100$ pages but now in the reverse order. How many page faults will occur?

• A. $196$
• B. $192$
• C. $197$
• D. $195$

Comments

same number of page faults  for any other algo (LRU , OPT)

Answer 1

Answer is (A).

When we access $100$ distinct page in some order (for example $1,2,3\ldots 100$) then total number of page faults $=100$. At last, the $4$ page frames will contain the pages $100,99,98$ and $97$. When we reverse the string $(100,99,98,\ldots,1)$ then first four page accesses will not cause the page fault because they are already present in page frames. But the remaining $96$ page accesses will cause $96$ page faults. So, total number of page faults $=100+96=196$.

Comments

$\text{Page fault} = 100 + 96\:\text{(reverse order)} = 196$

---

Why first four misses are not included even though frame is empty ?

---

Please look carefully included,

in the first time all 100 frames are included as a fault but while in reverse order 100, 99, 98, 97 are not included(as they hits) so, in reverse order only 96 faults, 100+96= 196 total page faults

Answer 2

Answer will be "196" first 100 page fault will occur then 4 page hit after that 96 page fault total =100+96

If you want to visualize how this mapping take small value and check

1)Lets take 5 district element and its reveverse then page fault 5(page fault) + 4(page hit)+1 (page fault)

Total page fault=6

2) let's take 10 district element and its reveverse then 10(page fault)+4(page hit) +6(page fault)

Total page fault=16

Comments

Nice Explanation