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.
The 12 questions run from GATE 2001 to DSSSB 2022, and each one carries its exam and year. Attempt every one on paper before reading the answer, then use the explanation to find where your frame table drifted. The full theory with worked simulations sits in the virtual memory learn module.
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, worked solution)
(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, worked solution)
(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, worked solution)
(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, worked solution)
(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. Q8 takes the same string and works the Optimal side out eviction by eviction.
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, worked solution)
(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, worked solution)
(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, worked solution)
(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, worked solution)
(a) 196
(b) 192
(c) 197
(d) 195
Answer: (a) 196.
The first pass faults on all 100 pages, leaving the 4 most recently accessed in the frames. The reverse pass opens with exactly those 4 pages, so its first 4 requests hit, and every one of the remaining 96 pages then faults. That gives 100 plus 96, which is 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 stem asks for a percentage while all four options are plain counts, a slip in the original paper, so count the faults and mark 10.
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. Only three references hit, the third 0, the third 1 and the second 4, because every other needed page had just been evicted, which is the hallmark of the strings examiners build for FIFO. The total lands at 9 faults.
How page replacement is examined
Page replacement shows up in three shapes. The conceptual FIFO and Belady questions anchor most papers (Q1 to Q4), the LRU and Optimal simulations are what GATE prizes (Q5 to Q8), and the raw fault-counting numericals come from GATE, DSSSB and UGC NET alike (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, and the GATE CS category page gathers the rest of the operating systems posts. Simulate each string by hand once, then re-solve from memory a week later.
