Consider the page-reference string: 0 1 2 3 0 1 4 0 1 2 3 4. If the FIFO page-replacement algorithm is used, find the number of page faults for (a) 3 page frames and (b) 4 page frames, respectively.

Explanation

With 3 frames (FIFO queue, oldest evicted first): 0,1,2 fault and fill the frames [0,1,2]; 3 faults, evicting 0 → [1,2,3]; 0 faults, evicting 1 → [2,3,0]; 1 faults, evicting 2 → [3,0,1]; 4 faults, evicting 3 → [0,1,4]; the next 0 and 1 are hits; 2 faults, evicting 0 → [1,4,2]; 3 faults, evicting 1 → [4,2,3]; the final 4 is a hit — giving 9 faults in total. With 4 frames: 0,1,2,3 fault and fill [0,1,2,3]; the next 0 and 1 are hits; 4 faults, evicting 0 → [1,2,3,4]; 0 faults, evicting 1 → [2,3,4,0]; 1 faults, evicting 2 → [3,4,0,1]; 2 faults, evicting 3 → [4,0,1,2]; 3 faults, evicting 4 → [0,1,2,3]; the final 4 faults, evicting 0 — giving 10 faults in total. So the answer is 9, 10, option (iv) — a textbook example of Belady's anomaly, where adding a frame under FIFO actually increased the fault count.