????????Belady現(xiàn)象是操作系統(tǒng)虛擬存儲(chǔ)技術(shù)下，請(qǐng)求分頁(yè)技術(shù)采用FIFO置換算法所特有的問題。在網(wǎng)上搜了一圈，都在描述該現(xiàn)象，卻沒有談?wù)撛摤F(xiàn)象是如何形成的，本文就此進(jìn)行講解。（不了解Belady的讀者可以搜一下，此處不再贅述）
? ? ? ? 現(xiàn)在假設(shè)有兩個(gè)操作系統(tǒng)os1、os2駐留集分別為m,n，且0<m<n。
????????為方便描述，需要引入兩個(gè)個(gè)人定義的概念：
? ? ? ? 1.穩(wěn)定區(qū)：即在os2的駐留集中，存在一個(gè)大小為m的區(qū)域，其頁(yè)面次序與os1完全一致。
? ? ? ? 2.不穩(wěn)定區(qū)：即os2的駐留集中除開穩(wěn)定區(qū)的部分。
? ??????Belady發(fā)生的兩個(gè)必要條件：
? ??????1.os2不包含os1的全部頁(yè)面。
? ??????2.接下來訪問的頁(yè)面在os1中有，而os2沒有。
????????而FIFO算法會(huì)產(chǎn)生Belady現(xiàn)象的根本原因則是，在os2中，盡管駐留集更大，但并不是一直存在一個(gè)“穩(wěn)定區(qū)”。這會(huì)導(dǎo)致一個(gè)結(jié)果：os1與os2換出的頁(yè)面有可能不一致。如果os2換出的頁(yè)面p2是下一步將要訪問的，且os1中仍舊持有p2，此時(shí)os2就將比os1多置換一次，便產(chǎn)生了Belady現(xiàn)象。
? ? ? ? 為什么FIFO算法不存在穩(wěn)定區(qū)？
? ? ? ? 這是由于FIFO算法完全按照順序來進(jìn)行置換。我們觀察以下訪問頁(yè)號(hào)串：S=1,2,3,4,1
? ? ? ? 以m=3,n=4為例。初始狀態(tài)都為空。
? ? ? ? 當(dāng)os1=os2=[1,2,3]的時(shí)候，此時(shí)仍舊處于穩(wěn)定的狀態(tài)。再進(jìn)行一步，os1=[2,3,4]，os2=[1,2,3,4]，此時(shí)仍存在穩(wěn)定區(qū)[2,3,4]，但接下來的一步os1與os2將進(jìn)行的置換情況就會(huì)喪失這個(gè)穩(wěn)定性。我們看看下一步會(huì)變成什么樣：os1=[3,4,1]，os2=[1,2,3,4]，很明顯此時(shí)已經(jīng)不存在穩(wěn)定區(qū)了，但是現(xiàn)在還需要做一點(diǎn)點(diǎn)小的調(diào)整才能觀察到Belady現(xiàn)象，這是因?yàn)閛s2完全包含了os1的頁(yè)面，任何能夠?qū)е耾s2置換的頁(yè)面，也都會(huì)導(dǎo)致os1置換。
? ? ? ? 很顯然，只需要換出頁(yè)面1，就滿足Belady現(xiàn)象的條件1，為達(dá)到這樣的效果，我們讓下一步訪問的頁(yè)面號(hào)為5。此時(shí)os1=[4,1,5],os2=[2,3,4,5]，再訪問頁(yè)面1，os1=[4,1,5],os2=[3,4,5,1]，發(fā)生置換。截止此時(shí)，os1置換次數(shù)為6次，os2的置換次數(shù)也為6次，通過這樣的方法，我們可以讓os1與os2轉(zhuǎn)了一圈后，置換次數(shù)相等。但是，我們發(fā)現(xiàn)，此時(shí)os1中任何頁(yè)面都包含在os2中，且次序都不會(huì)比os2晚，這意味著os1中的任何一頁(yè)從os2調(diào)出，必然在此之前或者同時(shí)從os1中調(diào)出，也就是說，os2置換次數(shù)不會(huì)多于os1。
????????因此，我們得到了Belady現(xiàn)象的另外兩個(gè)重要構(gòu)建準(zhǔn)則：
? ? ? ? 1.os2中不存在穩(wěn)定區(qū)（否則必然無(wú)法滿足準(zhǔn)則2）
? ? ? ? 2.os1中只有次序晚于os2的頁(yè)面，才有可能使os2置換而os1保持不動(dòng)。
? ? ? ? 我們重新構(gòu)造一次訪問順序：1,2,3,4,1,2
? ? ? ? 此時(shí)os1=[4,1,2],os2=[1,2,3,4]，分別發(fā)生了6次，4次置換。這個(gè)時(shí)候1,2兩個(gè)頁(yè)面的，在os1中的次序都晚于os2，因此我們可以利用這兩個(gè)頁(yè)面完成置換次數(shù)的持平。而頁(yè)面4是先于os2的，所以先處理掉它。因此，我們繼續(xù)訪問序列：5,1,2。我們先看看持平的結(jié)果，os1=[1,2,5],os2=[4,5,1,2]，（此時(shí)os1、os2置換次數(shù)均為7次）這時(shí)候我們驚訝地發(fā)現(xiàn)了，5在os1的位置竟然先于os2！換句話說，只要把5從os2推出去，就可以故技重施。繼續(xù)訪問序列：6,7。os1=[5,6,7],os2=[1,2,6,7]，此時(shí)都置換了9次。這時(shí)候已經(jīng)滿足了Belady條件，我們直接訪問頁(yè)面5！os1=[5,6,7]，os2=[2,6,7,5]，這時(shí)候os1一共置換了9次，而os2置換了10次，Belady現(xiàn)象構(gòu)造成功?！靖剑和暾L問序列為：1,2,3,4,1,2,5,1,2,6,7,5】
? ? ? ? 核心的問題來了，為什么序列1,2,3,4,1,2,5就能成功構(gòu)建Belady現(xiàn)象，1,2,3,4,1,5則不可以？
? ? ? ? 這是因?yàn)椋诒纠衝=4,m=3,他們的長(zhǎng)度差為1。如果有辦法在打破穩(wěn)定狀態(tài)的時(shí)候，讓新增的那個(gè)頁(yè)面（本例中就是頁(yè)面5），可以在os2中前進(jìn)超過x次，而在os1中前進(jìn)y次，且x-y>n-m=1的時(shí)候，就能保證頁(yè)面5在os2中的次序先于os1了。而x的最大值則是從穩(wěn)定狀態(tài)開始，一直到os1與os2置換次數(shù)追平，所需要的置換次數(shù)。說得有點(diǎn)繞，本例中也就是從os1=[2,3,4],os2=[1,2,3,4]開始，下一步就將打破穩(wěn)定狀態(tài)，并且延續(xù)到了os1=[4,1,2],os2=[1,2,3,4]，再下一步os2開始了追平os1的路程。因此本例中采用的方式是令y=0,x=2。
? ? ? ? 總結(jié)起來，要構(gòu)建Belady現(xiàn)象，第一要?jiǎng)?wù)是能夠滿足兩個(gè)必要條件，而這兩個(gè)必要條件的又有兩個(gè)構(gòu)建準(zhǔn)則。從這個(gè)思想出發(fā)，我們來看看LRU算法是如何成功避免Belady現(xiàn)象的。
? ? ? ? 依然采用Belady現(xiàn)象訪問序列：1,2,3,4,1,2,5,1,2,6,7,5
? ? ? ? 先看訪問序列：1,2,3
? ? ? ? 此時(shí)os1=[1,2,3],os2=[1,2,3]。設(shè)此時(shí)狀態(tài)為A下一步能訪問的不外乎兩種情況：
????????1、1,2,3中訪問一頁(yè)，其結(jié)果分別為os1=[2,3,1],os2=[2,3,1];os1=[1,3,2],os2=[1,3,2];os1=[1,2,3],os2=[1,2,3]。我們可以發(fā)現(xiàn)，這種情況下os1與os2始終保持這穩(wěn)定區(qū)，且該情況等同于os1=[1,2,3],os2=[1,2,3]，因此這一步相當(dāng)于之后會(huì)遇到的訪問情境，與狀態(tài)A相同，只能考慮另外一種情況是否能打破穩(wěn)定狀態(tài)。
? ? ? ? 2、1,2,3之外訪問一頁(yè)，不妨設(shè)下一步訪問頁(yè)面4。此時(shí)os1=[2,3,4],os2=[1,2,3,4]，可以發(fā)現(xiàn)，os1與os2仍然具有穩(wěn)定區(qū)，但此時(shí)os1、os2并不完全相同。設(shè)此時(shí)狀態(tài)為B
????????繼續(xù)狀態(tài)B之后的情況，再下一步存在三種可能：
? ? ? ?1、在2、3、4中訪問，不妨假設(shè)訪問了頁(yè)面3，此時(shí)os1=[2,4,3],os2=[1,2,4,3]，仍然存在穩(wěn)定區(qū)，且此時(shí)狀態(tài)等同于狀態(tài)B，后續(xù)變化不必考慮。（頁(yè)面2、4也一樣）
? ? ? ? 2、訪問頁(yè)面1，此時(shí)os1=[3,4,1],os2=[2,3,4,1]。此時(shí)依然存在穩(wěn)定區(qū)，且與狀態(tài)B等同，亦不作后續(xù)考慮。
? ? ? ? 3、在頁(yè)面1、2、3、4之外訪問，不妨假設(shè)訪問頁(yè)面5，此時(shí)os1=[4,3,5],os2=[2,4,3,5]，此時(shí)狀態(tài)仍然與B等同。
????????因此狀態(tài)LRU算法在狀態(tài)A之后只可能變?yōu)闋顟B(tài)A或狀態(tài)B，在狀態(tài)B之后的算法將永遠(yuǎn)保持狀態(tài)B的穩(wěn)定狀態(tài)，且狀態(tài)A、B都是穩(wěn)定狀態(tài)，不可能發(fā)生Belady現(xiàn)象。
????????其余算法也都無(wú)法同時(shí)滿足兩個(gè)必要條件，或者兩個(gè)準(zhǔn)則，因此無(wú)法構(gòu)建Belady現(xiàn)象。當(dāng)然，我們也可以根據(jù)這兩個(gè)條件、兩個(gè)準(zhǔn)則，自己研究一個(gè)能夠?qū)崿F(xiàn)Belady現(xiàn)象的置換算法。
