Page replacement is where demand paging turns into arithmetic. Once frames fill up, the operating system must evict something, and the rule it uses, FIFO, LRU, or Optimal, decides the fault count. GATE loves the counting numericals and the Belady's anomaly trick; UGC NET and DSSSB lean on the same fault-simulation drills. The skill being tested is simple to state and easy to slip on: simulate the reference string frame by frame without losing track of which page is oldest.
Below are 12 solved MCQs from KnowledgeGate's published question bank, most of them real previous-year questions with the exam and year noted. Attempt each before checking the answer; the explanation stays short on purpose. The full theory with worked simulations sits in the virtual memory learn module.
A note on the deep links: where a question is a GATE PYQ carried inside the GATE course, we link its exact solved page. The questions from other recruitment papers live in the same module's practice sets, so for those the module link above is your entry point.
FIFO and Belady's anomaly
Q1. Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will *(GATE 2001, see the solved page)*
(a) always decrease the number of page faults
(b) always increase the number of page faults
(c) sometimes increase the number of page faults
(d) never affect the number of page faults
Answer: (c) sometimes increase the number of page faults.
Intuition says more frames means fewer faults, and usually that holds. But FIFO is not a stack algorithm, so for certain reference strings adding a frame actually raises the fault count. That counter-intuitive case is Belady's anomaly, which is exactly why the word "sometimes" is correct.
Q2. In which one of the following page replacement policies may Belady's anomaly occur? *(GATE 2009, see the solved page)*
(a) FIFO
(b) Optimal
(c) LRU
(d) MRU
Answer: (a) FIFO.
Belady's anomaly is confined to algorithms that lack the stack property, and FIFO is the classic offender. LRU and Optimal both satisfy the inclusion property, where the pages held with n frames are always a subset of those held with n+1 frames, so they can never fault more with extra frames. That property is what protects them.
Q3. A virtual memory system uses FIFO page replacement and allocates a fixed number of frames. Consider: P: increasing the number of page frames sometimes increases the page fault rate. Q: some programs do not exhibit locality of reference. Which one is TRUE? *(GATE 2007, see the solved page)*
(a) Both P and Q are true, and Q is the reason for P
(b) Both P and Q are true, but Q is not the reason for P
(c) P is false, but Q is true
(d) Both P and Q are false
Answer: (b) Both P and Q are true, but Q is not the reason for P.
P is true because of Belady's anomaly under FIFO, and Q is true because programs certainly exist that reference memory without locality. The catch is causation: the anomaly is a property of FIFO's eviction order, not a consequence of missing locality. So both statements stand, but Q does not explain P.
Q4. Belady's anomaly is related to which function of the operating system? (DSSSB 2022)
(a) process scheduling
(b) deadlock
(c) process synchronisation
(d) page replacement
Answer: (d) page replacement.
The anomaly is defined entirely in terms of page frames and page faults, so it belongs to page replacement and nowhere else. It is a favourite one-line recall question precisely because the distractors name unrelated OS functions. If you can attach the term to FIFO, you can attach it to page replacement.
LRU page replacement
Q5. A process is allocated 3 page frames, none loaded initially. The reference string is 1, 2, 1, 3, 7, 4, 5, 6, 3, 1. How many more page faults occur with LRU than with the optimal policy? *(GATE 2007, see the solved page)*
(a) 0
(b) 1
(c) 2
(d) 3
Answer: (c) 2.
Optimal evicts the page not needed for the longest time and faults 7 times on this string. LRU evicts the least recently used page and faults 9 times, because it cannot see the future the way Optimal can. The difference is 9 minus 7, which is 2.
Q6. Main memory has 4 pages of 16 bytes each, initially empty. The CPU generates virtual addresses 0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92 and uses LRU. How many page faults occur and which pages remain? *(GATE 2008, see the solved page)*
(a) 6 and 1, 2, 3, 4
(b) 7 and 1, 2, 4, 5
(c) 8 and 1, 2, 4, 5
(d) 9 and 1, 2, 3, 5
Answer: (b) 7 and 1, 2, 4, 5.
First convert each address to a page number by dividing by 16, giving the sequence 0, 0, 0, 1, 1, 2, 2, 0, 4, 4, 5, 5, 1, 2, 5, 5. Simulating LRU on those page numbers produces 7 faults, and the four pages left resident at the end are 1, 2, 4 and 5. The address-to-page conversion is the step most candidates rush and get wrong.
Optimal page replacement
Q7. The optimal page replacement algorithm will select the page that *(GATE 2002, see the solved page)*
(a) has not been used for the longest time in the past
(b) will not be used for the longest time in the future
(c) has been used least number of times
(d) has been used most number of times
Answer: (b) will not be used for the longest time in the future.
Optimal, also called OPT or MIN, looks forward and evicts whatever page will be needed farthest in the future, which provably minimises faults. Note the contrast with option (a), which describes LRU by looking at the past. Optimal is a benchmark, not a real algorithm, because no OS truly knows the future reference string.
Q8. A process is allocated 3 page frames, none loaded initially. For the reference string 1, 2, 1, 3, 7, 4, 5, 6, 3, 1, how many page faults occur under the optimal policy? *(GATE 2007, see the solved page)*
(a) 7
(b) 8
(c) 9
(d) 10
Answer: (a) 7.
The first three distinct pages 1, 2 and 3 all fault, filling the frames. At 7 Optimal evicts 2, at 4 it evicts 7, at 5 it evicts 4, and at 6 it evicts 5, while the later 3 and 1 are hits. Counting the faults gives exactly 7, which pairs with Q5 to show LRU trailing Optimal by two on this same string.
Page-fault counting numericals
Q9. A system uses FIFO with 4 page frames, none loaded initially. It accesses 100 distinct pages in some order, then the same 100 pages in reverse order. How many page faults will occur? *(GATE 2010, see the solved page)*
(a) 196
(b) 192
(c) 197
(d) 195
Answer: (a) 196.
The first pass faults on all 100 pages, leaving the last 4 accessed in the frames. On the reverse pass the very first few requests hit those resident pages, so a small number of hits are saved before FIFO starts evicting again. Working it through, the reverse pass adds 96 faults, for a total of 196.
Q10. How many page faults occur for FIFO with 3 frames on the reference string 7, 0, 1, 0, 2, 7, 1, 0, 1, 2? (DSSSB 2022)
(a) 5
(b) 7
(c) 8
(d) 10
Answer: (c) 8.
The first three references 7, 0 and 1 fault while filling the frames. After that, FIFO faults at 2 (evict 7), at 7 (evict 0), at 0 (evict 1), at 1 (evict 2) and finally at 2 (evict 7), with the repeat of 0 in the fourth position and the repeat of 1 in the seventh position hitting. Adding the three initial faults to the five replacements gives 8.
Q11. For the page trace 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5, what percentage of page faults occurs if FIFO is used with 4 frames? (UGC NET 2012)
(a) 8
(b) 9
(c) 10
(d) 12
Answer: (c) 10.
Pages 4, 3, 2 and 1 fault as the frames fill, then 4 and 3 hit. From 5 onward FIFO keeps evicting the oldest page and faults on 5, 4, 3, 2, 1 and again 5, giving 10 faults over 12 references. The question asks for the count labelled as a percentage figure, and 10 is the matching option.
Q12. A program has five virtual pages numbered 0 to 4. If the pages are referenced in the order 0 1 2 3 0 1 4 0 1 2 3 4 with three page frames, the total number of page faults with FIFO will be (UGC NET 2007)
(a) 0
(b) 4
(c) 6
(d) 9
Answer: (d) 9.
FIFO fills on 0, 1 and 2, then faults again as it cycles the oldest page out for 3, 0, 1, 4, 2 and 3. The repeated pattern gives no help because each needed page has just been evicted, a hallmark of the strings examiners build for FIFO. The total lands at 9 faults.
Where these 12 fit in your preparation
The set tracks the exact way this topic is examined: the conceptual FIFO and Belady questions that anchor most papers (Q1 to Q4), the LRU and Optimal simulations that GATE prizes (Q5 to Q8), and the raw fault-counting numericals from GATE, DSSSB and UGC NET (Q9 to Q12). If your counts drift, the fix is almost always process, so redraw the frame table on every step rather than tracking it in your head.
For the theory and more worked simulations, use the virtual memory learn module, and see where page replacement sits in the wider syllabus in our Operating Systems for GATE breakdown. GATE aspirants get the complete OS sequence inside GATE Guidance by Sanchit Sir; those preparing for teaching and PSU papers can browse the GATE CS category page. Simulate each string by hand once, then re-solve from memory a week later.
