Explain the differences between LRU, FIFO, CLOCK, and OPT page replacement algorithms, including typical strengths and weaknesses.

• A. LRU perfectly predicts future references, making it always optimal.
• B. LRU is always the best choice for all workloads; OPT requires no overhead.
• C. CLOCK requires knowledge of future references to function.
• D. OPT is ideal but impractical; LRU, FIFO, and CLOCK are practical approximations.

Answer: (D)

The essential idea is comparing a theoretical best-case strategy with practical real-world approaches. The optimal page replacement algorithm would evict the page whose next use is farthest in the future, because that choice minimizes misses for the exact sequence of references. In principle this is the best possible policy, but it requires perfect knowledge of future memory accesses. Since a running system cannot know future references, implementing this exact strategy is impossible in practice. That’s why it’s described as ideal but impractical.

LRU (least recently used) makes the next-best move by assuming that pages used recently will be used again soon. It evicts the page with the oldest recent access, which tends to work well when programs exhibit temporal locality. The trade-off is that tracking recency information adds overhead—either in hardware counters, timestamps, or a data structure that maintains order—which can be expensive, especially with large numbers of pages. Still, LRU is a common and effective practical approach.

FIFO (first-in, first-out) evicts the oldest loaded page, ignoring how recently or frequently each page has been used. Its simplicity is appealing, but it can perform badly on certain workloads because it doesn’t reflect actual usage patterns. A notable downside is Belady’s anomaly, where increasing the number of frames can unexpectedly increase the number of misses for some sequences.

CLOCK offers a middle ground by approximating LRU with low overhead. It uses a circular list of pages with a reference bit and gives pages a “second chance” before eviction. This results in much cheaper maintenance than full LRU while capturing much of the benefit of recency, making it a practical and widely used real-world replacement policy.

So the statement that best captures the reality is that OPT is ideal but impractical, while LRU, FIFO, and CLOCK are practical approximations with different trade-offs in accuracy and overhead.