Page replacement questions in GATE CS are mostly counting. You get a reference string, a number of frames and a policy, and you write a row of letters. The idea is easy; the marks go when you lose track of the oldest page late in the paper.
So the useful skill is a method you can run without thinking, plus a way to check yourself on practice problems. I wrote a small Python checker for the second part.
Schoolabe's GATE memory management chapter uses this reference string with 3 frames as its worked example:
1 2 3 4 1 2 5 1 2
It says to count FIFO carefully with a queue, and it doesn't print the answer. Here are the three policies, then the numbers. The code blocks in this post are one file, in order; paste them together and it runs.
import random
from collections import OrderedDict, deque
def fifo(refs, frames):
q, mem, faults, trace = deque(), set(), 0, []
for p in refs:
if p in mem:
trace.append("hit")
else:
faults += 1
if len(mem) == frames:
mem.remove(q.popleft())
q.append(p)
mem.add(p)
trace.append("F")
return faults, trace
def lru(refs, frames):
mem, faults, trace = OrderedDict(), 0, []
for p in refs:
if p in mem:
mem.move_to_end(p)
trace.append("hit")
else:
faults += 1
if len(mem) == frames:
mem.popitem(last=False)
mem[p] = True
trace.append("F")
return faults, trace
def opt(refs, frames):
mem, faults, trace = [], 0, []
for i, p in enumerate(refs):
if p in mem:
trace.append("hit")
continue
faults += 1
trace.append("F")
if len(mem) < frames:
mem.append(p)
continue
rest = refs[i + 1:]
# evict the page whose next use is furthest away (or never)
victim = max(mem, key=lambda x: rest.index(x) if x in rest else float("inf"))
mem.remove(victim)
mem.append(p)
return faults, trace
lesson = [1, 2, 3, 4, 1, 2, 5, 1, 2]
print("Lesson string with 3 frames:", lesson)
for name, policy in (("FIFO", fifo), ("LRU", lru), ("OPT", opt)):
n, t = policy(lesson, 3)
print(f" {name}: {n} faults {' '.join(t)}")
print("FIFO on the same string with 4 frames:", fifo(lesson, 4)[0], "faults")
Lesson string with 3 frames: [1, 2, 3, 4, 1, 2, 5, 1, 2]
FIFO: 7 faults F F F F F F F hit hit
LRU: 7 faults F F F F F F F hit hit
OPT: 5 faults F F F F hit hit F hit hit
FIFO on the same string with 4 frames: 7 faults
Check the FIFO row by hand. Pages 1, 2, 3 fill the frames. Page 4 evicts 1, so the next 1 faults and evicts 2, so the next 2 faults and evicts 3. Page 5 evicts 4. Then 1 and 2 are both still in memory and hit. Seven faults.
For the hand trace I write the full frame contents under every reference, not just F or hit. For FIFO I underline the oldest page, and for LRU I rewrite the frames in recency order each time. It is slower, but when you go wrong you can see where.
LRU also gets seven here, so LRU does not always beat FIFO on a given string. Optimal gets five, and that is your floor. It needs the future, so no real system can do it. The chapter calls it the offline lower bound, and if your hand trace beats it, you have miscounted.
The anomaly
The chapter says FIFO can show Belady's anomaly, where more frames give more faults, and calls it a favourite trap. The lesson string above doesn't show it: FIFO with 4 frames also gives 7. The textbook string is the same one extended by three pages, 1 2 3 4 1 2 5 1 2 3 4 5.
belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print("Classic string:", belady)
for name, policy in (("FIFO", fifo), ("LRU", lru)):
for frames in (3, 4):
print(f" {name}, {frames} frames: {policy(belady, frames)[0]} faults")
Classic string: [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
FIFO, 3 frames: 9 faults
FIFO, 4 frames: 10 faults
LRU, 3 frames: 10 faults
LRU, 4 frames: 8 faults
FIFO goes from 9 faults to 10 when it gets a fourth frame. The anomaly was described by Belady, Nelson and Shedler in "An anomaly in space-time characteristics of certain programs running in a paging machine", Communications of the ACM 12(6), June 1969, pp. 349-353 (doi 10.1145/363011.363155).
LRU on the same string drops from 10 to 8, as you would expect. The reason is the stack property: the pages LRU holds with k frames are always a subset of what it holds with k+1 frames. FIFO keeps pages by arrival order, not by use, so it has no such property.
How common is this? I guessed "not very" and wanted a number, so I drew random strings of 12 references over pages 1 to 5, with a fixed seed so you can reproduce it, and compared 3 frames against 4.
random.seed(2026)
trials, bad_fifo, bad_lru = 1_000_000, 0, 0
for _ in range(trials):
refs = [random.randint(1, 5) for _ in range(12)]
if fifo(refs, 4)[0] > fifo(refs, 3)[0]:
bad_fifo += 1
if lru(refs, 4)[0] > lru(refs, 3)[0]:
bad_lru += 1
print(f"{trials:,} random strings, 12 refs over pages 1-5, 3 frames vs 4:")
print(f" FIFO faulted more with 4 frames: {bad_fifo}")
print(f" LRU faulted more with 4 frames: {bad_lru}")
1,000,000 random strings, 12 refs over pages 1-5, 3 frames vs 4:
FIFO faulted more with 4 frames: 1
LRU faulted more with 4 frames: 0
One hit in a million. A first attempt with 100,000 strings found none, so I'd have written "never" if I'd stopped there. A single hit can't pin down a rate, though, so I also counted exhaustively with a small C program: of all 5^12 = 244,140,625 strings of 12 references over five pages, FIFO faults more with 4 frames than with 3 in exactly 120 of them. That is about 1 in 2 million. It also explains why the textbook string looks hand-built. Someone had to go looking for it.
Don't hunt for the anomaly in the trace. Look at the wording: of these three policies only FIFO can fault more with more frames, so a question asking which one can has its answer before you count anything. If the policy is LRU or Optimal, the anomaly can't be the point.
The checker is also good for something duller. Take any previous-year question with a string and a frame count, run all three policies, and compare with your hand trace. Schoolabe's GATE hub says its previous-year questions show questions and options only for now, and tells you to cross-check the official IIT answer key yourself. That is fair advice for any source, this one included.
CLOCK, the chapter's fourth policy, is not covered here.
Written by the Schoolabe team, who build schoolabe.com. The GATE CS section lists free subject tutorials, topic quizzes and previous-year papers.
Top comments (0)