Belady's Anomaly: FIFO vs LRU vs Optimal in Python
Explore page replacement policies for GATE CS with hand-trace methods and a Python script to verify FIFO, LRU, and Optimal algorithms.
Stock photo for illustration only, not from the actual event
- GATE CS page replacement questions typically involve reference strings, frame counts, and specific policies.
- The author wrote a small Python checker to simulate and verify FIFO, LRU, and Optimal memory management policies.
- FIFO policy can exhibit Belady's Anomaly where increasing the number of frames leads to more page faults.
- LRU maintains the stack property, meaning pages held with k frames are always a subset of k+1 frames.
Page replacement questions in GATE Computer Science exams mostly rely on counting reference strings, frame counts, and specific policies to write down rows of letters. A useful skill is mastering a fast hand-trace method without overthinking, alongside a reliable way to check practice problems using code.
Schoolabe's GATE memory management chapter uses a reference string with 3 frames as a worked example. The textbook instructs readers to count FIFO carefully using a queue without printing the final answer, so the author compiled all three policies and numbers into a single runnable Python file.
Stock photo for illustration only, not from the actual event
For hand-tracing, the author writes out full frame contents under every reference rather than just noting F or hits. For FIFO, the oldest page is underlined, while LRU rewrites frames in recency order every time. Although slower, this meticulous tracking makes spotting counting errors much easier.
LRU also results in seven faults here, proving that LRU does not always outperform FIFO on every given string. Optimal achieves five faults, serving as the offline lower bound because it requires future knowledge that real systems lack. If a hand-trace beats this optimal floor, a counting mistake has occurred.
Belady's Anomaly remains a classic operating systems trap question. While adding more memory frames should theoretically reduce page faults, the FIFO policy can occasionally trigger more faults when given extra capacity due to its arrival-order mechanism. Understanding this anomaly through Python simulations helps bridge theoretical computer science concepts with practical computational verification.
The chapter notes that FIFO can demonstrate Belady's anomaly as a favorite exam trap. The textbook string extended by three pages (1 2 3 4 1 2 5 1 2 3 4 5) tested with 4 frames still yields 7 faults for FIFO.
Meanwhile, LRU on the extended string drops its fault count from 10 to 8 as expected due to the stack property. Pages held by LRU with k frames always form a subset of those held with k+1 frames, whereas FIFO tracks arrival order instead of actual usage.
To check how common this anomaly is, the author generated random strings of 12 references across pages 1 to 5 with a fixed seed for reproducibility, comparing 3 frames against 4. Questions asking which policy can fault more with frames can be answered immediately if the policy is LRU or Optimal, as only FIFO triggers this anomaly.
Source: Dev.to
Found something wrong in this article? Report an issue with this article
Comments
Leave a Comment