LRU 和 LFU 页面置换算法的区别

在本文中，您将学习 LRU 和 LFU 页面置换算法之间的区别。但在讨论差异之前，您需要了解 LRU 和 LFU 页面置换算法。

什么是 LRU 页面置换算法？

LRU 代表“最近最少使用”（Least Recently Used）。它在短时间内跟踪内存中的页面使用情况。它的原理是：过去使用过的页面在未来很可能再次被使用。它会移除内存中已最长时间未使用的页面。LRU 是最广泛使用的算法，因为它比其他方法产生的页面错误更少。

示例

让我们用下面的引用字符串来理解 LRU 页面置换算法。

5 0 1 2 0 3 2 0 3 4 1 0 5 0 4 3 2 1 2 0 1

使用 LRU 页面置换策略时，找出页面错误的数量。同时，考虑页面帧大小为三。

解决方案

引用字符串

5 0 1 2 0 3 2 0 3 4 1 0 5 0 4 3 2 1 2 0 1

总引用字符串数 = 21

总页面错误或页面未命中数 = 14

我们知道：

总页面命中数 = 总引用字符串数 - 总页面错误数

总页面命中数 = 21 - 14 = 7

页面错误概率 = 总页面错误数 / 总引用字符串数

页面错误概率 = 14/21 = 0.67

页面错误百分比 = 总页面错误数 / 总引用字符串数 * 100

页面错误百分比 = 14/21*100 = 67%

说明

1. 首先，内存中有三个空帧。因此，当 5、0、1 进入帧时，它们会按照到达的顺序分配到空帧中。由于 5、0、1 不在内存中，因此发生页面错误。
2. 当 2 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 5，这是最近最少使用的页面。
3. 当 0 进入时，它在内存中。因此，发生页面命中，不发生替换。
4. 当 3 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 1，这是最近最少使用的页面。
5. 当 2、0、3 进入时，它们在内存中。因此，发生页面命中，不发生替换。
6. 当 4 进入时，它不在内存中。因此，发生页面错误，它会替换最近最少使用的页面 2。
7. 当 1 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 0，这是最近最少使用的页面。
8. 当 0 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 3，这是最近最少使用的页面。
9. 当 5 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 4，这是最近最少使用的页面。
10. 当 0 进入时，它在内存中。因此，发生页面命中，不发生替换。
11. 当 4 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 1，这是最近最少使用的页面。
12. 当 3 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 0，这是最近最少使用的页面。
13. 当 2 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 5，这是最近最少使用的页面。
14. 当 1 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 4，这是最近最少使用的页面。
15. 当 2 进入时，它在内存中。因此，发生页面命中，不发生替换。
16. 当 0 进入时，它不在内存中。因此，发生页面错误，它会替换最旧的页面 3，这是最近最少使用的页面。
17. 当 1 进入时，它在内存中。因此，发生页面命中，不发生替换。

LRU 页面置换算法的优点和缺点

LRU 页面置换算法有各种优点和缺点。这些优点和缺点如下：

优点

1. LRU 不会发生 Belady 异常。
2. 主内存中已最长时间未使用的页面将被选为替换。
3. 它产生的页面错误比任何其他页面置换算法都少。因此，LRU 是最常用的方法。
4. 它是一个非常有效的算法。
5. 它有助于全面分析。

缺点

1. 它不容易实现，因为它需要硬件支持。
2. 它成本高昂且更复杂。
3. 它需要额外的数据结构。

什么是 LFU 页面置换算法？

LFU 页面置换算法代表“最不常用”（Least Frequently Used）。在 LFU 页面置换算法中，移除在给定时间段内访问次数最少的页面。它替换最不常用的页面。如果页面的频率保持不变，则首先替换先进入的页面。

示例

让我们用下面的引用字符串来理解 LFU 页面置换算法。

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

使用 LFU 页面置换策略时，找出页面错误的数量。同时，考虑页面帧大小为三。

解决方案

引用字符串

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

总引用字符串数 = 16

总页面错误或页面未命中数 = 12

我们知道：

总页面命中数 = 总引用字符串数 - 总页面错误数

总页面命中数 = 16 - 12 = 4

页面错误概率 = 总页面错误数 / 总引用字符串数

页面错误概率 = 12/16 = 0.75

页面错误百分比 = 总页面错误数 / 总引用字符串数 * 100

页面错误百分比 = 12/16*100 = 75%

说明

1. 首先，内存中有三个空帧。因此，当 7、0、2 进入帧时，它们会按照到达的顺序分配到空帧中。由于 7、0、2 不在内存中，因此发生页面错误。
2. 当 4 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 7。
3. 当 3 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 0。
4. 当 1 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 2。
5. 当 4 进入时，它在内存中。因此，发生页面命中，不发生替换。
6. 当 7 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 3。
7. 当 2 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 1。
8. 当 0 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 7。
9. 当 4 进入时，它在内存中。因此，发生页面命中，不发生替换。
10. 当 3 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 2。
11. 当 0、3 进入时，它们在内存中。因此，发生页面命中，不发生替换。
12. 当 2 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 0。
13. 当 7 进入时，它不在内存中。因此，发生页面错误，替换最不常用的页面 2。

LRU 和 LFU 页面置换算法之间的主要区别

在这里，您将学习 LRU 和 LFU 页面置换算法之间的主要区别。LRU 和 LFU 页面置换算法之间的各种区别如下：

1. LRU 代表“最近最少使用”页面置换算法。相比之下，LFU 代表“最不常用”页面置换算法。
2. LRU 页面置换算法在短时间内跟踪内存中的页面使用情况。相比之下，在 LFU 页面置换算法中，移除在给定时间段内访问次数最少的页面。
3. LRU 替换已在内存中存放最长时间但未使用的页面。相比之下，LFU 替换最不常用的页面。

LRU 和 LFU 页面置换算法的直接比较

在这里，您将学习 LRU 和 LFU 页面置换算法之间的直接比较。LRU 和 LFU 页面置换算法之间的主要区别如下：