Comparison of Page Replacement Policies

Page replacement policies decide which page to remove when memory is full.

Below is a clear comparison of the most common ones.

---

1️⃣ FIFO (First-In, First-Out)

Idea:
Evict the page that entered memory first.

✔ Pros

• Very simple

• Easy to implement (queue)

✖ Cons

• Ignores usage pattern

• Can remove important pages

• Suffers from Belady’s anomaly

🧠 Intelligence Level: Low

---

2️⃣ Random

Idea:
Evict any page chosen randomly.

✔ Pros

• Extremely simple

• No bookkeeping overhead

✖ Cons

• Completely ignores locality

• Performance depends on luck

• Unpredictable

🧠 Intelligence Level: Very Low

---

3️⃣ LRU (Least Recently Used)

Idea:
Evict the page that was not used for the longest time.

✔ Pros

• Uses history

• Exploits temporal locality

• Usually performs close to optimal

✖ Cons

• More overhead (must track usage)

• Hard to implement perfectly in hardware

🧠 Intelligence Level: High

---

4️⃣ LFU (Least Frequently Used)

Idea:
Evict the page with the lowest access count.

✔ Pros

• Keeps frequently used pages

• Uses long-term history

✖ Cons

• Old pages with high counts may stay forever

• Needs counters

• Less adaptive to changing patterns

🧠 Intelligence Level: Medium–High

---

5️⃣ Optimal (MIN)

Idea:
Evict the page that will not be used for the longest time in the future.

✔ Pros

• Best possible performance

• Theoretical benchmark

✖ Cons

• Impossible to implement in real systems (requires future knowledge)

🧠 Intelligence Level: Perfect (Theoretical)

---

Summary Table

Policy	Basis for Decision	Uses History?	Overhead	Performance	Practical?
FIFO	Arrival time	❌	Low	Poor–Average	✅ Yes
Random	Random choice	❌	Very Low	Variable	✅ Yes
LRU	Recent usage	✅ (short-term)	Medium	Very Good	✅ Yes
LFU	Frequency count	✅ (long-term)	Medium–High	Good	✅ Yes
Optimal	Future knowledge	Future info	—	Best	❌ No

---

Key Insight

• FIFO & Random → Simple but unintelligent

• LRU & LFU → Use locality principle

• Optimal → Ideal but unrealistic

---

In Practice

Modern systems often use:

• Approximations of LRU

• Clock / Second-Chance algorithms (efficient LRU variants)