Least Recently Used (LRU) Page Replacement Policy

 

Least Recently Used (LRU) Page Replacement

🔹 Basic Idea

When memory is full and a page must be replaced:

🗑 Evict the page that was used least recently.

LRU assumes:

• If a page was used recently → it will likely be used again soon

• If a page has not been used for a long time → it is less important

This is based on temporal locality.

---

Why LRU Works

Programs usually:

• Reuse variables

• Run loops repeatedly

• Access the same data structures again

This behavior is called the Principle of Locality:

• Temporal locality → Recently used pages are likely to be reused

• Spatial locality → Nearby pages are likely to be accessed

LRU uses history to predict the future.

---

Example 

Reference String:

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

Cache Size:

3 pages

---

🔄 Step-by-Step Trace

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

---

Key Replacement Decisions

🔹 When page 3 arrives:

Cache = 0,1,2

Recently used order:

• 1 → most recent

• 0 → recent

• 2 → least recent

➡ LRU evicts 2

---

🔹 When page 2 arrives later:

Cache = 0,3,1

Recently used order:

• 1 → most recent

• 3 → recent

• 0 → least recent

➡ LRU evicts 0

---

Performance

• Hits = 6

• Misses = 5

$$Hit\ Rate = \frac{6}{11} = 54.5\%$$

LRU matches Optimal in this example.

---

Comparison With Other Policies

Policy	Strategy	Intelligent?	Hits (example)
FIFO	Oldest page out	❌ No	4
Random	Random eviction	❌ No	5 (varies)
LRU	Least recently used	✅ Yes	6
Optimal	Replace farthest future use	✅ Perfect	6

---

✅ Strengths of LRU

• Uses history

• Exploits temporal locality

• Usually performs close to Optimal

• Works well in real programs

---

❌ Weaknesses

• Requires tracking usage history

• More overhead than FIFO or Random

• Not perfect for all workloads

---

Final Insight

LRU is powerful because:

It uses the past to predict the future.

In this example, its decisions were correct every time, giving it optimal performance.