Question

Which of the following page replacement algorithms suffers from Belady's Anomaly ?

a) Optimal replacement
b) LRU
c) FIFO
d) Both optimal replacement and FIFO

Answer 1

Belady's Anomaly refers to the counter-intuitive situation where the FIFO page replacement algorithm can incur more page faults when more frame memory is added. Neither Optimal replacement nor LRU replacement algorithms suffer from this anomaly.

Step-by-step explanation:

The page replacement algorithm that suffers from Belady's Anomaly is FIFO (First-In, First-Out). Belady's Anomaly is a counter-intuitive situation where, under certain circumstances, increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern. This phenomenon was first observed by Les Belady in 1966, and it demonstrates that FIFO can perform worse with more memory. In contrast, the Optimal replacement algorithm, which replaces the page that will not be used for the longest period of time in the future, and the LRU (Least Recently Used) algorithm, which replaces the least recently used pages, do not suffer from Belady's Anomaly. Both the optimal replacement and LRU algorithms are designed in a way that adding more frames will either lower or keep constant the number of page faults.