Page Replacement Algorithms for GATE: FIFO, LRU and Optimal with Belady's Anomaly Explained

Page replacement questions in GATE are pure marks if you can run a trace without slipping, and pure frustration if you learned the algorithms as slogans. This post traces one reference string, fault by fault, through FIFO, LRU and Optimal, then shows Belady's anomaly actually happening in a table you can verify by hand. If you can reproduce these four traces cold, you are done with this subtopic.

Page replacement in operating systems: where it sits

In a demand-paged system, a process's pages live on disk and are brought into physical memory frames only when referenced. When a process references a page that is not in memory, the hardware raises a page fault, and the OS must load that page into a frame.

The interesting case is when every frame is already occupied. Some resident page must be evicted to make room, and the page replacement algorithm is the policy that picks the victim. A good policy keeps the pages you are about to use; a bad one keeps throwing out exactly what you need next.

This subtopic sits inside virtual memory, which itself builds on paging. If the frame, page-table and address-translation machinery is not solid yet, read our Memory Management in OS: paging and segmentation pillar first, then come back. Everything below assumes you know what a frame is.

The reference string every trace below uses

A reference string is just the sequence of page numbers a process touches. We will use one string for every algorithm in this post:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 frames, all empty at the start.

Two counting rules GATE expects you to follow:

• Every reference to a page not currently in a frame is a fault, including the initial faults that fill empty frames. Unless a question explicitly says to ignore cold-start faults, count them.

• Hit ratio = hits divided by total references; fault ratio is the complement.

This particular string is a classic for a reason: it is the standard string used to demonstrate Belady's anomaly, and it also cleanly separates the three algorithms at 3 frames.

FIFO page replacement: the fault-by-fault trace

FIFO evicts the page that has been in memory longest. Think of the frames as a queue: pages enter at the tail, victims leave from the head. Note what FIFO ignores: how recently or how often a page was used. Only arrival time matters.

FIFO with 3 frames: 9 faults, 3 hits. Hit ratio 3/12 = 0.25.

The pain point in steps 4 to 7 is typical FIFO behaviour: pages 1 and 2 are evicted right before they are needed again, purely because they arrived first.

LRU page replacement: the same string, traced

LRU evicts the page whose last use is furthest in the past. It bets that the recent past predicts the near future, which is exactly the locality-of-reference assumption behind caching everywhere.

LRU with 3 frames: 10 faults, 2 hits.

Look at that carefully: on this string, LRU does worse than FIFO (10 faults against 9). Students memorise "LRU is better than FIFO" as a law, and examiners exploit exactly that. LRU is better on workloads with strong locality; on an adversarial string like this one, nothing guarantees it. Never answer a comparison question from folklore. Trace it.

The traces diverge only from step 10. At step 10, FIFO evicts page 1 (oldest arrival) while LRU evicts page 5 (least recently used), and the two policies part ways from there.

Optimal page replacement: the benchmark trace

Optimal (also called OPT or Belady's algorithm) evicts the page that will not be used for the longest time in the future. It needs knowledge of the future, so no real OS can implement it. It exists as the provable lower bound on faults, the benchmark other policies are measured against, and GATE tests it as a numerical exercise anyway.

Optimal with 3 frames: 7 faults, 5 hits.

So the scoreboard on one shared string with 3 frames reads: Optimal 7, FIFO 9, LRU 10. When two resident pages are never used again (steps 10 and 11), either is a valid victim; the fault count is the same whichever you pick.

Belady's anomaly: more frames, more faults under FIFO

Intuition says adding frames should reduce faults, or at worst leave them unchanged. Belady's anomaly is the observation that under FIFO, adding frames can increase faults. Here is the same string with 4 frames:

FIFO with 4 frames: 10 faults, against 9 faults with 3 frames. That is the anomaly, demonstrated, not asserted.

Why does it happen? FIFO's eviction order depends only on arrival order, so the set of pages held with 4 frames is not a superset of the set held with 3 frames at each step. Compare step 8 in the two FIFO tables: with 3 frames, page 1 is resident (it was reloaded at step 5); with 4 frames, page 1 was just evicted.

LRU never shows the anomaly. It belongs to the class of stack algorithms, policies where the pages held with k frames are always a subset of the pages held with k+1 frames. A subset relation makes faults monotonically non-increasing in frame count. Optimal is also a stack algorithm. On our string, LRU with 4 frames gives 8 faults, down from 10, exactly as the stack property predicts.

Page replacement in GATE: how it is asked

GATE treats this subtopic as numerical territory. The recurring patterns: For cycle-specific paper rules and scoring, use the official GATE portal.

1. Count the faults. A reference string, a frame count, one named algorithm. Pure NAT-style computation; the tables above are the exact procedure.

2. Compare two algorithms on one string, or find the string position where their behaviour first diverges.

3. Belady's anomaly conceptually: which algorithms can exhibit it, and why LRU and Optimal cannot (the stack property is the answer).

4. Hit ratio and effective access time, combining a fault count with memory and page-fault service times.

Speed matters more than insight here. The insight is fixed; the marks go to whoever traces 20 references without a slip. Build that speed on real questions: our Page Replacement MCQs for GATE collection has previous-year and practice problems keyed to this exact post, and the Virtual Memory module of GATE Guidance carries the full lesson sequence with worked solutions.

For cycle-specific paper rules and scoring, use the official GATE portal.

The short version, and the next step

Four things to walk away with:

• FIFO evicts by arrival, LRU by last use, Optimal by furthest future use. On our shared string with 3 frames: 9, 10 and 7 faults respectively.

• Count cold-start faults unless told otherwise, and compute hit ratio as hits over total references.

• LRU beating FIFO is a tendency, not a theorem. Trace, never assume.

• FIFO can exhibit Belady's anomaly, while the stack algorithms LRU and Optimal are immune because of the subset property.

Hand-solve all four tables in this post once without looking, then move to timed questions. If you want the whole Operating System syllabus sequenced this way, with 205 OS lessons including dedicated Memory Management and Virtual Memory sections, personalised to your target score, that is what GATE Guidance by Sanchit Sir is built for. If you only need this one subtopic, the MCQ set linked above will tell you honestly whether you are exam-ready. For the wider syllabus map, use the GATE preparation category.