Page Replacement Algorithms (FIFO vs. LRU) Explained

PRG November 14, 2025

🧠 OS Concepts Explained: Page Replacement Algorithms (FIFO vs. LRU)

Welcome, CSE students! Today we're tackling one of the most important concepts in Operating Systems: Page Replacement Algorithms.

What's the Big Idea?

In modern systems, we use Virtual Memory. This lets us pretend we have more RAM (physical memory) than we actually do. We do this by breaking programs into fixed-size chunks called pages.

  • Physical Memory is divided into frames.
  • When a program needs a page that isn't in a frame, the CPU triggers a Page Fault.
  • The OS must then load that page from the disk into a frame.

The Problem: What if all the frames are already full?
The Solution: A Page Replacement Algorithm decides which page to kick out (evict) to make room for the new one.

Let's solve the two classic examples you provided.

1. First-In, First-Out (FIFO)

The Logic: This is the simplest algorithm. It works like a queue. The page that has been in memory the longest (the "oldest" page) is the one we evict.

The Problem:

  • Reference String: 1, 3, 0, 3, 5, 6, 3
  • Page Frames: 3

Step-by-Step Solution:

We'll track the state of our 3 frames and mark Faults (F) and Hits (H).

  1. 1: [ 1, _, _ ] - Fault (1). Page 1 loaded.
  2. 3: [ 1, 3, _ ] - Fault (2). Page 3 loaded.
  3. 0: [ 1, 3, 0 ] - Fault (3). Page 0 loaded. (Frames are full)
  4. 3: [ 1, 3, 0 ] - Hit. Page 3 is already in memory.
  5. 5: [ 3, 0, 5 ] - Fault (4). Evict 1 (it was the first one in).
  6. 6: [ 0, 5, 6 ] - Fault (5). Evict 3 (it's now the oldest).
  7. 3: [ 5, 6, 3 ] - Fault (6). Evict 0 (it's now the oldest).

Final Result: There are a total of 6 Page Faults.

2. Least Recently Used (LRU)

The Logic: This algorithm evicts the page that has not been used for the longest period. We look back in time to see which page in memory is the "least recently used."

The Problem:

  • Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
  • Page Frames: 4

Step-by-Step Solution:

This is trickier. We'll track the frames. The "LRU" page will be on the left, and the "MRU" (Most Recently Used) page will be on the right.

  1. 7: [ 7, _, _, _ ] - Fault (1)
  2. 0: [ 7, 0, _, _ ] - Fault (2)
  3. 1: [ 7, 0, 1, _ ] - Fault (3)
  4. 2: [ 7, 0, 1, 2 ] - Fault (4). (Frames are full. LRU is 7)
  5. 0: [ 7, 1, 2, 0 ] - Hit. (Page 0 was used, so it moves to MRU. LRU is now 7)
  6. 3: [ 1, 2, 0, 3 ] - Fault (5). (Evict LRU page 7. LRU is now 1)
  7. 0: [ 1, 2, 3, 0 ] - Hit. (Page 0 moves to MRU. LRU is now 1)
  8. 4: [ 2, 3, 0, 4 ] - Fault (6). (Evict LRU page 1. LRU is now 2)
  9. 2: [ 3, 0, 4, 2 ] - Hit. (Page 2 moves to MRU. LRU is now 3)
  10. 3: [ 0, 4, 2, 3 ] - Hit. (Page 3 moves to MRU. LRU is now 0)
  11. 0: [ 4, 2, 3, 0 ] - Hit. (Page 0 moves to MRU. LRU is now 4)
  12. 3: [ 4, 2, 0, 3 ] - Hit. (Page 3 moves to MRU. LRU is now 4)
  13. 2: [ 4, 0, 3, 2 ] - Hit. (Page 2 moves to MRU. LRU is now 4)

Final Result: There are a total of 6 Page Faults.

💻 Dynamic Example: Try It Yourself!

Enter your own reference string and frame count to see how the algorithms perform.

Click a button to run a simulation...

🧠 Check Your Knowledge: Quick Quiz

Test your understanding! Click a button to see the answer.

Question 1:

Given string 1, 2, 3, 4 and 3 frames, which page will FIFO evict when 4 is loaded?

Question 2:

Given string 1, 2, 3, 2 and 2 frames, which pages are in memory at the end using LRU?

Question 3:

Which algorithm can suffer from Belady's Anomaly (where adding more frames increases page faults)?

Final Thoughts

As you can see, FIFO is simple to implement, but it's not very smart. It might kick out a page that's needed right away. LRU is much more intelligent (and often more efficient), but it's harder to implement in a real OS because it has to track when every page was used.

Keep practicing these examples!

Tags:
PRG

Posted by: PRG

Post a Comment

0 Comments