8.2 Page Replacement Algorithms: First-In, First-Out (FIFO) & Belady's Anomaly

Back to Operating Systems Notes

📚Module 08: Virtual Memory & Page ReplacementTopic 8.2⏱️18 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Algorithm Analysis

💡 Core Intuition

🍳 The Everyday Analogy: The Bakery Display Case

Imagine a boutique bakery with a counter display case that holds only three dessert trays:

Architecture Flow

The Bakery Tray Replacement Pipeline

Contrasting arrival-time eviction with customer demand patterns

💡 Hover or click any card for deep-dive operational details

🥐Rule of Order

Strict Chronological Queue

FIFO Policy

When a customer requests a chocolate croissant not on the counter, the baker throws away the tray that arrived earliest in the morning.

→

Counter-Intuitive Reality

🏪The Paradox

Adding a Fourth Shelf

Belady's Anomaly

The bakery expands the display case from 3 shelves to 4 shelves to satisfy more customers.

→

The Theoretical Root

📐Root Cause

Lack of Stack Property

Non-Stack Algorithm

FIFO does not guarantee that the set of items held in N shelves is a subset of N+1 shelves.

• First-In, First-Out (FIFO): The simplest page replacement policy. When a frame is needed, the page that has resided in physical memory the longest is evicted.
• Belady's Anomaly: The counter-intuitive phenomenon where increasing the number of physical memory frames causes the total number of page faults to increase rather than decrease!

---

💻 Bridging to Computer Science

When physical memory is fully saturated and a new page is referenced, the operating system must choose a victim page to evict.

The ideal eviction goal is simple: Evict the page that is least likely to be needed in the near future.

However, because the operating system cannot predict the future, it must use heuristics. The most elementary heuristic is First-In, First-Out (FIFO):

• Track the arrival timestamp of each page in memory.
• When a replacement is required, evict the oldest page.
• While trivial to implement with a FIFO circular queue, FIFO frequently discards heavily used core utility pages simply because they were loaded early during process startup.

---

📚 Core Deep-Dive & Concepts

1. The FIFO Page Replacement Algorithm

Algorithm Mechanics

1. Queue Maintenance: The OS maintains a FIFO queue of all physical frames currently resident in RAM.
2. On Page Fault:
   • If free frames exist: Load the incoming page into a free frame and push the frame index to the tail of the queue.
   • If memory is full: Pop the frame index from the head of the queue (the oldest page). Evict that page, load the incoming page into that frame, and append the frame index to the tail.
3. On Page Hit:
   • The page already resides in memory. The FIFO queue is completely unaffected! Arrival timestamps do not change on read or write references.

---

2. Comprehensive 20-Reference Trace

Let us trace the classic 20-reference workload with $3$ allocated physical frames:

$\text{Reference String: } \mathbf{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}$

Step	Page Ref	Frame 1	Frame 2	Frame 3	Event	Victim Evicted	Oldest Page in Queue
1	7	7	—	—	Fault	None (Cold)	7
2	0	7	0	—	Fault	None (Cold)	7
3	1	7	0	1	Fault	None (Cold)	7
4	2	2	0	1	Fault	7	0
5	0	2	0	1	Hit	None	0
6	3	2	3	1	Fault	0	1
7	0	2	3	0	Fault	1	2
8	4	4	3	0	Fault	2	3
9	2	4	2	0	Fault	3	0
10	3	4	2	3	Fault	0	4
11	0	0	2	3	Fault	4	2
12	3	0	2	3	Hit	None	2
13	2	0	2	3	Hit	None	2
14	1	0	1	3	Fault	2	3
15	2	0	1	2	Fault	3	0
16	0	0	1	2	Hit	None	0
17	1	0	1	2	Hit	None	0
18	7	7	1	2	Fault	0	1
19	0	7	0	2	Fault	1	2
20	1	7	0	1	Fault	2	7

Performance Summary for 3 Frames:

• Total References: $20$
• Total Page Faults: $\mathbf{15}$
• Total Page Hits: $\mathbf{5}$
• Hit Ratio: $\frac{5}{20} = \mathbf{25\%}$
• Fault Ratio: $\frac{15}{20} = \mathbf{75\%}$

---

3. Belady's Anomaly: The Memory Paradox

Intuition dictates that giving a process more physical RAM frames should either decrease the number of page faults or, in the worst case, leave it unchanged:

$\text{Intuitive Expectation: } \quad \text{Faults}(m + 1 \text{ frames}) \le \text{Faults}(m \text{ frames})$

In 1969, László Bélády proved that for certain replacement algorithms, this assumption is false!

Definition of Belady's Anomaly:
For certain page replacement algorithms (such as FIFO), the page fault rate may increase as the number of allocated physical frames increases for the exact same memory reference string.

---

4. Mathematical Demonstration of Belady's Anomaly

Consider the canonical 12-reference sequence:

$\text{Reference String: } \mathbf{1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}$

Case A: FIFO with 3 Physical Frames

