📚 Page Replacement Algorithms

Complete Guide with Reasoning & Interview Preparation

🧠 Why Do We Need Page Replacement?

💡 The Core Problem

Physical Memory (RAM) is LIMITED - Programs need more memory than what's available

Solution: Virtual Memory - Use disk space as extended memory

Problem: When RAM is full, which page to remove to make space?

Program A
Program B
Program C
Which to remove?

🔄 Page Replacement Process

1
Page Fault Occurs: Program tries to access a page not in memory
2
Check Available Frames: Is there free space in memory?
3
If No Free Space: Choose a victim page to replace
4
Replace Page: Remove victim page, bring in new page
Goal: Minimize Page Faults = Minimize Disk Access = Better Performance
🚶‍♂️ FIFO (First In, First Out)

🤔 Why FIFO?

Reasoning: Oldest page might not be needed anymore

Assumption: Pages loaded long ago are less likely to be used again

Real-life analogy: Like a queue at a store - first person in line leaves first

📝 Step-by-Step Example

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Number of Frames: 3

Step 1
Page 7 → [7, -, -] (Page Fault)
Step 2
Page 0 → [7, 0, -] (Page Fault)
Step 3
Page 1 → [7, 0, 1] (Page Fault)
Step 4
Page 2 → [2, 0, 1] (Page Fault - Replace 7)
Step 5
Page 0 → [2, 0, 1] (Hit - No replacement)

✅ Advantages

  • Extremely simple to implement
  • Fair - every page gets equal treatment
  • Low overhead - just need to track insertion order
  • No complex calculations needed

❌ Disadvantages

  • Poor performance in practice
  • May remove frequently used pages
  • Suffers from Belady's Anomaly
  • Doesn't consider page usage patterns

⚠️ Belady's Anomaly - Interview Important!

What is it? Adding more frames sometimes increases page faults instead of decreasing them

Why does it happen? FIFO doesn't consider page usage - it only considers arrival time

Example: Reference string 1,2,3,4,1,2,5,1,2,3,4,5

  • 3 frames: 9 page faults
  • 4 frames: 10 page faults (MORE!)

💼 Interview Questions on FIFO

  • What is Belady's Anomaly? Which algorithms suffer from it?
  • Why is FIFO not optimal for page replacement?
  • How would you implement FIFO page replacement?
  • What data structure would you use for FIFO?
🎯 Optimal Page Replacement (OPT)

🤔 Why Optimal?

Reasoning: Replace page that will be used farthest in future

Logic: If we know the future, we can make perfect decisions

Goal: Minimize page faults by keeping most useful pages

📝 Step-by-Step Example

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Number of Frames: 3

Step 4
Need to replace one of [7, 0, 1] for page 2
Check
Page 7: Never used again | Page 0: Used at position 5 | Page 1: Never used again
Decision
Replace page 7 (or 1) - both never used again

✅ Advantages

  • Guaranteed minimum page faults
  • Best theoretical performance
  • Used as benchmark for other algorithms
  • No anomalies

❌ Disadvantages

  • Impossible to implement in practice
  • Requires complete future knowledge
  • Only theoretical importance
  • Can't predict program behavior

💡 Why Study Optimal if It's Impossible?

Benchmark: Compare real algorithms against optimal

Understanding: Shows the best possible performance

Algorithm Design: Inspires better heuristics

💼 Interview Questions on Optimal

  • Why is optimal page replacement impossible to implement?
  • How do you calculate optimal page replacement?
  • What's the difference between optimal and practical algorithms?
  • Why study optimal if it can't be implemented?
🕐 LRU (Least Recently Used)

🤔 Why LRU?

Reasoning: Recent past predicts near future

Principle of Locality: Recently used pages likely to be used again

Practical Approximation: Close to optimal in many cases

📝 Implementation Methods

📚 Stack Implementation
1
Page Access: Move page to top of stack
2
Replacement: Remove page from bottom
3
Data Structure: Doubly linked list
⏰ Counter Implementation
1
Page Access: Update timestamp
2
Replacement: Find oldest timestamp
3
Data Structure: Array with timestamps

📝 LRU Example with Stack

Reference String: 7, 0, 1, 2, 0, 3, 0

7
Stack: [7] (top)
0
Stack: [0, 7] (top to bottom)
1
Stack: [1, 0, 7]
2
Stack: [2, 1, 0] (Replace 7 - LRU)
0
Stack: [0, 2, 1] (Move 0 to top)

✅ Advantages

  • Good approximation of optimal
  • Exploits temporal locality
  • No Belady's Anomaly
  • Widely used in practice

❌ Disadvantages

  • Implementation overhead
  • Hardware support needed for efficiency
  • Complex data structures
  • May not work well for sequential access

💡 Why LRU Works Well

Temporal Locality: Programs tend to access recently used data again

Spatial Locality: Programs access nearby memory locations

Real-world Pattern: 80% of accesses to 20% of pages

💼 Interview Questions on LRU

  • How would you implement LRU page replacement?
  • What data structures are used for LRU?
  • Why is LRU better than FIFO?
  • What is the time complexity of LRU operations?
  • How does hardware support LRU?
🔢 Counting-Based Algorithms

🤔 Why Count References?

Idea: Track how often each page is used

LFU Logic: Rarely used pages can be replaced

MFU Logic: Heavily used pages might not be needed anymore

📉 LFU (Least Frequently Used)

Rule: Replace page with minimum reference count

Example:

  • Page A: 5 references
  • Page B: 2 references ← Replace this
  • Page C: 8 references

Problem: New pages always have low counts

📈 MFU (Most Frequently Used)

Rule: Replace page with maximum reference count

Logic: Heavily used pages might be done

Example:

  • Page A: 5 references
  • Page B: 2 references
  • Page C: 8 references ← Replace this

Problem: Often removes useful pages

💡 Why Counting Algorithms Are Rarely Used

LFU Problem: New pages always have low counts and get replaced immediately

MFU Problem: Removes pages that might still be heavily used

Poor Performance: Don't handle program phases well

Overhead: Need to maintain counters for all pages

💼 Interview Questions on Counting

  • What's the difference between LFU and MFU?
  • Why are counting algorithms rarely used?
  • What are the problems with LFU?
  • How would you implement reference counting?
🎯 Advanced Topics & Interview Prep

📊 Algorithm Comparison

Algorithm Page Faults Implementation Overhead Real-world Use
FIFO High Very Easy Low Rarely
Optimal Minimum Impossible - Theoretical
LRU Low Complex High Very Common
LFU Variable Medium Medium Rare
MFU