Belady现象是操作系统虚拟存储技术下，请求分页技术采用FIFO置换算法所特有的问题。在网上搜了一圈，都在描述该现象，却没有谈论该现象是如何形成的，本文就此进行讲解。（不了解Belady的读者可以搜一下，此处不再赘述）

        现在假设有两个操作系统os1、os2驻留集分别为m,n，且0<m<n。

        为方便描述，需要引入两个个人定义的概念：

        1.稳定区：即在os2的驻留集中，存在一个大小为m的区域，其页面次序与os1完全一致。

        2.不稳定区：即os2的驻留集中除开稳定区的部分。

        Belady发生的两个必要条件：

        1.os2不包含os1的全部页面。

        2.接下来访问的页面在os1中有，而os2没有。

        而FIFO算法会产生Belady现象的根本原因则是，在os2中，尽管驻留集更大，但并不是一直存在一个“稳定区”。这会导致一个结果：os1与os2换出的页面有可能不一致。如果os2换出的页面p2是下一步将要访问的，且os1中仍旧持有p2，此时os2就将比os1多置换一次，便产生了Belady现象。

        为什么FIFO算法不存在稳定区？

        这是由于FIFO算法完全按照顺序来进行置换。我们观察以下访问页号串：S=1,2,3,4,1

        以m=3,n=4为例。初始状态都为空。

        当os1=os2=[1,2,3]的时候，此时仍旧处于稳定的状态。再进行一步，os1=[2,3,4]，os2=[1,2,3,4]，此时仍存在稳定区[2,3,4]，但接下来的一步os1与os2将进行的置换情况就会丧失这个稳定性。我们看看下一步会变成什么样：os1=[3,4,1]，os2=[1,2,3,4]，很明显此时已经不存在稳定区了，但是现在还需要做一点点小的调整才能观察到Belady现象，这是因为os2完全包含了os1的页面，任何能够导致os2置换的页面，也都会导致os1置换。

        很显然，只需要换出页面1，就满足Belady现象的条件1，为达到这样的效果，我们让下一步访问的页面号为5。此时os1=[4,1,5],os2=[2,3,4,5]，再访问页面1，os1=[4,1,5],os2=[3,4,5,1]，发生置换。截止此时，os1置换次数为6次，os2的置换次数也为6次，通过这样的方法，我们可以让os1与os2转了一圈后，置换次数相等。但是，我们发现，此时os1中任何页面都包含在os2中，且次序都不会比os2晚，这意味着os1中的任何一页从os2调出，必然在此之前或者同时从os1中调出，也就是说，os2置换次数不会多于os1。

        因此，我们得到了Belady现象的另外两个重要构建准则：

        1.os2中不存在稳定区（否则必然无法满足准则2）

        2.os1中只有次序晚于os2的页面，才有可能使os2置换而os1保持不动。

        我们重新构造一次访问顺序：1,2,3,4,1,2

        此时os1=[4,1,2],os2=[1,2,3,4]，分别发生了6次，4次置换。这个时候1,2两个页面的，在os1中的次序都晚于os2，因此我们可以利用这两个页面完成置换次数的持平。而页面4是先于os2的，所以先处理掉它。因此，我们继续访问序列：5,1,2。我们先看看持平的结果，os1=[1,2,5],os2=[4,5,1,2]，（此时os1、os2置换次数均为7次）这时候我们惊讶地发现了，5在os1的位置竟然先于os2！换句话说，只要把5从os2推出去，就可以故技重施。继续访问序列：6,7。os1=[5,6,7],os2=[1,2,6,7]，此时都置换了9次。这时候已经满足了Belady条件，我们直接访问页面5！os1=[5,6,7]，os2=[2,6,7,5]，这时候os1一共置换了9次，而os2置换了10次，Belady现象构造成功。【附：完整访问序列为：1,2,3,4,1,2,5,1,2,6,7,5】

        核心的问题来了，为什么序列1,2,3,4,1,2,5就能成功构建Belady现象，1,2,3,4,1,5则不可以？

        这是因为，在本例中n=4,m=3,他们的长度差为1。如果有办法在打破稳定状态的时候，让新增的那个页面（本例中就是页面5），可以在os2中前进超过x次，而在os1中前进y次，且x-y>n-m=1的时候，就能保证页面5在os2中的次序先于os1了。而x的最大值则是从稳定状态开始，一直到os1与os2置换次数追平，所需要的置换次数。说得有点绕，本例中也就是从os1=[2,3,4],os2=[1,2,3,4]开始，下一步就将打破稳定状态，并且延续到了os1=[4,1,2],os2=[1,2,3,4]，再下一步os2开始了追平os1的路程。因此本例中采用的方式是令y=0,x=2。

        总结起来，要构建Belady现象，第一要务是能够满足两个必要条件，而这两个必要条件的又有两个构建准则。从这个思想出发，我们来看看LRU算法是如何成功避免Belady现象的。

        依然采用Belady现象访问序列：1,2,3,4,1,2,5,1,2,6,7,5

        先看访问序列：1,2,3

        此时os1=[1,2,3],os2=[1,2,3]。设此时状态为A下一步能访问的不外乎两种情况：

        1、1,2,3中访问一页，其结果分别为os1=[2,3,1],os2=[2,3,1];os1=[1,3,2],os2=[1,3,2];os1=[1,2,3],os2=[1,2,3]。我们可以发现，这种情况下os1与os2始终保持这稳定区，且该情况等同于os1=[1,2,3],os2=[1,2,3]，因此这一步相当于之后会遇到的访问情境，与状态A相同，只能考虑另外一种情况是否能打破稳定状态。

        2、1,2,3之外访问一页，不妨设下一步访问页面4。此时os1=[2,3,4],os2=[1,2,3,4]，可以发现，os1与os2仍然具有稳定区，但此时os1、os2并不完全相同。设此时状态为B

        继续状态B之后的情况，再下一步存在三种可能：

       1、在2、3、4中访问，不妨假设访问了页面3，此时os1=[2,4,3],os2=[1,2,4,3]，仍然存在稳定区，且此时状态等同于状态B，后续变化不必考虑。（页面2、4也一样）

        2、访问页面1，此时os1=[3,4,1],os2=[2,3,4,1]。此时依然存在稳定区，且与状态B等同，亦不作后续考虑。

        3、在页面1、2、3、4之外访问，不妨假设访问页面5，此时os1=[4,3,5],os2=[2,4,3,5]，此时状态仍然与B等同。

        因此状态LRU算法在状态A之后只可能变为状态A或状态B，在状态B之后的算法将永远保持状态B的稳定状态，且状态A、B都是稳定状态，不可能发生Belady现象。

        其余算法也都无法同时满足两个必要条件，或者两个准则，因此无法构建Belady现象。当然，我们也可以根据这两个条件、两个准则，自己研究一个能够实现Belady现象的置换算法。