E ExamMaster

AWS Cloud Architect & Developer · Operating Systems

Page replacement

Victim choice under FIFO, LRU and Optimal, and Belady's anomaly.

maya still has 3 frames. She touches pages 1, 2, 3, 4, 1, 2, 5. Every algorithm on this lesson is a different victim on that string. FIFO faults 7 times — every touch missed. Optimal is the future-knowing lower bound. LRU approximates it. FIFO on 1,2,3,4,1,2,5,1,2,3,4,5 faults 9 times with 3 frames and 10 with 4 — Belady's anomaly.

  • AWS Cloud Architect & Developer
  • Medium level
  • 4 concepts

1A fault with no free frame needs a victim

maya has been given 3 frames. She touches a fourth page. Demand paging wants a frame and there is none free. The OS must pick a resident page to evict — the victim — write it back if it is dirty, and install the new page. That choice is page replacement.

The reference string on this lesson is the sequence of page numbers maya touches: 1, 2, 3, 4, 1, 2, 5. Three frames. Every algorithm below is a different victim rule on that same string.

Three frames, seven references. Each algorithm fills those frames in a different order.

When a victim is needed

  1. Touchmaya refers to a page.
  2. Hit or faultResident: continue. Not resident: fault.
  3. VictimIf no free frame, evict one resident page and bring the new one in.
The string
WhatValue
Frames3
References1, 2, 3, 4, 1, 2, 5
A page fault occurs and every frame is full. The OS must
  1. choose a victim page to evict
  2. grow RAM by one frame
  3. convert the process to a thread

Replacement is the victim choice. RAM does not grow. Threads do not create frames.

2FIFO evicts the oldest arrival

FIFO evicts the page that has been in memory the longest — the oldest arrival — regardless of how recently maya used it. Trace 1, 2, 3, 4, 1, 2, 5 against 3 frames: 1,2,3 miss and fill the frames (3 faults). 4 misses and evicts 1. 1 misses and evicts 2. 2 misses and evicts 3. 5 misses and evicts 4. Seven references, seven faults — every touch missed.

FIFO is easy to implement (a queue of arrival order) and can misbehave: a page used a moment ago may be the oldest arrival. Belady's anomaly is FIFO's famous extra fault when you add a frame.

Figure. Snapshot after the fourth reference in the ledger. Arrival order left→right is 2, then 3, then 4 — the next FIFO victim is whatever sits under "oldest".

How it works

  1. HitReferenced page already in a frame → no change to the arrival order.
  2. Miss, roomLoad into a free frame; record it as the newest arrival.
  3. Miss, fullEvict the oldest arrival; load the new page in its place.

FIFO page faults

Reference string 1, 2, 3, 4, 1, 2, 5 with 3 frames using FIFO — count page faults.

  • 1,2,3 miss → frames{1, 2, 3} (3 faults)
  • 4 misses, evict oldest 1{2, 3, 4} (fault 4)
  • 1 misses (evict 2); 2 misses (evict 3){3, 4, 1} then {4, 1, 2}
  • 5 misses (evict 4); hits so far: none{1, 2, 5}; total = 7 faults

Pro tip. In FIFO, always evict the page that entered earliest, not the one used least recently. Every reference in this string faulted — a useful stress case for hand traces.

Coding lab. FIFO faults on 1,2,3,4,1,2,5 runs in the app, with checks on your output.

Under FIFO with 3 frames, after references 1, 2, 3, 4 the resident set is
  1. {1, 2, 3}
  2. {2, 3, 4}
  3. {1, 2, 4}

1, 2, 3 fill the frames; 4 evicts the oldest arrival 1, leaving {2, 3, 4}.

3LRU evicts the least recently used page

LRU looks at recency, not arrival. The victim is the resident page whose last use is farthest in the past. On a hit, that page becomes the most recent. On a miss with a full set, the least recent leaves.

LRU is a stack algorithm: giving it more frames never increases the fault count on a given string. That is why LRU does not show Belady's anomaly. It needs hardware or a software approximation (a clock / second-chance hand) because a true timestamp on every reference is expensive.

Same string 1,2,3,4,1,2,5 and three frames. LRU would evict by recency, not by arrival order.

On each reference

  1. HitThe page is already resident. Mark it most recent.
  2. Miss, free frameLoad it. Mark it most recent.
  3. Miss, fullEvict the least recently used resident page, then load.
