SSC IMD SA 2017 – Question 127

A process references 5 pages A, B, C, D, and E in the order: A, B, C, D, A, B, E, A, B, C, D, E.
If the page replacement algorithm is FIFO, the number of page transfers with an empty internal store of 4 frames is

• 9
• 10
• 11
• 12

Detailed Explanation:

The correct answer is b) 10.

Belady’s Anomaly Reference String Trace (4 Frames, FIFO):
Reference String: A, B, C, D, A, B, E, A, B, C, D, E

1. Ref A: Page fault $\rightarrow$ [A, -, -, -] (Fault 1)
2. Ref B: Page fault $\rightarrow$ [A, B, -, -] (Fault 2)
3. Ref C: Page fault $\rightarrow$ [A, B, C, -] (Fault 3)
4. Ref D: Page fault $\rightarrow$ [A, B, C, D] (Fault 4)
5. Ref A: Hit $\rightarrow$ [A, B, C, D]
6. Ref B: Hit $\rightarrow$ [A, B, C, D]
7. Ref E: Page fault $\rightarrow$ replaces oldest (A) $\rightarrow$ [E, B, C, D] (Fault 5)
8. Ref A: Page fault $\rightarrow$ replaces oldest (B) $\rightarrow$ [E, A, C, D] (Fault 6)
9. Ref B: Page fault $\rightarrow$ replaces oldest (C) $\rightarrow$ [E, A, B, D] (Fault 7)
10. Ref C: Page fault $\rightarrow$ replaces oldest (D) $\rightarrow$ [E, A, B, C] (Fault 8)
11. Ref D: Page fault $\rightarrow$ replaces oldest (E) $\rightarrow$ [D, A, B, C] (Fault 9)
12. Ref E: Page fault $\rightarrow$ replaces oldest (A) $\rightarrow$ [D, E, B, C] (Fault 10)

Total page faults (transfers) = 10.

Historical Context: This is László Bélády’s classic 1969 counterexample demonstrating Bélády’s Anomaly: with 3 frames, this sequence produces 9 page faults, but allocating 4 frames paradoxically increases page faults to 10!