Belady's Anomaly は、FIFO ページ置換ポリシーを使用すると、ページ スペースを追加するとページ フォールトが増えると述べています。
私の直感では、ページ スペースを追加するのと同じ数のページ フォールトを減らすか、多くても同じ数にする必要があります。
FIFO キューをパイプと考えると、ページ スペースを追加することは、パイプを大きくすることに似ています。
____
O____O size 4
________
O________O size 8
では、なぜページ フォールトが増えるのでしょうか。私の直感では、パイプが長いと、ページ フォールトが発生し始めるまでに少し時間がかかります (したがって、無限のパイプを使用すると、ページ フォールトは発生しません)。多くの場合、より小さなパイプと同様です。
私の推論のどこが間違っていますか?
FIFO を使用する場合、ページ数を増やすと一部のアクセス パターンで障害率が高くなる可能性がある理由は、ページ数が増えると、最近要求されたページが FIFO キューの一番下に長く留まる可能性があるためです。
ここのウィキペディアの例で「3」が要求される 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 つのページ フォールトがあります。
2 番目の例 (より多くのページ) では、10 個のページ フォールトがあります。
FIFO を使用している場合、キャッシュのサイズを大きくすると、アイテムが削除される順序が変わります。場合によっては、障害率が高くなる可能性があります。
Belady's Anomaly は、キャッシュ サイズに関する障害率の一般的な傾向については何も述べていません。したがって、一般的なケースでは、(キャッシュをパイプとして表示することについて) あなたの推論は間違っていません。
要約すると、Belady's Anomaly は、キャッシュ サイズが大きいとキャッシュ内のアイテムがキャッシュ サイズが小さい場合よりも後で FIFO キューに入れられるという事実を悪用して、キャッシュ サイズが大きいほど障害が大きくなる可能性があると指摘しています。特定の（そしておそらくまれな）アクセスパターンの下でレート。
このステートメントは、過度に一般化されているため、間違っています。
Belady's Anomaly は、FIFO ページ置換ポリシーを使用する場合、ページ スペースを追加するとページ フォールトが増えると述べています。
これは修正版です:
「Belady's Anomaly は、FIFO ページ置換ポリシーを使用している場合、ページ スペースを追加すると、実際には一部のメモリ アクセス パターンでより多くのページ フォールトが発生すると述べています。」
つまり、異常が観察されるかどうかは、実際のメモリ アクセス パターンに依存します。
Belady の異常は、現在参照されているページがメイン メモリから最後に削除されたページである場合にのみ、FIFO 方式で発生します。この場合のみ、ページ スペースを増やしても、ページ フォールトが多くなります。