Page replacement, and the GATE trap in Belady's anomaly
FIFO, LRU and Optimal worked end to end on one reference string, plus the question pattern that catches people every year.
Page replacement questions are near-guaranteed marks because the algorithms are mechanical. The marks get lost in bookkeeping, not in understanding.
Reference string, three frames throughout:
7 0 1 2 0 3 0 4 2 3 0 3 2FIFO
Evict the page that arrived first, regardless of use.
7 -> [7] fault 1
0 -> [7 0] fault 2
1 -> [7 0 1] fault 3
2 -> [0 1 2] fault 4 evict 7
0 -> [0 1 2] hit
3 -> [1 2 3] fault 5 evict 0
0 -> [2 3 0] fault 6 evict 1
4 -> [3 0 4] fault 7 evict 2
2 -> [0 4 2] fault 8 evict 3
3 -> [4 2 3] fault 9 evict 0
0 -> [2 3 0] fault 10 evict 4
3 -> [2 3 0] hit
2 -> [2 3 0] hit10 faults.
LRU
Evict the page unused for longest. Same string:
7 0 1 -> three faults, resident [7 0 1]
2 -> evict 7 fault 4 [0 1 2]
0 -> hit
3 -> evict 1 fault 5 [2 0 3]
0 -> hit
4 -> evict 2 fault 6 [0 3 4]
2 -> evict 3 fault 7 [0 4 2]
3 -> evict 0 fault 8 [4 2 3]
0 -> evict 4 fault 9 [2 3 0]
3 -> hit
2 -> hit9 faults.
Optimal
Evict whatever is used furthest in the future. Unimplementable, and that is the point: it is the lower bound you compare against. 7 faults on this string.
The trap
The question is rarely “count the faults”. It is usually some form of:
Increasing the number of frames from 3 to 4 increases the number of page faults. Which algorithm is in use?
This is Belady’s anomaly. FIFO can fault more with more frames. LRU and Optimal cannot, because they are stack algorithms: the set of pages resident with n frames is always a subset of the set resident with n+1 frames. That subset property is what rules out the anomaly, and naming it is what earns the mark.
So: anomaly possible means FIFO, or Second Chance which inherits it. Anomaly impossible means LRU, Optimal, or any algorithm with the stack property.
Two more that appear regularly
Effective access time. With hit ratio h, memory access time m, and fault service time s:
EAT = h*m + (1 - h)*sRead carefully whether the question counts the failed memory access before the fault is serviced. That single detail flips the answer, and it is deliberate.
TLB plus page table. With multi-level page tables a TLB miss costs several memory accesses, not one. Count the levels the question specifies rather than assuming two.
— Ishaan Sandhwar