MFU和LRU页面置换算法的比较

Question

在什么情况下，MFU（最常用）页面替换算法的性能优于LRU（最不常用）？在什么情况下它比LRU更差？ 我在哪里可以找到超出MFU页面替换算法基本定义的信息？

- Grisha

Answer 1

通常，我看到MFU缓存被用作主要缓存，由一个使用LRU替换算法的二级缓存作为备用缓存（一个MRU缓存）。这样做的想法是最近使用的东西将保留在主缓存中，从而获得非常快速的访问。这减少了在MRU缓存中看到的“翻滚”，当少数项被非常频繁地使用时。它还防止因为长时间未使用而从缓存中移除那些常用的项。

如果您有很少的经常引用的项目和大量的不经常引用的项目，则MFU效果很好。例如，典型的桌面用户可能有三四个他每天多次使用的程序，以及他极少使用的数百个程序。如果您想通过将程序缓存在内存中来改善他的体验，以使它们快速启动，您最好缓存那些他非常频繁使用的东西。

另一方面，如果您有大量随机引用的项，或某些项比其他项稍微更频繁地访问，或者通常以批处理方式引用项目（例如，项目A在短时间内多次访问，然后完全不再访问），则LRU缓存驱逐方案可能更好。

- Jim Mischel

---

我不确定是否漏掉了什么，但这难道不是与所解释的MRU算法相反吗 - https://en.wikipedia.org/wiki/Cache_replacement_policies#Most_recently_used_(MRU) - MRU算法在旧项目更可能被访问的情况下最有用。 - seeker

https://en.wikipedia.org/wiki/Cache_replacement_policies#Most_recently_used_(MRU) - seeker

@seeker 是的，这个答案混淆了术语（第二句话应该是“最常用的事物”），并使用MFU缓存来表示具有LFU替换算法的缓存。根据我的经验，这不是正确的术语。LRU缓存是指驱逐最近最少使用的项目的缓存，因此MFU缓存应该是一种驱逐最常使用的项目的缓存。 - Kyle Chadha

有人能告诉我为什么MFU在实践中不常用或可能会出现的问题吗？ - Tianna Wrona

Answer 2

最近最少使用（LRU）页面置换算法

在此算法中，需要替换最长时间未使用的页面。

LRU页面置换算法的优点：

1. 可以进行全面的统计分析。
2. 永远不会受到Belady异常的影响。

最常用（MFU）页面置换算法

实际上，MFU算法认为最经常使用的页面不会立即需要，因此将替换MFU页面。

例如：考虑以下参考字符串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

缓冲区大小：3 字符串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 7 7 2 2 2 0 4 2 2 0 0 2 2 2 0 0 7 7 7

  0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0

    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

- priyanka

Answer 3

我一直在苦苦寻找MFU的用例，因为它经常被与MRU混淆。MFU最常引用的用例是：

最常使用（MFU）页面替换算法基于这样一个论点：计数最小的页面可能刚刚被带入并且尚未被使用。

但很明显他们谈论的是MRU - 最近使用的缓存。

我所能找到的是一篇论文，其中描述了同时使用MFU和LFU的情况，即将最常使用的参考移动到主缓存以实现更快的访问，并将最不常使用的参考移动到次要缓存。这是我所能找到的MFU的唯一用例。

- sam