The Page Replacement Problem

In Section 3, we saw that a page fault occurs when a process accesses a page not currently in RAM. The OS must load the page from disk into a free frame. But what happens when there are no free frames — when every frame in RAM is occupied by some page of some process?

The OS must choose a victim page — an existing page in RAM to evict (write back to disk if necessary, then overwrite with the new page). The algorithm for choosing the victim is the page replacement algorithm, and it directly determines the system's page fault rate.

---

The Dirty Bit: Optimizing Eviction

Each page table entry contains a dirty bit (also called the modified bit), set to 1 by the hardware whenever the page is written to.

• Dirty bit = 0 (clean page): The page in RAM is identical to the copy on disk. Eviction is free — just overwrite the frame. No disk write needed.
• Dirty bit = 1 (dirty page): The page has been modified since it was last loaded from disk. Before eviction, the OS must write the page back to disk to preserve changes. This costs one extra disk I/O.

Optimization: All else being equal, a good replacement algorithm prefers to evict clean (unmodified) pages to avoid the extra disk write cost.

---

Evaluating Algorithms: Reference Strings

To compare algorithms, we simulate them against a reference string — a sequence of page numbers representing the pages a process accesses.

Standard Reference String used throughout this section:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3

Number of frames: 3

We count page faults (each time a referenced page is not in RAM). A page hit (page already in RAM) costs nothing extra.

