FIFO Page Replacement Explained: Step-by-Step Fault Counting and Belady's Anomaly
Learn a reliable FIFO queue method, trace every hit and fault across a complete example, and see why adding a frame can sometimes increase the fault count.
KnowledgeGate Team
Exam prep & CS education

FIFO page replacement is easy to define, but easy to calculate wrongly. One untracked hit or incorrect queue update changes every later eviction and the final count. A clean queue method, a fresh 12-reference trace, an exact Belady anomaly counterexample, and exam-style checks make every result auditable.
FIFO page replacement from zero
A page is a block of virtual memory, while a physical frame is a slot in main memory that can hold one page. A reference string records the requested pages in order. If the requested page is resident, the access is a page hit. If it is absent, the access is a page fault.
On a fault, the operating system loads the missing page. An empty-frame fault needs no eviction. Replacement starts only when a fault occurs after every available frame is occupied.
FIFO keeps resident pages in a queue ordered by when they entered memory. The page at the front, the oldest arrival, is the next victim. A hit does not remove or re-enqueue a page. It does not make that page new again. Frame slots show where pages currently sit, but queue order decides age.
The queue method that prevents counting errors
For every reference, apply these rules in order:
If the page is present, mark H and change nothing.
If it is absent and an empty frame exists, mark F, load it, and append it to the queue.
If it is absent and all frames are full, mark F, remove the queue front, replace that page, and append the new page.
Use a scratch table with step, reference, F1, F2, F3, queue oldest to newest, H/F, and evicted. Update the queue only on a fault.
For a quick check, three empty frames and 7, 0, 1, 7 produce F, F, F, H. After the final hit, the frames are still [7, 0, 1], and the queue is still 7 -> 0 -> 1.
Worked example: count FIFO faults with three frames

Consider three initially empty frames and this reference string:
2, 1, 2, 3, 4, 2, 5, 1, 2, 4, 5, 3
Use FIFO and count initial loads as faults. In the table, - means an empty frame, and the queue runs from oldest to newest.
Step | Ref | F1 | F2 | F3 | Queue, oldest to newest | Result | Evicted |
|---|---|---|---|---|---|---|---|
1 | 2 | 2 | - | - | 2 | F | - |
2 | 1 | 2 | 1 | - | 2 -> 1 | F | - |
3 | 2 | 2 | 1 | - | 2 -> 1 | H | - |
4 | 3 | 2 | 1 | 3 | 2 -> 1 -> 3 | F | - |
5 | 4 | 4 | 1 | 3 | 1 -> 3 -> 4 | F | 2 |
6 | 2 | 4 | 2 | 3 | 3 -> 4 -> 2 | F | 1 |
7 | 5 | 4 | 2 | 5 | 4 -> 2 -> 5 | F | 3 |
8 | 1 | 1 | 2 | 5 | 2 -> 5 -> 1 | F | 4 |
9 | 2 | 1 | 2 | 5 | 2 -> 5 -> 1 | H | - |
10 | 4 | 1 | 4 | 5 | 5 -> 1 -> 4 | F | 2 |
11 | 5 | 1 | 4 | 5 | 5 -> 1 -> 4 | H | - |
12 | 3 | 1 | 4 | 3 | 1 -> 4 -> 3 | F | 5 |
Count only the F entries. Steps 1, 2, 4, 5, 6, 7, 8, 10, and 12 are faults. Steps 3, 9, and 11 are hits. Therefore:
Page faults = 9
Page hits = 3
Page-fault ratio = 9/12 = 3/4 = 0.75 = 75%
Hit ratio = 3/12 = 1/4 = 0.25 = 25%
Why one extra frame can cause more faults
Fault counting and cross-algorithm comparison are different jobs. Page Replacement Algorithms for GATE: FIFO, LRU, Optimal compares FIFO, LRU, and Optimal on one shared string. A FIFO-only audit instead exposes the queue-state change that proves the anomaly.
Use the classic anomaly string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with initially empty frames. With three frames, steps 8, 9, and 12 hit, so the run has 9 faults. With four frames, only steps 5 and 6 hit, so the run has 10 faults.
At step 8, the three-frame resident set is {1, 2, 5}, while the four-frame resident set is {1, 3, 4, 5}. Page 2 is present in the smaller run but absent from the larger one, so step 9 hits with three frames and faults with four.
The increase from 9 to 10 faults after adding a frame is Belady's anomaly. It can occur with FIFO, but not every reference string shows it.
FIFO is not a stack algorithm: the pages retained with three frames do not have to form a subset of those retained with four frames. Without that subset guarantee, an extra frame can change the arrival and eviction order in a way that creates another fault.

