What is the FIFO Page Replacement Algorithm?
Learn how FIFO page replacement works, its Belady’s anomaly weakness, and how it compares to LRU, with OS interview questions.
Expected Interview Answer
First-In-First-Out (FIFO) page replacement evicts the page that has been resident in memory the longest, regardless of how recently or frequently it has actually been used.
FIFO maintains a simple queue of resident pages ordered by load time: a new page joins the tail, and whenever a frame must be freed, the page at the head of the queue — the oldest resident page — is evicted. This makes FIFO trivial to implement with O(1) overhead per access, since no reordering happens on a reference, only on a fault. Its major weakness is that “oldest” is a poor proxy for “least useful”: a page loaded early but still accessed constantly (like a frequently used code page) can be evicted purely because of its age, while a page loaded recently but never touched again stays. FIFO is also the classic example used to demonstrate Belady’s anomaly, where adding more physical frames can, counterintuitively, increase the total number of page faults for certain reference strings.
- Extremely simple to implement — a plain queue, O(1) per operation
- No per-access bookkeeping overhead, unlike LRU
- Useful teaching baseline for comparing replacement quality
- Predictable, deterministic eviction order given a reference string
AI Mentor Explanation
FIFO page replacement is like a squad rotation policy that always drops whichever player was selected to the squad earliest, no matter how well they are currently performing. A star all-rounder picked in the first training camp gets dropped purely for being the longest-serving squad member, even while in career-best form. Meanwhile a bench player added last week who has not played a single match stays untouched. This shows FIFO’s core flaw: it tracks time-in-squad, not actual usefulness.
Step-by-Step Explanation
Step 1
Page loaded
When a page is brought into memory, it is appended to the tail of a FIFO queue.
Step 2
Fault with no free frame
A page fault occurs and every frame is occupied, requiring a victim to be chosen.
Step 3
Dequeue oldest page
The page at the head of the queue — the one resident longest — is selected as the victim, regardless of recent use.
Step 4
Evict and enqueue new page
The victim is evicted (written back if dirty), and the newly loaded page joins the tail of the queue.
What Interviewer Expects
- A definition tied to residency time, not access recency or frequency
- Knowledge that FIFO can evict a heavily used page purely because it is old
- Awareness of Belady’s anomaly and FIFO as its classic demonstration algorithm
- Recognition that FIFO is simple (O(1)) but generally lower quality than LRU
Common Mistakes
- Confusing FIFO with LRU (residency time vs. access recency)
- Assuming FIFO always performs worse than LRU in every case (it can occasionally tie or even edge it, though generally it underperforms)
- Not knowing FIFO is the standard example for demonstrating Belady’s anomaly
- Thinking FIFO reorders pages on reference — it only changes order on load or eviction
Best Answer (HR Friendly)
“FIFO page replacement simply removes whichever page has been sitting in memory the longest, like a queue — first one in is the first one kicked out, no matter how often it is still being used. It is very cheap to implement, but that simplicity means it can accidentally evict pages that are still heavily needed just because they happened to load early, which is why more usage-aware algorithms like LRU usually perform better in practice.”
Code Example
#define NUM_FRAMES 4
int frame_queue[NUM_FRAMES];
int queue_head = 0; /* index of the oldest resident page’s frame */
int frames_used = 0;
int load_page(int page_id, int frames[]) {
int victim_frame;
if (frames_used < NUM_FRAMES) {
victim_frame = frames_used++;
} else {
victim_frame = queue_head; /* oldest frame, FIFO order */
queue_head = (queue_head + 1) % NUM_FRAMES;
}
frames[victim_frame] = page_id; /* load new page, evicting old */
return victim_frame;
}Follow-up Questions
- What is Belady’s anomaly, and how does FIFO demonstrate it?
- Why might a frequently used page still get evicted under FIFO?
- How does the second-chance (clock) algorithm improve on plain FIFO?
- In what scenario would FIFO and LRU produce identical eviction sequences?
MCQ Practice
1. FIFO page replacement evicts the page that is?
FIFO tracks only load order — the page that has been resident the longest is evicted, even if it is still actively used.
2. Belady’s anomaly refers to?
Belady’s anomaly is the counterintuitive result where giving FIFO more frames can increase, not decrease, the total page faults for some reference strings.
3. What is the main implementation advantage of FIFO over LRU?
FIFO only needs to track load order via a queue, with no bookkeeping on every reference, making it far cheaper than exact LRU.
Flash Cards
What does FIFO page replacement evict? — The page that has been resident in memory the longest, regardless of usage.
What data structure implements FIFO replacement? — A simple queue ordered by page load time.
What anomaly is FIFO famous for demonstrating? — Belady’s anomaly — more frames can increase page faults.
Why is FIFO cheap to implement? — It needs no per-access reordering, only updates on load and eviction, giving O(1) overhead.