Algorithm 1: Optimal (OPT / Bélády's Optimal)

Rule: Replace the page that will not be used for the longest time in the future.

This algorithm looks into the future — it knows exactly when each page will next be referenced and always makes the perfect eviction choice.

Trace — Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 3 Frames:

Total Page Faults (Optimal): 7

Why Optimal is impossible to implement: The algorithm requires knowing the future reference string — which is impossible at runtime. It is used purely as a theoretical benchmark to measure how close other algorithms come to perfect performance.

---

Algorithm 2: FIFO (First-In, First-Out)

Rule: Replace the page that has been in memory the longest (first loaded = first evicted). Implemented with a simple queue — new pages added to the back, victim taken from the front.

Trace — Same Reference String, 3 Frames:

Total Page Faults (FIFO): 9

FIFO is simple to implement but performs poorly because it evicts based purely on age — it has no idea whether the oldest page is heavily used or completely idle.

---

Belady's Anomaly: More Frames → More Faults?!

FIFO has a deeply counter-intuitive pathological behavior called Belady's Anomaly:

Increasing the number of frames can actually increase the number of page faults with FIFO.

Demonstration — Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

This is Belady's Anomaly. It occurs because adding a frame changes which pages are evicted in a way that causes more misses later. Intuitively, a page evicted with 3 frames might be the "right" page, while with 4 frames a different page is evicted, causing more subsequent faults.

Algorithms immune to Belady's Anomaly: Optimal, LRU, and Second Chance. All belong to a class called stack algorithms — algorithms where the set of pages in memory for $n$ frames is always a subset of the set for $n+1$ frames. FIFO is NOT a stack algorithm.

Algorithm 3: LRU (Least Recently Used)

Rule: Replace the page that was least recently used in the past. Uses the recent past as a predictor of the near future (inverse of temporal locality).

Key property: LRU is a stack algorithm → immune to Belady's Anomaly.

Trace — Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 3 Frames:

Total Page Faults (LRU): 8 — between FIFO (9) and Optimal (7).

---

LRU Implementation: The Stack Method

Maintain an ordered stack of page numbers. Most recently used (MRU) is at the top; least recently used (LRU) is at the bottom:

• On a page reference:
  • If page is in stack → move it to the top.
  • If page is not in stack → push to the top.
• On eviction: Remove the page from the bottom of the stack.

Trace of stack for references 7, 0, 1, 2, 0:

Ref 7: Stack = [7]           (top→bottom: 7 is MRU and LRU)
Ref 0: Stack = [0, 7]        (0 is MRU)
Ref 1: Stack = [1, 0, 7]     (1 is MRU, 7 is LRU)
Ref 2: Stack = [2, 1, 0 | evict 7]  (2 pushed, 7 removed from bottom)
Ref 0: Stack = [0, 2, 1]     (0 was at bottom, moved to top)

Alternative: Counter/Timestamp Method Each page table entry stores the time of last use. On eviction, scan all frames to find the smallest timestamp. Simpler conceptually but requires scanning all frames on every fault.

---

Algorithm 4: Second Chance (Clock Algorithm)

Motivation: LRU is excellent but expensive — maintaining an ordered stack requires hardware support for every memory access. The Second Chance algorithm approximates LRU cheaply using a single reference bit per page.

The Reference Bit: Set to 1 by hardware whenever the page is accessed. The OS can clear it to 0 at any time.

The Algorithm (Clock Variant): Arrange frames in a circular queue with a "clock hand" pointer.

Clock state:
→ [A: R=1] → [B: R=0] → [C: R=1] → [D: R=0] ↺
              ↑
         clock hand

On a page fault:

1. Examine the page at the clock hand.
2. If Reference bit = 0 → Evict this page (it hasn't been used recently). Load new page here. Advance hand.
3. If Reference bit = 1 → Give a second chance: clear R to 0, advance the hand, go to step 1 with the next page.
4. In the worst case, the hand completes a full revolution (clearing all R bits) and evicts the page it started on (which now has R=0 since it was just cleared).

Example trace:

Before fault:
→ [A: R=1] → [B: R=0] → [C: R=1] → [D: R=1] ↺
  ↑ clock hand

Step 1: A has R=1 → Clear A's bit to 0, advance hand.
→ [A: R=0] → [B: R=0] → [C: R=1] → [D: R=1] ↺
              ↑

Step 2: B has R=0 → EVICT B. Load new page X here.
→ [A: R=0] → [X: R=1] → [C: R=1] → [D: R=1] ↺
                          ↑ hand advances past X

Second Chance is often called the Clock Algorithm because the circular queue and advancing hand resemble a clock.

---

Algorithm 5: NRU (Not Recently Used)

Motivation: Use both the Reference bit (R) and the Modified/Dirty bit (M) to make smarter eviction decisions.

The Four Classes (priority for eviction: evict lowest class first):

The OS periodically clears all R bits (on a timer interrupt), so "recently" means "since the last R-bit reset."

Rationale: Class 0 pages have not been used recently and are clean — evicting them is free (no disk write). Class 3 pages are actively used and dirty — evicting them is the most expensive (disk write required + likely to fault again soon).

---

The Full Algorithm Comparison

Practical reality: Modern operating systems (Linux, Windows) use variants of the Clock Algorithm (Second Chance) or more sophisticated multi-hand clock algorithms. True LRU is almost never implemented due to hardware costs. Optimal is only used for benchmarking.

PYQ Solved Numericals

Example 1: LRU with All Unique Pages [2022 Q3b — 7 marks]

Problem: Virtual page reference string: 0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92. 4 frames initially empty. Use LRU. (i) How many page faults? (ii) What pages are in memory at the end?

Solution: All 16 page numbers are distinct — no page appears twice. Therefore EVERY reference is a page fault = 16 page faults.

Final 4 frames (last 4 unique pages loaded): 28, 32, 88, 92. These are the pages in main memory at the end of the sequence.

Example 2: FIFO vs LRU Comparison [2024 Q7b — 7 marks]

Problem: Reference string: 1, 3, 4, 4, 3, 2, 1, 7, 5, 6, 4, 2, 1, 2. Main memory = 4 page frames. Determine which algorithm (FIFO or LRU) performs better.

Solution — FIFO trace (Queue = oldest → newest):

FIFO Page Faults = 11

Solution — LRU trace (frames sorted LRU→MRU, left→right):

LRU Page Faults = 11

Verdict: Both FIFO and LRU produce 11 page faults — they perform equally for this reference string. The hits on pages 1, 2, 3, 4 are not frequent enough to give LRU an advantage over FIFO.

Example 3: Three-Way Comparison [2023 Q5b — 9 marks]

Problem: Reference string: 7,2,3,1,2,5,3,4,6,7,7,1,0,5,4,6,2,3,0,1. 4 frames. Count faults for FIFO, LRU and Optimal.

FIFO (queue order):

FIFO faults = 16

LRU:

LRU faults = 15

Optimal (look ahead):

Optimal faults = 13

LRU performs better than FIFO (15 vs 16 faults), but Optimal (13 faults) is the theoretical minimum.

Example 4: 3 Frames vs 4 Frames [2019 Q7 — 14 marks]

Problem: Reference string: 1,2,3,4,5,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2. Compare page faults for FIFO and LRU with both 3 frames and 4 frames.

Results (trace yourself using the StepByStepBlock method above):

Practice tip: This is the hardest PYQ numerical in the set (14 marks, 23 references, two frame counts, two algorithms). Trace it systematically: first do FIFO with 3 frames, then FIFO with 4, then LRU with 3, then LRU with 4. Use a table format like the examples above.