Random Page Replacement Policy

🔹 Basic Idea

When memory is full and a new page must be loaded:

🗑 Evict any page chosen at random.

No tracking of:

• Oldest page (like FIFO)

• Recently used page (like LRU)

• Future usage (like Optimal)

It simply picks a page randomly.

---

Why Use Random?

✅ Extremely simple to implement
✅ No bookkeeping overhead
❌ Makes no intelligent decisions
❌ Performance depends on luck

---

Example 

Reference String:

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

Cache Size:

3 pages

Since eviction is random, results can vary.
Below is one possible execution (from the table provided).

---

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

---

What Happened?

When page 3 arrived:

• Random chose to evict page 0

Later, when page 0 was needed:

• Random evicted page 1

Later, when page 1 was needed:

• Random evicted page 3

The decisions were purely random.

---

Performance in This Example

• Hits = 5

• Misses = 6

$$Hit\ Rate = \frac{5}{11} = 45.5\%$$

Compare:

Policy	Hits
Optimal	6
Random (this run)	5
FIFO	4

Random performs:

• Better than FIFO in this run

• Worse than Optimal

---

Important Observation

Random's performance depends on luck.

If we repeat the experiment thousands of times:

• Sometimes Random equals Optimal

• Sometimes it performs much worse

• Average performance falls somewhere in between

It has high variability.

---

Strengths vs Weaknesses

✅ Strengths

• Very easy to implement

• No tracking overhead

• No complex data structures

❌ Weaknesses

• Ignores usage patterns

• Can evict heavily used pages

• Unpredictable performance

---

Key Insight

Random does not try to be smart.

It works surprisingly decently sometimes,
but cannot consistently match intelligent policies like LRU.