Beyond Physical Memory: Page Replacement Policies 

When there is plenty of free memory, handling a page fault is easy:

1. A page fault happens.

2. The OS finds a free frame.

3. It loads the page into memory.

4. Done ✅

But things get more interesting when memory is full.

---

The Core Problem

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

❓ Which page should the OS remove (evict)?

This decision is made by the replacement policy.

This is one of the most important decisions in virtual memory systems.

---

Memory as a Cache

Main memory (RAM) can be viewed as:

A cache for all virtual memory pages stored on disk.

So the goal of a replacement policy is:

• ✅ Maximize cache hits

• ❌ Minimize cache misses (page faults)

Because every miss requires a slow disk access.

---

Why Misses Are So Expensive

We measure performance using:

📌 Average Memory Access Time (AMAT)

$$AMAT = (Hit\% \times T_M) + (Miss\% \times T_D)$$

Where:

• $T_M$= Time to access memory (RAM)

• $T_D$ = Time to access disk

• Hit% = Probability page is in memory

• Miss% = Probability page is not in memory

---

Example Calculation

Assume:

• Memory access time = 100 nanoseconds

• Disk access time = 10 milliseconds

⚠ Important:

• 1 millisecond = 1,000,000 nanoseconds

• Disk is about 100,000× slower than memory

---

Case 1: 90% Hit Rate

• Hit% = 0.9

• Miss% = 0.1

$$AMAT = (0.9 \times 100ns) + (0.1 \times 10ms)$$
$$= 90ns + 1ms$$

≈ 1 millisecond

Even though 90% of accesses are fast,
the 10% disk accesses dominate.

---

Case 2: 99.9% Hit Rate

• Hit% = 0.999

• Miss% = 0.001

$$AMAT = (0.999 \times 100ns) + (0.001 \times 10ms)$$
$$≈ 99.9ns + 10µs$$

≈ 10.1 microseconds

This is about 100× faster than the 90% case.

---

Key Insight

Even a tiny miss rate dramatically increases overall access time.

Because:

Component	Time
RAM	100 ns
Disk	10 ms

Disk dominates performance.

---

 Small Address Space Example (Concept)

Given:

• Address space = 4KB

• Page size = 256 bytes

• Total pages = 16

Suppose:

• All pages are in memory except page 3.

• The program accesses 10 pages.

• Only one reference is to page 3.

So we get:

Hit, Hit, Hit, Miss, Hit, Hit, Hit, Hit, Hit, Hit

Hit rate = 9/10 = 90%

Even with just one miss,
the average time becomes close to disk speed.

---

Why Replacement Policy Matters

Since disk is so slow:

The OS must choose very carefully which page to evict.

A bad choice:

• Evicts a page that is needed soon

• Causes another page fault

• Leads to poor performance

A good choice:

• Evicts a page unlikely to be used again

• Keeps hit rate high

• Keeps AMAT low

---

Big Picture

When memory is full:

1. A page fault occurs.

2. OS must pick a victim page.

3. That decision affects:

   • Hit rate

   • Miss rate

   • AMAT

   • Overall system performance

---

Final Takeaway

• RAM acts like a cache for disk.

• Disk is extremely slow.

• Even small miss rates hurt performance badly.

• Therefore:

  Designing a smart page replacement policy is critical for system performance.