Day 68 – OS – Page Replacement Algorithms (FIFO, LRU)

Concept Notes

When multiple programs are running, your operating system (OS) must manage the main memory efficiently. But memory is limited — so when it becomes full, the OS must decide which page to remove to load a new one.
This decision is made using Page Replacement Algorithms.

Let’s understand this deeply, in a way every ECET aspirant can visualize.

---

🧱 1️⃣ What is a Page?

A page is a fixed-size block of data that represents a part of a process in virtual memory.
The memory is divided into small equal-sized frames.

Example:
If your RAM = 4 KB and page size = 1 KB → you can have 4 frames in main memory.

---

🧱 2️⃣ What is Page Replacement?

When a process tries to access a page not currently in memory, a page fault occurs.
If all frames are full, the OS must replace one of the existing pages with the new one.

This process is called Page Replacement.

---

🧱 3️⃣ Real-Life Example

Imagine your backpack can hold 4 books (frames).
You have 10 books (pages) in total.
Whenever you need a new book and your bag is full, you must remove one.

How do you choose which book to remove?
👉 That’s what Page Replacement Algorithms decide!

---

🧱 4️⃣ Page Replacement Algorithms

Two most common algorithms in ECET and GATE exams are:

🔹 FIFO (First In First Out)

• The oldest page in memory is replaced first.
• Works like a queue — the first page loaded is the first to go out.

Example:

Page reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Frames: 3

Step	Pages in Memory	Page Fault?
1	1	✅
2	1, 2	✅
3	1, 2, 3	✅
4	2, 3, 4	✅ (1 removed)
5	3, 4, 1	✅ (2 removed)
6	4, 1, 2	✅ (3 removed)
7	1, 2, 5	✅ (4 removed)

Total Page Faults = 7

🧠 Note: FIFO is simple but can cause Belady’s anomaly, where adding more frames can increase page faults!

---

🔹 LRU (Least Recently Used)

• Removes the page that has not been used for the longest time.
• Works like our memory: “I’ll remove what I haven’t used recently.”

Example:

Page reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Frames: 3

Step	Pages in Memory	Page Fault?
1	1	✅
2	1, 2	✅
3	1, 2, 3	✅
4	2, 3, 4	✅
5	2, 3, 4	❌ (1 recently used, no replacement)
6	3, 4, 2	❌
7	4, 2, 5	✅
8	2, 5, 1	✅

Total Page Faults = 6

LRU performs better than FIFO in most cases because it uses recent history.

---

🧩 5️⃣ Diagram (Explained in Words)

Imagine 3 empty boxes (frames).
Each incoming number (page) fills one box.
When a new page comes in and all boxes are full:

• In FIFO, remove the leftmost box (oldest).
• In LRU, remove the box that hasn’t been touched for longest.

Visualize arrows showing “new → old → oldest” order.

---

🧠 6️⃣ Exam-Important Points

✅ FIFO → Simple, may suffer Belady’s anomaly
✅ LRU → Based on recent usage, fewer page faults
✅ Optimal Algorithm (for theory) → Replace page not used for longest future time
✅ Page Fault → When required page not in memory
✅ Page Hit → When page is already present

---

⚙️ Formulas

---

🔟 10 MCQs (ECET + GATE Hybrid)

1. In FIFO, which page is replaced first?
   A) Least used
   B) Oldest page
   C) Recently used
   D) Random page
2. Which of the following may cause Belady’s anomaly?
   A) LRU
   B) FIFO
   C) Optimal
   D) None
3. LRU algorithm replaces the page that:
   A) Has been used recently
   B) Was used first
   C) Has not been used recently
   D) Was just loaded
4. Which of the following is true for LRU?
   A) Complex to implement
   B) Suffers from anomaly
   C) Doesn’t consider usage
   D) Random replacement
5. Page fault occurs when:
   A) Page is in memory
   B) Page is not in memory
   C) Page replaced recently
   D) All are true
6. FIFO works similar to:
   A) Queue
   B) Stack
   C) Linked list
   D) Tree
7. LRU requires tracking of:
   A) Oldest page
   B) Page usage time
   C) Frame number
   D) Page size
8. Which is more efficient?
   A) FIFO
   B) LRU
   C) Random
   D) None
9. The phenomenon where page faults increase with more frames is called:
   A) Thrashing
   B) Fragmentation
   C) Belady’s anomaly
   D) Overhead
10. In page replacement, memory is divided into:
    A) Blocks
    B) Frames
    C) Segments
    D) Tables

---

✅ Answer Key

Q No | Answer
1 | B
2 | B
3 | C
4 | A
5 | B
6 | A
7 | B
8 | B
9 | C
10 | B

---

🧠 MCQ Explanations

1️⃣ FIFO replaces the oldest page, so (B) is correct.
2️⃣ Belady’s anomaly occurs in FIFO, not in LRU.
3️⃣ LRU removes the page least recently used, hence (C).
4️⃣ LRU needs time-tracking, so it’s complex to implement → (A).
5️⃣ Page fault means the page is not in memory → (B).
6️⃣ FIFO follows queue order → (A).
7️⃣ LRU tracks last usage time of each page → (B).
8️⃣ LRU generally gives fewer page faults → (B).
9️⃣ Belady’s anomaly → when increasing frames increases faults → (C).
10️⃣ Memory is divided into frames in paging → (B).

---

🎯 Motivation (ECET 2026 Focus)

Page Replacement is one of the most frequently asked OS topics in ECET, GATE, and campus placements.
Every year, 1–2 questions come directly from FIFO or LRU concepts.
If you master these, you’ll easily score 2–3 direct marks and strengthen your OS fundamentals.
Stay consistent — small daily practice = big ECET rank boost! 🚀

---

📲 CTA

Join our ECET 2026 CSE WhatsApp Group for daily quizzes & study notes:
👉 https://chat.whatsapp.com/GniYuv3CYVDKjPWEN086X9

Download as PDF