Page Replacement Questions in GATE CSE: FIFO, LRU, Optimal

Page replacement questions in GATE CSE almost always take the same shape: a reference string of ten to fourteen pages, three or four frames, one algorithm named, and a page-fault count as the answer. Around that core sit three companions: Belady's anomaly, the working-set model and demand-paging access time. This guide works the trace by hand, shows the anomaly with a verified example, and lists the conventions that decide close answers.

Key takeaways

• The standard question is a fault count. Frames start empty, so the first touch of each distinct page is always a fault.
• Optimal is a lower bound, not an implementable policy. LRU is not guaranteed to beat FIFO on a given string.
• Belady's anomaly is possible for FIFO and impossible for LRU and Optimal, which are stack algorithms.
• Demand-paging access time is dominated by the fault term. Convert milliseconds to nanoseconds before adding.
• The working set at a moment is the set of distinct pages in the last window of references, and its size drives the frame allocation.

Where these questions sit in the paper

Third-party analyst compilations put Operating System at 5 to 16 marks per paper across 2009 to 2026, typically 6 to 10 marks in the 100-mark era, which is roughly four to six questions. The overall average across that series is about 8.8 marks; the 2009 to 2017 average is about 9.3 and the 2018 to 2026 average about 8.3. These figures are unofficial and analysts differ by two to three marks on borderline questions. In 2026 Shift 1, one analyst counted two one-mark and two two-mark Operating System questions, and the reported topics across the two shifts included page replacement, multi-level paging with a TLB, multilevel-queue scheduling, semaphores, Banker's algorithm and inode-based file access.

Page replacement belongs to the group of four topics that the analysis finds in nearly every paper, alongside scheduling calculations, synchronization code analysis and paging arithmetic. The full subject ranking is in the Operating Systems important topics guide.

Running a trace by hand

Take the reference string 4, 7, 6, 1, 7, 6, 1, 2, 7, 2 with three frames, all initially empty. The table below runs all three algorithms on it.

Three things are worth taking away. First, FIFO and LRU tie here at six faults; LRU is often better but is not guaranteed to be. Second, Optimal beats both because at the eighth reference it looks forward and sees that page 7 is needed again while 6 and 1 are not. Third, five of the faults are unavoidable: five distinct pages are touched, so no algorithm can do better than five on this string.

The mechanical differences between the policies are small but decisive. FIFO evicts by load order and a hit changes nothing. LRU evicts by last-use order and every hit refreshes that page's position. Optimal evicts the page whose next reference is furthest ahead, and a page never referenced again is the first to go.

Belady's anomaly

More frames should mean fewer faults. For FIFO, that is not always true. On the standard demonstration string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO takes 9 faults with three frames and 10 faults with four frames. Both counts are worth verifying on paper once, because the reason is instructive: with four frames the pages 1 and 2 stay long enough to become the oldest entries just before they are needed again.

LRU and Optimal cannot behave this way. They are stack algorithms: the set of pages held with n frames is always a superset of the set held with n − 1 frames, so adding a frame can only convert faults into hits. That property is the reason the classification matters, and it has been examined both as a stand-alone statement and, more recently, as one option inside a multiple-select question.

Working sets and thrashing

The working set at time t with window Δ is the set of distinct pages among the last Δ references. On the string above with Δ = 4, the working set at the seventh reference covers references four to seven, that is 1, 7, 6, 1, giving the set {1, 6, 7} of size 3. At the tenth reference the window covers 1, 2, 7, 2, giving {1, 2, 7}, again size 3.

The model is used in two ways in questions. Either you are asked for the working-set size at a given instant, which is a counting exercise, or you are asked what happens when the sum of the working sets exceeds the available frames. The answer to the second is thrashing: paging activity rises, CPU utilisation falls, and the remedy is to reduce the degree of multiprogramming, not to increase it. That last point is a standard one-mark trap.

Demand-paging access time

The formula is short: effective access time = (1 − p) × memory access time + p × page-fault service time, where p is the page-fault rate.

Example: memory access time 100 ns, page-fault rate 0.001, fault service time 5 ms.

• 5 ms = 5,000,000 ns.
• Effective access time = 0.999 × 100 + 0.001 × 5,000,000 = 99.9 + 5000 = 5099.9 ns, about 5.1 µs.

One fault per thousand accesses makes the average fifty times worse than memory. The inverse form asks for the largest fault rate that keeps the effective time within a target. For a 200 ns target here, 100 + p × 4,999,900 ≤ 200 gives p ≤ about 2 × 10⁻⁵, which is one fault in fifty thousand accesses. When a question splits the service time by whether the victim page is dirty, take the weighted average of the two service times first, then substitute.

The conventions and traps that decide answers

• Count the compulsory misses. Frames start empty unless stated otherwise, so distinct pages set the floor.
• LRU updates on hits. Forgetting this changes which page is evicted a few steps later.
• Optimal ties. When two candidate pages are never referenced again, either choice gives the same fault count; state the tie rule you used.
• Belady never applies to LRU or Optimal. Answering that it might is a common multiple-select slip.
• Units. Service times come in milliseconds, memory times in nanoseconds. Convert first.
• Dirty pages. A weighted service time applies when the question gives separate times for clean and dirty victims.
• Thrashing remedy. Reduce the degree of multiprogramming.
• Read the algorithm name. Second-chance and clock are FIFO variants with a reference bit, not LRU.

A wider list of the same kind is in common mistakes that cost marks in GATE CSE, and the formulas here also appear in the GATE CSE formula sheet.

How to practise

Take any ten-page reference string and run it three times, once for each algorithm, on the same sheet. Compare the fault counts, then repeat with one more frame to see whether anything moves in the wrong direction. Ten minutes of that does more than reading the definitions again.

Then drill the access-time formula in both directions until the unit conversion is automatic, because that is where most of the lost marks in this topic actually go. Page replacement is one of the highest-frequency Operating System templates in the most repeated topics analysis, and the Operating System chapter of the GATE CSE 2027 book works the full set of variants with solutions, including the frames-versus-faults and minimum-frames forms.