【ITニュース解説】Belady's Anomaly: FIFO vs LRU vs Optimal, Checked in Python

仮想記憶システムは、物理メモリ（RAM）の容量よりも大きなプログラムを実行可能にするための仕組みだ。プログラムは「ページ」という単位に分割され、必要に応じて物理メモリに読み込まれたり、ディスクに退避されたりする。このとき、物理メモリが満杯で新しいページを読み込むスペースがない場合に、どのページを物理メモリから追い出すかを決めるのが「ページ置き換えアルゴリズム」である。この選択がシステムの効率に大きく影響する。

プログラムがアクセスしようとしたページが物理メモリ上に存在しない場合、これを「ページフォルト」と呼ぶ。ページフォルトが発生すると、ディスクから目的のページを物理メモリに読み込む必要があり、これは比較的時間がかかる処理のため、システムの性能低下につながる。したがって、ページ置き換えアルゴリズムの主な目的は、ページフォルトの回数を最小限に抑えることだ。物理メモリは「フレーム」と呼ばれる固定サイズの区画に分割されており、各フレームに1つのページが格納される。参照文字列とは、プログラムが要求するページのアクセス順序を示す一連の数字列を指す。

ページ置き換えアルゴリズムには、いくつかの主要なものがある。一つ目は「FIFO（First-In, First-Out）」だ。これは最も古く、つまり最初に物理メモリに入ったページを追い出すという単純なルールに基づく。キュー（待ち行列）の原理と同じで、入ってきた順に処理され、一番長く待ったものから出ていく。実装が簡単という利点がある一方で、たとえ頻繁に使われるページであっても、単に古くからメモリに存在するという理由で追い出されてしまう可能性があり、効率が悪い場合がある。Pythonのコードではcollections.dequeというデータ構造を使って、ページがメモリに入った順序を管理している。

二つ目は「LRU（Least Recently Used）」だ。これは最も長い間使われていないページを追い出すというルールに従う。最近使われたページは今後も使われる可能性が高いという統計的な傾向に基づいたヒューリスティックなアルゴリズムで、FIFOよりも一般的に優れた性能を示すことが多い。しかし、各ページの最終アクセス時刻を記録し、常に最新の情報を維持する必要があるため、FIFOに比べて実装の複雑さや管理のためのオーバーヘッドが増加する。Pythonのコードではcollections.OrderedDict（順序付き辞書）を利用して、ページのアクセス順序を効率的に追跡し、アクセスがあったページを辞書の末尾に移動させることで、最も最近使われた状態を保っている。

三つ目は「Optimal（最適）」アルゴリズムだ。これは将来最も長い期間使われないページを追い出すという、理論上最も効率的なアルゴリズムだ。このアルゴリズムは、将来のページアクセスパターンを完全に予測できることを前提としており、現実のシステムでは不可能である。しかし、これ以上ページフォルトを減らすことはできないという、ページ置き換えアルゴリズムにおける性能の理論的な下限値を示すため、他のアルゴリズムの評価基準として非常に重要だ。Pythonのコードでは、参照文字列の残りの部分を「未来」として参照し、シミュレーションを行うことでOptimalの動作を再現している。

ニュース記事では、Pythonでこれらのアルゴリズムを実装し、具体的な参照文字列「1 2 3 4 1 2 5 1 2」とフレーム数3でシミュレーションした結果を示している。この例では、FIFOは7回のページフォルト、LRUも7回のページフォルト、そしてOptimalは5回のページフォルトを発生させている。Optimalが最も少ないページフォルト数となり、その理論的な優位性が確認できる。LRUが常にFIFOより優れているわけではなく、この特定の参照文字列では同じフォルト数になった。

ここで注目すべきは「ベルディの異常（Belady's Anomaly）」という現象だ。これは、物理メモリのフレーム数を増やせば、通常はより多くのページを保持できるため、ページフォルトの回数は減少すると期待されるにもかかわらず、FIFOアルゴリズムの場合に限り、フレーム数を増やすとかえってページフォルトが増加するという、直感に反する現象である。ニュース記事では、参照文字列「1 2 3 4 1 2 5 1 2 3 4 5」を用いてこの異常を具体的に示している。この参照文字列でフレーム数が3の場合、FIFOは9回のページフォルトを起こすが、フレーム数を4に増やしたところ、ページフォルトが10回に増加した。これはベルディの異常の典型的な例である。

なぜFIFOでベルディの異常が起こるのか。FIFOはページの入った順序のみを考慮し、実際の使用頻度を無視するため、フレーム数が増えることでページの入れ替わりが非効率なタイミングで起こり、結果的に多くのページフォルトを招く場合がある。一方、LRUやOptimalアルゴリズムではこの異常は発生しない。これらのアルゴリズムは「スタックプロパティ」という特性を持つためだ。スタックプロパティとは、フレーム数kでメモリ上に存在するページ集合が、フレーム数k+1でメモリ上に存在するページ集合の部分集合になる、という性質を指す。この性質により、フレーム数を増やせば必ず性能が向上するか、少なくとも悪化しないことが保証される。FIFOはこのスタックプロパティを持たないため、ベルディの異常が発生しうる。

ベルディの異常は非常に稀な現象であることが、ニュース記事の実験で明らかにされている。100万回のランダムな参照文字列に対するシミュレーションでは、FIFOでフレーム数を増やすとページフォルトが増加するケースは1回しか観測されなかった。さらに、可能なすべての参照文字列（12ページ、5種類のページ番号の全パターン、約2億4千万通り）を調べた結果、そのようなケースはわずか120回、約200万分の1の確率でしか発生しないことが判明した。このことから、教科書などでこの現象を紹介する際に用いられる参照文字列は、この稀なケースを意図的に示すために工夫されたものであると推測される。

これらのページ置き換えアルゴリズムとその特性の理解は、システムエンジニアを目指す上でメモリ管理の基礎を固める上で非常に重要だ。FIFOはシンプルだがベルディの異常を示しうる。LRUは一般的に優れた性能を持つが、管理コストはかかる。Optimalは理論上の最良値を提供するが、実用には適さない。Pythonコードを使って実際にシミュレーションを行うことで、これらの抽象的な概念をより深く、実践的に理解できる。特に、ベルディの異常のような直感に反する現象は、アルゴリズムの動作原理を深く考察する良い機会となるだろう。