Optimal Page Replacement Policy (Belady’s MIN)

The Optimal Page Replacement Policy, proposed by Belady, replaces:

🗑 The page that will be used farthest in the future.

This policy guarantees the minimum possible number of page faults.

However:

• ❌ It requires knowing the future memory accesses.

• ❌ Not implementable in real operating systems.

• ✅ Used as a benchmark to compare other policies.

---

Why Is It Optimal?

If you must remove a page, the smartest choice is:

Remove the one that won’t be needed for the longest time.

That way:

• All remaining pages will be used sooner.

• You delay future page faults as much as possible.

---

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
0	Miss	—	0
1	Miss	—	0,1
2	Miss	—	0,1,2
0	Hit	—	0,1,2
1	Hit	—	0,1,2
3	Miss	2	0,1,3
0	Hit	—	0,1,3
3	Hit	—	0,1,3
1	Hit	—	0,1,3
2	Miss	3	0,1,2
1	Hit	—	0,1,2

---

Key Replacement Decisions

📌 When page 3 is accessed

Cache = {0,1,2}

Look into the future:

• 0 → used soon

• 1 → used soon

• 2 → used much later

➡ Evict 2

---

📌 When page 2 is accessed again

Cache = {0,1,3}

Look into future:

• 1 → used immediately

• 0 → not used again

• 3 → not used again

Either 0 or 3 can be evicted.

Example evicts 3.

---

Hit Rate Calculation

• Hits = 6

• Misses = 5

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

If we ignore compulsory misses (first-time accesses), hit rate improves significantly.

---

 Types of Misses (Related Concept)

1. Compulsory Miss

   • First time accessing a page.

   • Cache was empty.

2. Capacity Miss

   • Cache too small.

   • Must evict something.

3. Conflict Miss

   • Happens in hardware caches due to placement restrictions.

   • Does not apply to OS page replacement.

---

 Final Takeaways

• Optimal replaces the page used farthest in the future.

• Produces the fewest possible page faults.

• Cannot be implemented in practice (future unknown).

• Used as a benchmark to evaluate real policies.