XI.贝拉迪现象与 LRU、FIFO、时钟的比较

1、Belady现象

\qquad 在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象
\qquad Belady现象产生的原因： FIFO算法的置换特征与进程访问内存的动态特征时矛盾的，与置换算法的目标（即替换较少使用的页面）不一致的，因此，被他置换出去的页面并不一定是进程不会访问的。
\qquad 只有FIFO算法有Belady现象的缺陷，其他算法如LRU算法没有Belady算法这种缺陷，因为LRU算法符合一种“栈算法”的特点，所分配的物理页帧越多，则产生的缺页次数越少。

2、LRU、FIFO和clock的比较

\qquad LRU算法和FIFO本质上都是先进先出的思路，只不过LRU时针对页面最近访问的时间来进行排序，所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序(因为其中某个页面的最近访问时间改变了)；而FIFO是针对页面进入内存的时间来进行排序的，这个时间是固定不变的，所以各个页面之间的先后顺序时固定的。如果一个页面在进入内存后没有被访问，那么他的最近访问时间就是他进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就退化为FIFO算法。clock是使用了一些内存中的信息(访问位，脏位等)来模拟LRU算法。
\qquad LRU算法性能较好，但系统开销较大；FIFO算法系统开销较小，但可能会发生Belady现象。因此，这种的办法就是使用clock算法，在每一次页面访问的时候，他不必动态地去调整该页面在链表中的顺序，而仅仅是做一个标记，然后等到发生缺页中断时，再把它移动到链表末尾。对于内存当中那些未被访问的页面，clock和LRU算法表现一样好；而对于那些曾经被访问过的页面，他不能像LRU算法那样，准确记录他们的位置。

THE END

陈老师原视频链接：
https://www.bilibili.com/video/BV1wW41117GS?p=29