What is Belady's anomaly in page replacement?

Belady's anomaly is the counterintuitive phenomenon where increasing the number of page frames causes MORE page faults for FIFO page replacement. It does not occur for LRU or Optimal algorithms (which are stack algorithms — more frames always means fewer or equal page faults).

Which page replacement algorithm gives the minimum number of page faults?

Optimal (OPT) page replacement gives the minimum page faults — it replaces the page that will not be used for the longest time in the future. It is theoretically optimal but not implementable in practice (requires future knowledge). It serves as a benchmark to evaluate other algorithms.

How do you calculate effective access time with demand paging?

EAT = (1-p) × memory_access_time + p × page_fault_time. Where p is the page fault rate (fraction of accesses that cause page faults). Page fault time includes: service page fault interrupt + swap in page (dominant cost, milliseconds) + restart instruction.

What is thrashing in operating systems?

Thrashing occurs when a process does not have enough frames to keep its working set in memory — it constantly page faults, spending more time paging than executing. CPU utilisation drops to near zero as the OS is busy handling page faults. Solution: working set model (allocate frames based on working set size) or page fault frequency control.

Virtual Memory for GATE CS

Demand paging, page fault, EAT, FIFO/LRU/Optimal page replacement, Belady’s anomaly, thrashing — with full GATE numerical examples.

Last updated: April 2026 | GATE CS 2024–2026 syllabus

Key Takeaways for GATE

Virtual memory allows processes to use more memory than physically available — non-resident pages stored on disk.
Demand paging: pages loaded only when needed. Page fault → OS loads page from disk.
EAT = (1−p) × t_mem + p × t_fault. Must keep p very small (p < 10⁻⁶ for acceptable performance).
Optimal: minimum page faults (replace furthest-used). Not implementable. LRU: best practical. FIFO: simplest, worst.
Belady’s anomaly: FIFO can have MORE faults with MORE frames. LRU and OPT never have this.
Stack algorithms (LRU, OPT): more frames ⇒ never more page faults. FIFO is NOT a stack algorithm.
Thrashing: too few frames → constant page faults → CPU utilisation collapses.

1. Demand Paging

Pages are loaded into memory only when accessed (on demand). All pages initially on disk.
Each page table entry has a valid/invalid bit:
Valid (1): page is in memory. Invalid (0): page is on disk or not in address space.

Advantages: Less I/O, less memory needed, faster startup, more processes can be multiprogrammed.
Disadvantage: Page fault overhead (disk I/O, ~10ms) vs memory access (~100ns). Must keep page fault rate low.

2. Page Fault Handling

Steps when invalid bit triggers page fault:
1. OS checks page reference: valid access or illegal? If illegal: terminate process.
2. Find free frame. If none: run page replacement algorithm to select victim frame.
3. If victim frame is dirty (modified): write to disk (swap out).
4. Read required page from disk into free frame (swap in — dominant cost ~10ms).
5. Update page table (set valid bit, frame number).
6. Restart the faulting instruction.

Pure demand paging: start with no pages in memory. Every first access faults. Locality reduces subsequent faults.

3. Effective Access Time with Demand Paging

p = page fault rate (0 ≤ p ≤ 1)
EAT = (1−p) × t_mem + p × t_fault

t_fault includes: page fault interrupt service + swap out dirty page (if needed) + swap in required page + restart overhead.
Typically t_fault ≈ 10ms = 10,000,000 ns. t_mem ≈ 100ns.

Example: p=0.001, t_mem=100ns, t_fault=10ms.
EAT = 0.999 × 100 + 0.001 × 10,000,000 = 99.9 + 10,000 = 10,099.9 ns ≈ 10μs.
100× slowdown! Keep p < 10⁻⁶ for <10% slowdown.

For acceptable EAT ≤ 110 ns (10% overhead):
110 = (1−p)×100 + p×10,000,000 ⇒ 10 = 9,999,900p ⇒ p < 10⁻⁶.

4. FIFO Page Replacement

Replace the page that has been in memory the longest (first in, first out).
Implementation: queue of pages. Victim = front of queue.

Example (3 frames, reference string: 1,2,3,4,1,2,5,1,2,3,4,5):

Ref	Frames	Fault?
1	1 – –	F
2	1 2 –	F
3	1 2 3	F
4	4 2 3	F (replace 1)
1	4 1 3	F (replace 2)
2	4 1 2	F (replace 3)
5	5 1 2	F (replace 4)
1	5 1 2	Hit
2	5 1 2	Hit
3	5 3 2	F (replace 1)
4	5 3 4	F (replace 2)
5	5 3 4	Hit

Total page faults = 9. (Hits: 3)

5. Optimal (OPT) Page Replacement

Replace the page that will not be used for the longest time in future.
Gives minimum page faults. Not implementable (requires future knowledge).
Used as benchmark to evaluate other algorithms.

Same example (3 frames, string: 1,2,3,4,1,2,5,1,2,3,4,5):
At each fault, look ahead and keep pages needed soonest. Replace page needed latest (or never).
Total page faults with OPT = 7 (2 fewer than FIFO).

6. LRU Page Replacement

Replace the page that has not been used for the longest time (least recently used).
Good practical approximation of OPT (uses past as predictor of future).

Implementation:
Counter: each page table entry gets a counter updated on access. Replace smallest counter. O(1) update, O(n) search.
Stack: doubly linked list + hash map. O(1) update and O(1) replacement. Move accessed page to top; victim is bottom.

