10 页面置换算法中的Belady现象、工作集、常驻集

Belady现象：在采用FIFO算法时，有时会出现分配的物理页数增加，缺页率反而提高的异常现象。

Belady现象的原因：FIFO算法的置换特征与进程访问内+存的动态特征是矛盾的。与置换算法的目标是不一致的（即替换较少使用的页面）。因此，被它置换出去的页面并不一定是进程不会访问的。

为什么FIFO算法会产生Belady现象，而LRU算法不会产生Belady现象：

解答：因为LRU算法符合栈算法的特点，而FIFO算法不符合栈算法的特点。栈算法的特点是给与的物理页帧越多，所产生的缺页中断的次数就越少。

思考：Clock algorithm 和 Enhanced Clock algorithm 是否会产生Belady现象？

---

LRU、FIFO和Clock的比较：

• LRU算法和FIFO算法本质上都是先进先出的思路。只不过LRU针对页面最近访问的时间来进行排序。所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序（有一个页面最近访问的时间变了）；而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的。所以页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问。那么它最近访问的时间就是它进入内存的时间。换句话说，如果内存当中所有的页面都未曾访问过，那么LRU算法就退化为FIFO算法。

• LRU算法性能比较好，但系统的开销比较大；FIFO算法系统的开销比较小，但有可能会发生Belady现象。因此，折中的办法就是Clock算法，在每一次页面访问时，它不必动态的区调整页面在链表中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再把它移动到链表尾端。对于内存中那些未被访问的页面，Clock算法的表现和LRU一样好；而对于那些曾经被访问过的页面，它不能像LRU算法那样，记住它们准确的位置。

---

前言：之前介绍的各种页面置换算法，都是基于一个前提。即程序的局部性原理。但考虑此原理是否成立？就存在以下两种情况：

• 如果程序的局部性原理不成立。那么各种页面置换算法就没有什么分别，也没有什么意义。
• 如果局部性原理是成立的，那么如何证明它的存在，如何对它进行定量的分析？这就是工作集模型！

工作集：一个进程当前正在使用的逻辑页面的集合。可以用一个二元函数 W(t,^)来表示：

• t是当前的执行时刻
• ^称为工作集窗口（working-set window），即一个定长的页面访问的时间窗口（^是不变的）
• w(t,^)=在当前的时刻t之前的 ^时间窗口当中的所有页面所组成的集合(随着t的变化，该集合也在不断地变化)；
• | W(t,^) |,值工作集的大小，集页面的数目；

工作集大小的变化：进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集的大小也大致稳定；局部性区域的位置改变时，工作集快速的扩张和收缩过渡到下一个稳定值。

常驻集是指在当前时刻，进程实际驻留在内存当中的页面集合。

• 工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面的数目，以及所采用的页面置换算法；
• 如果一个进程的整个工作集都在内存当中，即常驻集包含或者等于工作集，那么进程将很顺利地进行，而不会产生太多的缺页中断（直到工作集发生剧烈的变动，从而过渡到另外一个状态）；
• 当进程常驻集的大小达到某个数目以后，再给它分配更多的物理页面，缺页率也不会明显的下降。

---

提示：为了更好的理解知识点，博主在微信公众号中将操作系统知识进行了重新排版和插入图片。感兴趣的朋友可以扫码进行关注。