Least Frequently Used (LFU) Page Replacement Policy

 

Least Frequently Used (LFU) Page Replacement

🔹 Basic Idea

When memory is full and a page must be replaced:

🗑 Evict the page with the lowest access frequency.

• Each page keeps a counter

• Every time the page is accessed → counter++

• The page with the smallest count is removed

• If tie → typically break using LRU (least recently used among them)

---

Example 

Reference String:

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

Cache Size:

3 pages

(Tie-breaking using LRU)

---

🔄 Step-by-Step Execution

Access	Hit/Miss	Evicted	Cache State (with counts)
0	Miss	—	0(1)
1	Miss	—	0(1), 1(1)
2	Miss	—	0(1), 1(1), 2(1)
0	Hit	—	0(2), 1(1), 2(1)
1	Hit	—	0(2), 1(2), 2(1)
3	Miss		0(2), 1(2), 3(1)
0	Hit	—	0(3), 1(2), 3(1)
3	Hit	—	0(3), 1(2), 3(2)
1	Hit	—	0(3), 1(3), 3(2)
2	Miss	3	0(3), 1(3), 2(1)
1	Hit	—	0(3), 1(4), 2(1)

---

Key Replacement Decisions

🔹 When page 3 arrives:

Counts:

• 0 → 2

• 1 → 2

• 2 → 1

➡ Evict 2 (lowest frequency)

---

🔹 When page 2 arrives later:

Counts:

• 0 → 3

• 1 → 3

• 3 → 2

➡ Evict 3 (lowest frequency)

---

Performance

• Hits = 6

• Misses = 5

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

In this example, LFU performs as well as LRU and Optimal.

---

Strengths & Weaknesses

✅ Strengths

• Keeps frequently used pages

• Good for stable access patterns

• Exploits long-term locality

❌ Weaknesses

• Needs counters (extra overhead)

• Old pages with high counts may stay forever

• Not good if access pattern changes suddenly

---

Key Difference from LRU

LRU	LFU
Focuses on recent use	Focuses on number of uses
Short-term memory	Long-term memory