FIFO Page Replacement Policy (First-In, First-Out)

 

FIFO Page Replacement Policy (First-In, First-Out)

FIFO is one of the simplest page replacement policies.

🔹 Basic Idea

When a page must be removed, evict the page that has been in memory the longest.

It works like a queue:

• New pages enter at the rear

• Oldest page leaves from the front

---

Why Use FIFO?

✅ Very simple to implement
✅ Low overhead
❌ Does not consider usage patterns
❌ Can evict heavily used pages

---

Example 

Reference String:

0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1

Cache Size:

3 pages

---

🔄 Step-by-Step Execution

Access	Hit/Miss	Evicted	Cache State (Oldest → Newest)
0	Miss	—	0
1	Miss	—	0,1
2	Miss	—	0,1,2
0	Hit	—	0,1,2
1	Hit	—	0,1,2
3	Miss	0	1,2,3
0	Miss	1	2,3,0
3	Hit	—	2,3,0
1	Miss	2	3,0,1
2	Miss	3	0,1,2
1	Hit	—	0,1,2

---

Key Decisions Explained

📌 When page 3 arrives:

Cache = {0,1,2}
Oldest page = 0

➡ Evict 0
New cache = {1,2,3}

---

📌 When page 0 is accessed again:

0 was removed earlier.

Oldest page = 1

➡ Evict 1
New cache = {2,3,0}

---

FIFO simply removes the page that entered memory first — even if it was just used recently.

---

Hit Rate

• Hits = 4

• Misses = 7

$$Hit\ Rate = \frac{4}{11} = 36.4\%$$

Compare with Optimal:

• Optimal had 6 hits (54.6%)

FIFO performs worse because it makes replacement decisions without considering future or recent use.

---

 FIFO Weakness

FIFO can suffer from Belady’s Anomaly:

Increasing the number of frames can sometimes increase page faults.

This should not happen ideally — but FIFO can cause it.

---

 Summary

FIFO:

• Replaces the oldest page in memory

• Very easy to implement (queue)

• Ignores usage patterns

• Often performs worse than smarter policies like LRU or Optimal