6.3Belady's anomaly and stack algorithms
The idea
Belady's anomaly: with FIFO, more frames can mean more faults. Stack algorithms such as LRU and OPT are immune.
Think of it like this: Adding more shelves should never lose you books, but with a poor eviction rule sometimes it does.
Why it exists
It is a favourite true-or-false: which policies can show the anomaly?
How it works
- Take the string 1 2 3 4 1 2 5 1 2 3 4 5.
- FIFO with 3 frames: 9 faults.
- FIFO with 4 frames: 10 faults: more frames, more faults.
- LRU and OPT keep the contents of n frames as a subset of those of n + 1 frames, so more frames never hurt.
Worked example: Run the Belady preset with FIFO
The lab shows faults for 1 to 7 frames: 12, 12, 9, 10, 5, 5, 5. Faults rise from 3 to 4 frames.
Now play with it
- →Switch the policy to LRU and watch the row never increase.
- →Try the cyclic loop string with FIFO and LRU.
| ref | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| frame 1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
| frame 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | |
| frame 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | ||
| fault? | F | F | F | F | F | F | F | hit | hit | F | F | hit |
Faults with 1 to 7 frames using this policy and string:
| 1 frame | 2 frames | 3 frames | 4 frames | 5 frames | 6 frames | 7 frames |
|---|---|---|---|---|---|---|
| 12 | 12 | 9 | 10 | 5 | 5 | 5 |
A red number means more frames caused more faults: Belady's anomaly. It can happen with FIFO, never with LRU or OPT (stack algorithms). Try the Belady preset with FIFO.
| Policy | Stack algorithm? | Belady's anomaly? |
|---|---|---|
| FIFO | no | can happen |
| LRU | yes | never |
| Optimal | yes | never |
| Clock / second chance | no (approximates LRU) | can happen |
Check yourself
Belady's anomaly can occur with
Exam notes (the dense version)
Belady's anomaly: with FIFO, giving a process more frames can cause more page faults. The classic string 1 2 3 4 1 2 5 1 2 3 4 5 gives 9 faults with 3 frames and 10 with 4. Stack algorithms (LRU and OPT) have the inclusion property: the set of pages in n frames is always a subset of the set in n + 1 frames, so they never show the anomaly. More frames never hurt LRU or OPT.
Previous year questions: Virtual Memory (9)
PYQs are grouped by topic, so this is the full set for Virtual Memory; try the ones that match this subtopic. Open all 9 on the topic page.