Page replacement: FIFO, optimal and LRU; Belady's anomaly

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. EAT with page faults? from Lesson 5.3.1
2. What happens in step 3 of a page fault if no frame is free? from Lesson 5.3.1
3. What is FCFS's weakness in CPU scheduling? from Lesson 2.1.1

1 · The Hook

Your desk holds three books; a fourth is needed. Which one goes back on the shelf: the one that has been on the desk longest, the one you won't need for the longest time, or the one you haven't opened for the longest time? These are FIFO, optimal and LRU, and counting their page faults on a reference string is one of the most common GATE questions in OS.

3 · Core Concept

Predict First — the answer

1, 2, 3 fault (3), 1 hits, 4 faults and evicts 1 (the oldest) → 4 faults.

In plain words

Write the reference string across the page. Keep a column of frames under each reference. On a hit nothing changes. On a miss with a free frame, fill it. On a miss with no free frame, evict the page the policy chooses. Count the misses.

1. The three policies

• FIFO: evict the page that has been in memory longest (loaded earliest).
• Optimal (OPT): evict the page whose next use is farthest in the future (or never used again). Fewest faults possible; needs the future, so it is only a benchmark.
• LRU (least recently used): evict the page not used for the longest time (looks at the past).

2. Running example: 7 0 1 2 0 3 0 4 2 3 0 3 2, 3 frames

ref:    7 0 1 2 0 3 0 4 2 3 0 3 2
FIFO    7 7 7 2 2 2 2 4 4 4 0 0 0
        . 0 0 0 0 3 3 3 2 2 2 2 2
        . . 1 1 1 1 0 0 0 3 3 3 3
fault   F F F F - F F F F F F - -     10 faults

OPT     7 7 7 2 2 2 2 2 2 2 2 2 2
        . 0 0 0 0 0 0 4 4 4 0 0 0
        . . 1 1 1 3 3 3 3 3 3 3 3
fault   F F F F - F - F - - F - -      7 faults

LRU     7 7 7 2 2 2 2 4 4 4 0 0 0
        . 0 0 0 0 0 0 0 0 3 3 3 3
        . . 1 1 1 3 3 3 2 2 2 2 2
fault   F F F F - F - F F F F - -      9 faults

(Each row is one frame; the new page goes into the victim's frame.) With 4 frames: FIFO 7, OPT 6, LRU 6.

3. Belady's anomaly

Normally more frames → fewer (or equal) faults. With FIFO this can fail: string 1 2 3 4 1 2 5 1 2 3 4 5 → FIFO with 3 frames: 9 faults; with 4 frames: 10 faults. LRU and OPT never show the anomaly (they are "stack algorithms": the pages kept with n frames are always a subset of those kept with n + 1).

4. Implementing LRU

Exact LRU needs hardware help on every access: a counter (time stamp) per page, or a stack of page numbers (move to top on use). That is expensive, so real systems use approximations based on a reference bit (next lesson).

5. Quick bounds

Starting with empty frames: faults ≥ number of distinct pages in the string, and faults ≤ length of the string.

4 · Visual

Belady's string 1 2 3 4 1 2 5 1 2 3 4 5: only FIFO gets worse when a frame is added.

5 · Worked Examples

Example 1 Easy

Running string, 3 frames, FIFO: which page is evicted when page 3 first arrives (6th reference)?

Solution

Frames hold 2, 0, 1 with 0 loaded earliest (at reference 2) → 0 is evicted.

Example 2 Medium

Running string, 3 frames, LRU: which page is evicted when page 4 arrives (8th reference)?

Solution

Frames 2, 0, 3; last uses: 2 at ref 4, 0 at ref 7, 3 at ref 6 → 2 is least recently used.

Example 3 GATE

Reference string 1 2 3 4 1 2 5 1 2 3 4 5 with OPT and 3 frames: number of faults?

Solution

7: 1, 2, 3 load; 4 evicts 3 (needed latest); 5 evicts 4; then 3 and 4 each evict a page that is never needed again.

6 · GATE Traps

• FIFO evicts the oldest loaded, even if it was just used (hits don't refresh it).
• LRU evicts the least recently used (hits do refresh it).
• OPT looks forward; a page never used again is the perfect victim.
• Belady's anomaly: only FIFO-type algorithms; never LRU or OPT.

7 · Memory Hook

"FIFO: oldest arrival. OPT: farthest future. LRU: longest past. More frames can hurt only FIFO."

8 · Connect the Dots

Exact LRU is too costly. The last memory lesson approximates it with the clock algorithm, decides how many frames each process gets, and explains thrashing: what happens when every process has too few.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — FIFO

Reference string 7 0 1 2 0 3 0 4 2 3 0 3 2, 4 frames (empty at first), FIFO. Number of page faults?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — LRU

Same string, 3 frames, LRU. Number of page faults?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — OPT

Same string, 3 frames, optimal replacement. Number of page faults?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Belady

Reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO with 4 frames. Number of page faults?

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Belady

Which algorithms can suffer from Belady's anomaly?

1. (A) Second chance (FIFO with a reference bit)
2. (B) FIFO
3. (C) Optimal
4. (D) LRU

10 · Rule Card

• FIFO: evict earliest loaded. OPT: evict farthest next use (never used = best). LRU: evict least recently used.
• Running string, 3 frames: FIFO 10, OPT 7, LRU 9; 4 frames: FIFO 7, OPT 6, LRU 6.
• Belady (FIFO): 1 2 3 4 1 2 5 1 2 3 4 5 → 9 faults with 3 frames, 10 with 4. LRU and OPT are stack algorithms (no anomaly).
• Faults ≥ distinct pages (from empty); exact LRU needs counters or a stack.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

page replacementvictim pagereference stringFIFO replacementoptimal replacementLRU replacementBelady's anomalystack algorithmsimplementing LRU with counters or a stack