clock算法中的Belady現象

clock算法是有belady現象的。

belady現象是指局部置換算法中，發現某程序缺頁率變高，于是作業系統給它又分了幾個實體頁，原以為缺頁率的增高是由于工作集變大，實體頁幀不夠用，結果增加了實體頁以後，缺頁率不降反而升高。

belady現象的出現，是由于置換算法将需要經常通路的頁面置換了出去導緻的。例如FIFO算法，即便最開始進入記憶體的那個頁面是最近以及未來要經常通路的，但是FIFO還是選擇把它換出去。

FIFO選擇替換最早進入記憶體的頁面，沒有考慮到這個頁面未來是否可能會經常通路，是以導緻了belady現象。

類似的算法還有clock算法，clock算法本質跟FIFO一樣，假如實體頁幀數為4，并頁面p1、p2、p3、p4先後被通路并被載入實體頁幀，從p4被載入記憶體的時刻t1開始，直到下一次發生缺頁的時刻t2為止這段時間内最經常通路的頁是p1，根據局部性原理，未來p1有很大可能要繼續通路。但是clock算法給這四個頁面都設定了通路位，而且很遺憾的是，這個通路位隻有一個比特，它根本區分不了這個四個頁面中誰被通路最頻繁，這4個頁面的通路位都是1，根據clock算法，t2時候發生缺頁，clock算法按照被載入記憶體的時間先後掃描所有頁幀，将第一個通路位為0的頁面置換出去，但是顯然這四個頁面的通路位都是1，是以clock算法會将這4個頁面的通路位依次置為0，然後循環掃描，将p1置換出去。是以clock算法是存在belady現象的。

clock算法的提出就是因為覺得LRU為了維持對通路局部性（誰是最近第一個被通路的、誰是最近第2個被通路的、...）的感覺，開銷太大，LRU需要經常修改頁面連結清單，確定是按照最近通路時間排序。FIFO不需要費這種功夫，是以開銷比較小，但是缺點是FIFO感覺不了通路局部性。

clock算法是LRU和FIFO的折中，但是還是偏向于FIFO，它不像LRU那樣能夠區分頁面的通路時間的先後順序，它隻能夠區分有沒有被通路過，至于在那些都被通路過的頁面中，誰是最頻繁被通路的、誰是最近被通路的，clock算法區分不了。是以導緻它經過一輪掃描以後退化成為FIFO。