B%C3%A9l%C3%A1dy’s_anomaly
でコンピュータストレージ、Béládyの異常は、数の増加にページ・フレームの結果の数を増加させる現象であるページフォルト特定のメモリアクセスパターンのために。この現象は、先入れ先出し（FIFO）ページ置換アルゴリズムを使用する場合によく発生します。FIFOでは、ページフォールトはページフレームが増加するにつれて増加する場合と増加しない場合がありますが、LRUのような最適なスタックベースのアルゴリズムでは、ページフレームが増加するとページフォールトが減少します。LászlóBéládyは1969年にこれを実証しました。
時間
{{ ce {-> [{} atop { text {Time}}]}}}
ページリクエスト3 2 1 0 3 2 4 3 2 30 31 32
最新のページ3 2 1 0 3 2 4 4 4 30 31 32
3 2 1 0 3 2 2 2 4 30 31
最も古いページ
3 2 1 0 3 3 3 2 4 30
時間
{{ ce {-> [{} atop { text {Time}}]}}}
ページリクエスト3 2 1 0 3 2 4 3 2 30 31 32
最新のページ3 2 1 0 0 0 4 3 2 30 31 32
3 2 1 1 1 0 4 3 2 30 31
3 2 2 2 1 0 4 3 2 30
最も古いページ
3 3 3 2 1 0 4 3 2
ベラディの異常の例。3ページフレームを使用すると、9ページフォールトが発生します。4ページフレームに増やすと、10ページフォールトが発生します。ページフォールトは赤で表示されます。これは、「ペニーワイズ、ポンド愚か者」の行動の結果として考えることができます。
一般的なコンピュータのメモリ管理では、情報は特定のサイズのチャンクでロードされます。各チャンクはページと呼ばれます。メインメモリは、一度に限られた数のページしか保持できません。ロードできるページごとにフレームが必要です。ページフォールトは、ページが見つからない場合に発生し、ディスクからメモリにロードする必要があるかもしれません。
ページフォールトが発生し、すべてのフレームが使用されている場合は、新しいページ用のスペースを確保するために1つをクリアする必要が単純なアルゴリズムはFIFOです。フレーム内にあるページが最も長いものがクリアされます。ベラディの異常が実証されるまで、ページフレームの数を増やすと、常に同じ数以下のページフォールトが発生すると考えられていました。
ベラディの異常には限りがありません
ベラディ、ネルソン、シェドラーは、FIFOページ置換アルゴリズムが小さいメモリよりも大きいメモリでほぼ2倍のページフォールトを生成する参照文字列を作成し、2が一般的な境界であるという推測を定式化しました。
2010年、FornaiとIványiは、異常が実際には無制限であり、任意のページフォールト比率への参照文字列を作成できることを示しました。
参考文献
^ クリストファークルーゲル「オペレーティングシステム（CS170-08コース）」 （PDF）。cs.UCSB.edu。2016年8月10日にオリジナル （PDF）からアーカイブされました。
外部リンク
ベラディの1969年の論文：ページングマシンで実行されている特定のプログラムの時空間特性の異常
FIFOの異常には制限がありません。arXiv：1003.1336
インターネット問題解決コンテストソリューション–問題L –司書