Belady's anomaly — OS, DBMS & Networks Aptitude Question
Belady's anomaly: Belady's anomaly — adding a frame producing more page faults — can occur with which… Answer and worked solution on CodeKairo.
- Topic: OS, DBMS & Networks
- Section: Programming MCQs
- Difficulty: Easy
- Time target: 75 seconds
Question
Belady's anomaly — adding a frame producing more page faults — can occur with which page-replacement algorithm?
Options
- FIFO
- LRU
- Optimal (OPT)
- Both LRU and Optimal
Show the answer and the worked solution
Correct answer: A. FIFO
Worked solution
- LRU and OPT are stack algorithms: the set of pages resident with n frames is always a subset of the set resident with n + 1 frames, so extra frames can never add faults.
- FIFO ranks pages only by arrival, which does not have that nesting property.
- The classic string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 gives FIFO 9 faults with three frames but 10 with four.
Answer: FIFO.
The idea
The stack property is the whole explanation. Second-chance and clock, being FIFO in disguise, can show the anomaly too, while anything ranking pages by a fixed priority cannot.
Shortcut. OPT is optimal for every frame count, so an extra frame cannot hurt it, and LRU shares its nesting property; that rules out three options at once.
Common trap. "LRU" tempts as the other everyday policy, but LRU is a stack algorithm, so more frames can never cause more faults.