Why LRU doesn't suffer Belady's Anomaly?

I have a quest开发者_运维技巧ion about page replacement algorithms. FIFO suffers from Belady's Anomaly but LRU doesn't. Does anyone know why LRU doesn't suffer? I've been searching for the reason on the internet but no luck.

---

Because LRU is a stacking algorithm, and using k frames will always be a subset of k + n frames for LRU. Thus, any page-faults that may occur for k + n frames will also occur for k frames, which in turn means that LRU doesn't suffer Belady's anomaly.

---

Because FIFO assumes that the mere fact that a page has been occupying memory for a long time that it is the safest to replace, where in reality that simply isn't the case. Rather, where FIFO fails is that statistically, if a page has been called frequently, it's more likely to be called again than another page which has been called recently. In other words, frequency is a far better determiner of page loading than age.

---

Similar to Caspar's answer, however I found the explanation from my textbook (slightly edited) to be a bit more clear.

[LRU belongs] to a class of page-replacement algorithms, called stack algorithms, [which] can never exhibit Belady’s anomaly.

A 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 would be in memory with N + 1 frames. [Therefore an additional frame will never cause an additional page fault.]

For LRU replacement, the set of pages in memory would be the N most recently referenced pages. If the number of frames is increased, these N pages will still be the most recently referenced and so will still be in memory.

Silberschatz, A., Galvin, P. B., & Gagne, G. (2014). Operating System Concepts (9th ed.). Singapore: Wiley.