Why doesn't LRU suffer from anomaly?

Question

I have a question about page replacement algorithms. FIFO suffers from Belady Anomaly , but the LRU does not. Does anyone know why LRU does not suffer? I searched for a reason on the Internet, but no luck.

Answer 1

Since LRU is a stacking algorithm, and the use of k frames will always be a subset of k + n frames for LRU. Thus, any k-errors that may occur for k + n frames will also occur for k frames, which, in turn, means that the LRU does not suffer from Belady anomalies.

Answer 2

Because FIFO assumes that the fact that the page takes up memory for a long time, that it is the safest to replace, where in fact it is simply not so. Rather, if the FIFO fails, it is statistically that if the page was frequently called, it would rather be called than the other page that has been called recently. In other words, frequency determines page load much better than age.

Answer 3

As with Caspar, however, I found the explanation from my tutorial (slightly edited) a little more understandable.

[LRU belongs] to a class of page replacement algorithms called stack algorithms [which] can never exhibit the Beladys anomaly.

The stack algorithm is an algorithm for which it can be shown that the set of pages in memory for N frames is always a subset of the set of pages that will be in memory with frames N + 1. [Therefore, an additional frame will never cause an additional page error.]

To replace LRU, the set of pages in memory will be the N most recent links. If the number of frames is increased, these N pages will still be the last, and they will still be in memory.

Silberschatz, A., Galvin, PB and Gagne, G. (2014). Operating System Concepts (9th ed.). Singapore: Wiley.