FIFO Replacement
Evict the oldest page. Belady's anomaly is the interview sting.
Level: beginner
What is it?
FIFO page replacement evicts the page that has been resident the longest, regardless of how recently it was referenced. It is simple to implement with a queue or age order.
Why does it matter?
FIFO is useful for teaching the replacement problem and has low bookkeeping cost. Its weakness is that a frequently reused page can still be evicted just because it is old, and its fault count can increase when more frames are added.
Mental model
FIFO tracks admission order, not usefulness. Picture pages standing in a line: a hit does not move a page to the back; the oldest resident is next to leave.
How it works
- A page is placed at the tail when first loaded.
- A hit does not change its arrival order in pure FIFO.
- On a page fault with a full memory, the head page is evicted and the new page is appended.
- Belady's anomaly is a reference string for which increasing frame count increases FIFO page faults.
- Stack algorithms such as LRU do not exhibit this anomaly for the same reference string.
Steps
- Maintain a queue of resident page identities.
- On a reference, check whether the page is in the queue.
- On a miss with full memory, remove the oldest page, then add the requested page.
- Repeat exactly the same reference sequence when comparing frame counts.
Real-world usage
- Solving basic page-replacement problems.
- Understanding why recency and frequency can beat admission age.
- Explaining Belady's anomaly.
Common mistakes
- Updating FIFO order on every hit.
- Comparing reference strings with different initial conditions.
- Assuming more frames must reduce faults under every replacement policy.
Interview questions
Does a hit change the order in FIFO?
No. In pure FIFO, the order is based on when pages entered memory, not their subsequent accesses.
What is Belady's anomaly?
For some reference strings, FIFO experiences more page faults after the number of available frames is increased.