2011-01-26 25 views
28

因此,Belady的Anomaly指出,當使用FIFO頁面替換策略時,當添加更多頁面空間時,我們會出現更多頁面錯誤。無法理解Belady的異常

我的直覺說,我們應該減少或至多減少頁面錯誤的數量,因爲我們增加了更多的頁面空間。

如果我們認爲一個FIFO隊列作爲管道,增加更多的頁面空間是像製作管道更大:

____ 
O____O size 4 

________ 
O________O size 8 

那麼,爲什麼你會得到更多的頁面錯誤?我的直覺說,用更長的管道,你會花更長的時間來開始頁面錯誤(所以,無限的管道,你沒有頁面錯誤),然後你會有同樣多的頁面錯誤,就像通常與較小的管道一樣。

我的推理出了什麼問題?

+1

不確定你在找什麼 - 這個WP頁面有一個實際的例子:http://en.wikipedia.org/wiki/Belady's_anomaly – Ken 2011-01-26 00:20:59

+4

你讀過[Wikipedia article](http: //en.wikipedia.org/wiki/Belady's_anomaly)?這被稱爲異常,因爲它違背了大多數人的直覺。 :) – 2011-01-26 00:22:00

+4

在這種特殊情況下,擁有更多頁面框架會導致算法將頁面保留更長時間,以至於稍後使用頻率較低,並且它們不會從FIFO中快速退出,以便爲實際結束的頁面釋放空間需要。但我不知道你可以從中得到一個普遍的直覺。這就是可能發生的事情。 – Ken 2011-01-26 00:24:27

回答

28

當使用FIFO時,增加頁面數可能會增加某些訪問模式下的錯誤率,這是因爲當您有更多頁面時,最近請求的頁面可能會更長時間保留在FIFO隊列的底部。

考慮到「3」的請求在這裏例如維基百科第三次: http://en.wikipedia.org/wiki/Belady%27s_anomaly

頁面錯誤都標有一個「F」。

1:

Page Requests 3 2 1 0 3 2 4 3 2 1 0 4 
Newest Page  3f 2f 1f 0f 3f 2f 4f 4 4 1f 0f 0 
        3 2 1 0 3 2 2 2 4 1 1 
Oldest Page    3 2 1 0 3 3 3 2 4 4 

2:

Page Requests 3 2 1 0 3 2 4 3 2 1 0 4 
Newest Page  3f 2f 1f 0f 0 0 4f 3f 2f 1f 0f 4f 
        3 2 1 1 1 0 4 3 2 1 0 
          3 2 2 2 1 0 4 3 2 1 
Oldest Page     3 3 3 2 1 0 4 3 2 

在第一個例子(用更少的頁),有9個錯誤。

在第二個示例(包含更多頁面)中,有10個頁面錯誤。

使用FIFO時,增加緩存的大小會改變項目的刪除順序。其中有些的情況下,可以增加故障率。

Belady's Anomaly沒有說明有關緩存大小的錯誤率的總體趨勢。因此,您的推理(關於將緩存視爲管道)在一般情況下並不是錯誤的。

總結: Belady's Anomaly指出,有可能利用這樣一個事實,即較大的高速緩存大小會導致高速緩存中的項目在FIFO隊列中比較小的高速緩存大小更晚,以便導致更大的高速緩存大小在特定的(可能是罕見的)訪問模式下具有更高的故障率。

-2

只有當前被引用的頁面是最後從主存儲器中刪除的頁面時,Belady的異常纔會發生在FIFO方案中。只有在這種情況下,即使您增加了更多的頁面空間,您也會遇到更多頁面錯誤。

6

這種說法是錯誤的,因爲它是泛化的檢討

Belady的異常指出,使用FIFO頁面替換策略時,加入更多的頁面空間的時候,我們將有更多的頁面錯誤

這是一個正確的版本:

「Belady's Anomaly說,當使用FIFO頁面替換策略時,添加更多頁面空間時,一些內存訪問模式實際上會導致更多的頁面錯誤。「

換句話說...觀察異常是否取決於實際的內存訪問模式。

1

Belady的異常發生在頁面替換算法中不遵循堆棧算法。也就是說,當頁面較少時頁面應該是頁面的一個子集,當頁面更多時。在增加頁面框架時,之前存在的頁面框架必須在那裏。這可能發生在FIFO有時甚至是隨機頁面替換,但不是LRU或最優。