Ref	1	2	3	4	1	2	5	1	2	3	4	5
F1	1	1	1	4	4	4	5	5	5	5	5	5
F2	—	2	2	2	1	1	1	1	1	3	3	3
F3	—	—	3	3	3	2	2	2	2	2	4	4
Hit/Fault	F	F	F	F	F	F	F	Hit	Hit	F	F	Hit

• Total Page Faults with 3 Frames: $\mathbf{9\text{ Faults}}$ (3 Hits: at references 1, 2, and 5).

---

Case B: FIFO with 4 Physical Frames (More Memory Allocated!)

Ref	1	2	3	4	1	2	5	1	2	3	4	5
F1	1	1	1	1	1	1	5	5	5	5	4	4
F2	—	2	2	2	2	2	2	1	1	1	1	5
F3	—	—	3	3	3	3	3	3	2	2	2	2
F4	—	—	—	4	4	4	4	4	4	3	3	3
Hit/Fault	F	F	F	F	Hit	Hit	F	F	F	F	F	F

• Total Page Faults with 4 Frames: $\mathbf{10\text{ Faults}}$ (Only 2 Hits: at references 1 and 2).

Allocated Physical Frames	Total Page Faults	Page Hits	Performance Outcome
$3\text{ Frames}$	$9\text{ Faults}$	$3\text{ Hits}$	Baseline reference for string
$4\text{ Frames}$	$10\text{ Faults}$	$2\text{ Hits}$	$+11.1\%$ Faults (Worse performance despite $+33\%$ physical frames!)

By adding an extra physical frame, the page fault count increased from 9 to 10!

---

5. Why Does Belady's Anomaly Occur? The Stack Property

To understand why FIFO fails, computer scientists classify page replacement algorithms into two categories:

---

🏭 In The Real World: Production Case Study

Second-Chance (Clock) Algorithm in Linux & BSD

Pure FIFO is rarely used in production kernels because of its terrible performance and Belady vulnerability. Instead, operating systems deploy the Second-Chance (Clock) Algorithm:

Architecture Flow

Second-Chance (Clock) Circular Pointer Traversal

Circular sweep evaluating hardware reference bits (R) before selecting eviction victim

🔄Slot 0

Frame 0 (R = 1)

Recently accessed. Hand clears bit to R = 0 (Second Chance granted).

→

Advance Hand

🎯Slot 1 (Target)

Frame 1 (R = 0)

Not accessed since last sweep. Selected as eviction victim!

→

Evicted & Replaced

🛡️Slot 2

Frame 2 (R = 1)

Active working-set page. Kept resident; reference bit cleared on next pass.

→

Advance Hand

⏳Slot 3

Frame 3 (R = 0)

Cold page awaiting next scan cycle if no immediate replacement occurs.

1. How Clock Operates:
   • Arranges physical frames in a circular circular buffer (a clock face).
   • A hand points to the oldest frame.
   • When eviction is required, the hand inspects the Reference Bit ($R$) set by hardware:
     • If $R == 1$: Clear $R \to 0$, advance hand to next frame (give it a "second chance").
     • If $R == 0$: Evict this frame immediately!
2. Production Balance:
   • Preserves the $\mathcal{O}(1)$ queue simplicity of FIFO while approximating the hit performance of LRU and dramatically suppressing Belady-style pathologies.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Which of the following page replacement algorithms can suffer from Belady's Anomaly?

1. Optimal (OPT)
2. Least Recently Used (LRU)
3. First-In, First-Out (FIFO)
4. Most Frequently Used (MFU)

Answer:

• FIFO (and algorithms that do not satisfy the stack property, such as pure FIFO and Random replacement) suffers from Belady's Anomaly.
• OPT and LRU are certified Stack Algorithms and can never suffer from Belady's Anomaly under any circumstance.

---

Question 2: Explain the formal definition of a "Stack Algorithm" in Operating Systems memory management. Answer: A page replacement algorithm is defined as a Stack Algorithm if for any given reference string and for all time $t$, the set of pages resident in physical memory with $m$ frames, denoted $B(m, t)$, is a strict subset of the set of pages resident in physical memory with $m + 1$ frames, denoted $B(m + 1, t)$:

$B(m, t) \subseteq B(m + 1, t) \quad \forall m \ge 1, \quad \forall t$

Because any page present in the $m$-frame system is guaranteed to also be present in the $(m+1)$-frame system, adding frames can never convert a page hit into a page fault. Hence, stack algorithms are provably immune to Belady's Anomaly.

Common Interview Traps

• The "More Memory Always Means Fewer Faults" Trap: When asked if adding RAM always reduces page faults, the answer is NO. Under FIFO replacement, Belady's Anomaly can cause page faults to increase.
• The Hit-Update Misconception in FIFO: In FIFO, when a page reference results in a Hit, DO NOT change its queue position! Its arrival timestamp remains the original time it was first loaded. Moving it to the tail converts the algorithm into LRU!

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic8.1 Demand Paging & Page FaultsNext Topic →8.3 Optimal Page Replacement