-
A system uses FIFO policy for page replacement. It has 4 frames with no page loaded to begin with. The system first accesses 100 distinct pages in same order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?
-
- 196
- 192
- 197
- 195
- 196
Correct Option: A
The First In First Out (FIFO) page replacement algorithm is a low-overhead algorithm. In FIFO, the operating system keeps track of all the pages in memory in a queue. The queue is managed in a way that the most recent arrival is placed at the back, and the earliest arrival in front. T the time of page replacement, oldest page is selected to get replaced. Practical implementation of FIFO is not very good as the algorithm experiences Belady’s anomaly.
Given are 4 page frames. The 100 pages are accessed in some order → 1 to 100 pages will get 100 faults. Now, after the pages are accessed, they are to be accessed in reverse order. But in reverse, there won’t be any fault for page numbers 100, 99, 98, 97.
Therefore, all page frames are occupied. Now, for remaining 96 accesses, 96 faults would occur.
Total 100 (Direct access) + 96 (Reverse access) = 196
Alternate method
Fault of n pages = 2n – 4
So, for 100 pages = 2 × 100 – 4 = 196