LRU evicts the resident page that
  1. was used farthest in the past
  2. arrived first, ignoring later uses
  3. will be used farthest in the future

Recency of last use is LRU. Arrival order is FIFO. Future use is Optimal.

4Optimal, and Belady's anomaly

Optimal replacement evicts the page whose next use is farthest in the future. It is the theoretical minimum fault count on a known string, and it needs the future, so it is a benchmark, not a kernel policy. LRU is the usual practical approximation: the least recent past stands in for the farthest future.

Belady's anomaly is the surprise that adding a frame can raise the fault count. FIFO shows it. The string 1,2,3,4,1,2,5,1,2,3,4,5 faults 9 times with 3 frames and 10 times with 4 frames. LRU and Optimal are stack algorithms and do not Belady.

Figure. Same reference string under FIFO: three frames end at {5,3,4} with 9 faults, four frames end with 10. LRU and Optimal never show this anomaly because they obey the stack property.

What each picks

  1. OptimalVictim = page with the most distant next reference (or never again).
  2. LRUVictim = page whose most recent reference is oldest.
  3. Stack propertyLRU/Optimal never show Belady: growing the frame set never drops a page that a smaller set would keep.
Replacement at a glance
AlgorithmVictimBelady?
FIFOOldest arrivalPossible
LRULeast recently usedNever (stack)
OptimalFarthest next useNever (stack); lower-bound benchmark

Belady under FIFO

Reference string 1,2,3,4,1,2,5,1,2,3,4,5. Compare FIFO faults with 3 frames versus 4 frames.

  • 3 frames: 1..5 as in FIFO concept, then 1 hit, 2 hit{1,2,5}; faults = 7 so far
  • 3 frames: 3 misses (evict 1); 4 misses (evict 2); 5 hits{5,3,4}; faults = 7+2 = 9
  • 4 frames: fill 1..4 (4 faults); 1,2 hit; 5 misses → {2,3,4,5}faults = 5 so far
  • 4 frames: 1,2,3,4,5 each miss once morefaults = 5+5 = 10 (> 9)

Pro tip. If your LRU fault count ever beats Optimal on the same string and frame count, the arithmetic is wrong — Optimal is the lower bound.

Which statement is true?
  1. LRU can exhibit Belady's anomaly; Optimal cannot
  2. FIFO can exhibit Belady's anomaly; LRU and Optimal cannot
  3. All three of FIFO, LRU and Optimal can exhibit Belady's anomaly

Belady's anomaly is a FIFO (non-stack) phenomenon. LRU and Optimal are stack algorithms and never get worse when frames increase.

Notes

  • A page fault with no free frame picks a victim to evict.
  • FIFO evicts the oldest arrival and can show Belady's anomaly.
  • LRU evicts the least recently used page and is a stack algorithm.
  • Optimal evicts the page used farthest in the future — a lower bound.

Formulas

  • FIFO fault count is the number of misses while maintaining an arrival queue of size equal to the frame count.
  • Belady's anomaly: more frames, more faults — possible under FIFO, not under LRU or Optimal.

Exam traps & shortcuts

  • If adding a frame raised the fault count, the algorithm is not a stack algorithm — usually FIFO.
  • Optimal is the exam's 'minimum possible faults', not a real OS policy.

Reference tables

String 1,2,3,4,1,2,5,1,2,3,4,5. More frames, more faults.

Belady under FIFO
FramesFIFO faults
39
410

Recap

Same string, different victim. FIFO can Belady; LRU and Optimal cannot.

Victim
A fault with no free frame evicts a resident page.
FIFO
Oldest arrival leaves. 1,2,3,4,1,2,5 with 3 frames → 7 faults.
LRU
Least recent use leaves. Stack algorithm — no Belady.
Optimal
Farthest next use leaves. Benchmark, needs the future.
Belady
FIFO: 9 faults at 3 frames, 10 at 4, on 1..5,1,2,3,4,5.

Practise Page replacement

Reading is free and needs no account. Practice, mocks and progress live in the app.

  • A 1-question practice set that ends the chapter
  • 4 quick checks with worked explanations
  • Timed mocks scored with the real marking scheme
  • Readiness tracked per topic, kept on your device
Continue with Google — freeNo card, no trial. Works offline once installed.