操作系统 LRU和LFU页面置换算法的区别

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

什么是LRU页面置换算法

LRU指的是 最近最少使用 。它在内存中跟踪页面的使用情况，时间跨度较短。它的工作原理是在过去被频繁使用的页面未来可能会再次被显著使用。它会删除未在内存中被使用的最长时间的页面。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’s Anomaly的影响。
2. 内存中未使用时间最久的页面将被选择进行替换。
3. 它比其他页面替换算法更少地发生页面错误。因此，LRU是最常用的方法。
4. 这是一个非常有效的算法。
5. 它有助于完整的分析。

缺点

1. 实现不容易，因为它需要硬件辅助。
2. 它昂贵且更复杂。
3. 它需要额外的数据结构。

什么是LFU页面替换算法

LFU页面替换算法代表 最不常用 . 在LFU页面替换算法中，会选择在给定时间段内访问次数最少的页面进行替换。它替换最不常用的页面。如果页面的访问频率保持恒定，那么最先进行替换的是先到达的页面。

示例：

让我们看下面的参考字符串以了解LFU页面替换算法。

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

当使用LFU页面替换策略时，找出页面错误的数量。同时，假设页面帧的大小为3。

解决方案：

参考字符串：

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页面置换算法之间的主要区别如下所示：