当前位置：首页 > news >正文

《操作系统 - 清华大学》6 -7：局部页面置换算法：Belady现象

news 来源：原创 2025/7/5 14:51:09

文章目录

1. 定义
2. LRU、FIFO和Clock的比较

1. 定义

在这里插入图片描述
局部页面置换算法的特点是针对一个正在运行的程序，它访问内存的情况，访问页的情况，来决定应该采取什么样策略，把相应的页替换出去，站在算法本身角度来考虑置换哪个页。

Belady现象是比较异常现象，当给运行程序分配的物理业越多，按道理来说它产生缺页次数应该越少，但是如果采取某些页面置换算法之后，会发现出现相反的情况，给它分配的物理页越多，产生缺页的次数反而也跟着增加。

FIFO 算法就是这么一种算法，在给它增加更多的物理页之后，并没有说缺页次数减少，反而缺页次数增加了，什么原因？

原因在于 FIFO 算法并没有考虑程序访问内存的动态特征，算法本身的替换策略和访问内存的动态特征是矛盾的，目标是不一致的，替换的页面并不是当前程序不会访问的页面。

FIFO算法的Belady现象：

增加物业帧，从3变成4，但是在同样访问序列下，它的缺页次数从9变成10，这不是我们预期的，给它更多的物理资源，给它更多的物理业，结果它产生缺页次数更加多了，期望是少。
那怎么来解决这个现象？
在看另一种 LRU 算法：

同样的访问序列，LRU 算法分三个物业页帧，会产生十次缺页错误，但是如果给它分4个物理页帧，它只会产生8次缺页错误。这是符合预期的，给他物理资源越多，缺页错误次数就越少。
那为什么 LRU 算法会比 FIFO 算法在这方面要做得更好呢？
LRU 算法符合栈算法的特点，意味着给物业资源越多，它产生的缺页次数就越少。但是 FIFO 算法不满足栈算法特点，那么就不会产生这种现象。

2. LRU、FIFO和Clock的比较

在这里插入图片描述

LRU 算法和 FIFO算法在处理过程中都可以用链表或者栈来表示驻留在内存中次序，但是 LRU 算法除了考虑驻留时间之外，还考虑最近访问时间，如果最近这个页被访问到了，会把它从列表中取出来放头上去。但是 FIFO 没有这个过程，那这也就是 FIFO 和 LRU 很重的区别。如果程序具有局部性特点，LRU算法就可以更好适应局部性特点，产生更少的缺页次数。

但是换个角来说，缺页次数不光是算法本身的问题，还和程序本身特点相关，如果程序没有局部性特征，那其实 LRU 算法和 FIFO 算法最后的结果有可能一样，就是 LRU 可能会退化为 FIFO 算法。

而 Clock 算法其实是对 LRU 算法的近似。因为 Clock 算法只用一个 bit 或者两个 bit来表示访问时间，很明显一两个 bit 不可能精确地表示出一段时间内不同的页面访问先后顺序，只是近似，所以本质上Clock算法也是一种类似于 LRU 算法的一种算法，它使用一些硬件的bit，来模拟访问时间先后顺序，所以它可以有效地去逼近或者模拟 LRU 算法，而且它的开销也还很小，这是 Clock 算法的特点。

在某种不具有局部性的页面访问序列下，LRU 会退化为 FIFO，那 Clock算法也可能会退化为 FIFO 算法，其实可以看出来，如果要有效减少缺页次数，除了算法之外，还对本身访问序列有一定要求，最好是具有局部性访问特征，那么 LRU算法 Clock 算法才能发挥效果。如果算法本身不具有局部性，那么 LRU FIFO Clock 就没什么区别了。

另一方面 LRU 算法开销比较大，FIFO 算法开销小，但是它的效率并不好，所以折中Clock算法， Clock 算法本质上也是 FIFO 算法，但是在 FIFO 算法基础上增加了对页面访问时间的记录，但不是精准记录，而是粗略记录，根据 access bit 或者 dirty bit 来记录这个页的访问情况，开销比较小，效果又接近 LRU，所以说它是更加实际，相对来说比 LRU 和 FIFO 都要好。

文章目录

1. 定义

2. LRU、FIFO和Clock的比较

相关文章：