Common FIFO traps and how to correct them
Treating a hit as a fresh arrival: For
1, 2, 3, 1, 4with three frames, the second1is a hit. The queue remains1 -> 2 -> 3, so4evicts1, not2.Counting only replacements: The first three accesses in the main example are faults even though they fill empty frames and evict nothing.
Reading the leftmost frame as the oldest: After step 10, the frames are
[1, 4, 5], but the queue is5 -> 1 -> 4. Page5is next to leave.Using the wrong denominator: The fault ratio uses all 12 references, not only the faults.
Mixing algorithms or frame counts: Keep the frame count fixed during one run. Unlike LRU, FIFO does not update age after recent use.
How exam-style questions test FIFO
FIFO problems commonly take four useful shapes:
Direct fault count: The main three-frame trace has
9faults.Frame and victim after a prefix: After step 10, frames are
[1, 4, 5]and the queue is5 -> 1 -> 4, so page5is next.Anomaly comparison: The classic anomaly string gives
9faults with three frames and10with four.Hit-order trap: For
1, 2, 3, 1, 4with three frames, page1is evicted.
Before accepting an answer, check that the number of H/F results equals the number of references. Every hit must name a resident page. Every fault with full frames must have exactly one eviction. The queue length must never exceed the frame count, and hits must not alter its order.
Then test the method on Page Replacement Algorithms MCQs: FIFO, LRU, Optimal without looking back at the trace.
FIFO in the short version and what to study next
Keep pages in arrival order.
Count every miss as a fault.
Replace a page only when the frames are full.
Never refresh the FIFO queue on a hit.
Write the complete H/F row before summing.
Use the CS Fundamentals category for the wider subject map. Choose Zero to Hero for a structured college-level CS foundation, or CS Fundamentals for Placements by Sanchit Sir for Operating Systems revision before technical interviews.
Next, redraw the 12-reference table from memory, verify every queue update, then solve the linked MCQs without the rules.
Keep learning
Page Replacement Algorithms for GATE: FIFO, LRU and Optimal with Belady's Anomaly Explained
One shared reference string traced fault by fault through FIFO, LRU and Optimal page replacement with 3 frames, then re-run under FIFO with 4 frames to demonstrate Belady's anomaly. Includes the counting rules GATE expects, why LRU beating FIFO is a tendency and not a theorem, and the stack-algorithm property that makes LRU and Optimal immune to the anomaly.
Optimal Replacement MCQs: 10 Solved Questions with Step-by-Step Page-Fault Explanations
Solve 10 Optimal Replacement questions from GATE, ISRO, HTET, UPPSC and DSSSB papers, then check each answer against a full three-frame page-fault trace.
FIFO Page Replacement MCQs: 12 Solved Questions with Step-by-Step Explanations
Practise FIFO carefully through 12 questions on hits, faults, preloaded frames, reverse reference strings, queue traces, and Belady's anomaly.
LRU Page Replacement MCQs: 12 Solved Questions with Page-Fault Traces
Solve 12 LRU questions with checked hit-fault traces, victim choices, policy comparisons, and one address-to-page conversion.





