A system uses FIFO page replacement policy. 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
GATE 2010 · Operating System · Page Replacement · medium
Answer: 196 page faults. Answer: A. 196
Forward pass: access pages 1 to 100: Pages 1, 2, ..., 100 are all distinct and none pre-loaded. Every access is a fault. With 4 frames, the FIFO queue after loading all 100 pages holds the last 4: pages 97, 98, 99, 100 (97 being the oldest in the queue).
Faults in forward pass = 100.
Reverse pass: access pages 100, 99, ..., 1: Reverse order: 100, 99, 98, 97, 96, 95, ..., 1.
Access 100: hit (in frames). Access 99: hit. Access 98: hit. Access 97: hit.
Access 96: miss. FIFO evicts 97 (oldest). frames=[98,99,100,96].
Access 95: miss. FIFO evicts 98. frames=[99,100,96,95].
... continuing, each page from 96 down to 1 is a miss (96 total faults in this segment).
Faults in reverse pass = 96.