Same example (3 frames):
Total page faults with LRU = 8 (1 fewer than FIFO, 1 more than OPT).

LRU is a stack algorithm — more frames ⇒ never more page faults.

7. LRU Approximations

True LRU requires hardware support (timestamps). Approximations used in practice:

Reference bit: Set to 1 on access. OS periodically clears. Replace page with reference bit = 0 (not used recently).

Second-chance (Clock) algorithm: FIFO + reference bit. When replacing, check reference bit:
If 1: clear bit, give second chance (advance pointer). If 0: replace this page.

Enhanced second-chance: Use (reference bit, dirty bit) pairs. Priority: (0,0) > (0,1) > (1,0) > (1,1).
(0,0): not used, not modified — best victim. (1,1): recently used and dirty — worst victim.

8. Belady’s Anomaly

Belady’s anomaly: For FIFO, increasing the number of frames can increase page faults.

Example (reference string: 1,2,3,4,1,2,5,1,2,3,4,5):
3 frames (FIFO): 9 faults. 4 frames (FIFO): 10 faults! ← More frames, more faults!

Stack algorithms do NOT exhibit Belady’s anomaly:
Property: the set of pages in memory with n frames is always a subset of pages with n+1 frames.
LRU and Optimal are stack algorithms. FIFO is NOT.

GATE significance: Belady’s anomaly ⇒ FIFO. No anomaly ⇒ LRU/Optimal. Common 1-mark question.

9. Thrashing & Working Set

Thrashing: Process has fewer frames than its working set. It constantly page faults.
CPU spends more time paging than executing. CPU utilisation drops. OS may increase multiprogramming (wrong!), making it worse.

Working Set Model:
Working set W(Δ, t) = set of pages referenced in last Δ time units (working set window).
Allocate at least |W| frames to each process. If ∑|W_i| > total frames: suspend a process.

Page Fault Frequency (PFF) control:
Set upper and lower bounds on acceptable fault rate.
Too high fault rate → allocate more frames. Too low → reclaim frames. Suspend process if no free frames available.

10. GATE Examples

GATE 2020 — LRU page faults:
Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,2. Frames = 3.
Trace (LRU, replace least recently used on fault):
7:F[7] 0:F[7,0] 1:F[7,0,1] 2:F[2,0,1](replace7) 0:H 3:F[2,0,3](replace1) 0:H 4:F[4,0,3](replace2) 2:F[4,2,3](replace0) 3:H 0:F[4,2,0](replace3) 3:F[3,2,0](replace4) 2:H
Faults: 7,0,1,2,3,4,2,0,3 = 9 page faults.

GATE 2022 — EAT:
Memory access = 200ns. Page fault service = 8ms = 8,000,000ns. Page fault rate = 0.5%.
p = 0.005. EAT = 0.995 × 200 + 0.005 × 8,000,000 = 199 + 40,000 = 40,199 ns ≈ 40μs.

GATE 2023 — Belady’s anomaly:
For which algorithm can increasing frames increase page faults?
Answer: FIFO. LRU and Optimal are stack algorithms — more frames never increases faults.

11. Common Mistakes

Confusing FIFO victim with LRU victim: FIFO replaces the page loaded earliest (oldest in time since load). LRU replaces the page accessed least recently (oldest last access). They often give different victims — trace carefully.
Counting compulsory misses: Every page’s first access is always a page fault regardless of algorithm or frames — it’s a compulsory miss. Don’t penalise algorithms for these.
Thrashing direction: Thrashing is caused by TOO FEW frames. More multiprogramming without enough memory increases thrashing. The solution is to REDUCE multiprogramming (suspend processes) or allocate more frames.
Optimal algorithm ≠ LRU: Optimal looks into the future; LRU looks at the past. They give different page fault counts for most reference strings.
Belady’s anomaly is FIFO-specific: Do not apply Belady’s reasoning to LRU or Optimal — they are stack algorithms with monotone fault behaviour.

12. FAQ

What is Belady’s anomaly in page replacement?: Belady’s anomaly is the surprising behaviour of FIFO page replacement where adding more page frames actually causes more page faults for certain reference strings. This seems counterintuitive — more memory should help, not hurt. It occurs because FIFO is not a stack algorithm. LRU and Optimal are stack algorithms: the set of pages in memory with n frames is always a subset of those with n+1 frames, guaranteeing more frames ⇒ never more faults.
Which page replacement algorithm gives the minimum number of page faults?: Optimal (OPT) gives the provably minimum page faults — it always replaces the page that will not be needed for the longest time in the future. It cannot be implemented in practice since it requires knowledge of future references, but it serves as the theoretical lower bound. LRU is the best practical algorithm, usually approaching OPT performance due to locality of reference.
How do you calculate effective access time with demand paging?: EAT = (1−p) × t_mem + p × t_fault, where p is the page fault rate. t_fault includes disk I/O to load the missing page (typically 8−10ms, orders of magnitude slower than memory). To keep EAT within 10% of t_mem (say ≤ 110ns for 100ns memory), p must be less than about 10^−6 — fewer than 1 fault per million accesses.
What is thrashing in operating systems?: Thrashing occurs when a process or set of processes has fewer allocated frames than their working set requires. They continuously page fault, spending all their time waiting for pages to be swapped in. CPU utilisation drops near zero. The OS misinterprets this as low CPU load and increases multiprogramming, making thrashing worse. Solutions: working set model (give each process its working set frames), page fault frequency control, or suspend some processes.

Virtual Memory in OS – Demand Paging, Page Replacement and Thrashing | GATE CS