Belady の例外(Belady's anomaly)

　まず最初に断っておきます。「そんなことも知らなかったのか」という突っ込みは無し。では、始めましょう。

　情報源である『OS の基礎と応用』の中では、メモリページング問題の一環として出てきていますが、実際にはレジスタマッピング、キャッシュマッピングを始めとするいろいろな世界で出てくる話です。

Belady の例外とは

　あるプログラムがあります。このプログラムは全部で5Kbyte のメモリを消費します。が、あなたの計算機には3Kbyte 分しかありません。でもあなたが使っているOSは、 1Kbyte を 1 page とする仮想メモリが実装されています。このためあなたのプログラムは動くことができます。が、時々ページフォルトを起こすのでちょっと遅いです。

　あなたはプログラムがどのようにメモリを触っているかを調べました。すると 5page を順に 0,1,2,3,4 と名付けた時に、アクセス順序は

0 1 2 3 0 1 4 0 1 2 3 4

となっていることがわかりました。

　また、あなたの OS は FIFO でpaging space を管理していることもわかりました。つまり、今メモリ上にないページをアクセスする必要が出た場合、一番昔にメモリ上に載せたページを swap out することにしていたのです。

　このことから、あなたの計算機はメモリ上に次のようにページを保持していることがわかりました。

アクセス順序	0	1	2	3	0	1	4	0	1	2	3	4
最新のページ	0	1	2	3	0	1	4	4	4	2	3	3
:		0	1	2	3	0	1	1	1	4	2	2
最古のページ			0	1	2	3	0	0	0	1	4	4
Page Fault	Ｐ	Ｐ	Ｐ	Ｐ	Ｐ	Ｐ	Ｐ			Ｐ	Ｐ

「９回がページフォルトか…ま、こんなもんかな」
あなたはそう思っていました。

　ある日、あなたは道端に 1kbyte のメモリが落ちているのを発見しました。
「らっきー。これを入れれば早くなるな」
あなたは早速そのメモリを計算機に挿してみました。

　ところか…落しものを素直に届けなかった罰なのでしょうか？全然計算が早くありません。いや、むしろ遅くなったような感じさえします。あなたは慌ててメモリのアクセス状態を調べました。

アクセス順序	0	1	2	3	0	1	4	0	1	2	3	4
最新のページ	0	1	2	3	3	3	4	0	1	2	3	4
:		0	1	2	2	2	3	4	0	1	2	3
:			0	1	1	1	2	3	4	0	1	2
最古のページ				0	0	0	1	2	3	4	0	1
Page Fault	Ｐ	Ｐ	Ｐ	Ｐ			Ｐ	Ｐ	Ｐ	Ｐ	Ｐ	Ｐ

　なんと！メモリが増えたせいで、ページフォルトの回数が増えています。この方法だと 10回になっています。

　このように、リソースを増やすと効率が落ちてしまう。これが『Belady の例外』と言われる現象です。

現象の本質と解決策

　この現象が生じる理由は基本だけであれば簡単で、 FIFO戦略を選んだ所に原因があります。

　上のメモリに存在するページの履歴を見てみると、３ページしかない時と４ページある時ではその動きが全く違います。これはFIFO戦略がメモリページ数依存で動作を替えるためです。

　仮に、４ページ分メモリがある方のメモリページの新しい方３ページ分の履歴が、３ページ分しかメモリがない場合と一緒であるようなアルゴリズムを選んだとします。例えば LRU（Least Recently Used：最長不使用）と言われる戦略を選んだ場合:

LRU 3kbyte
アクセス順序	0	1	2	3	0	1	4	0	1	2	3	4
最新のページ	0	1	2	3	0	1	4	0	1	2	3	4
:		0	1	2	3	0	1	4	0	1	2	3
最古のページ			0	1	2	3	0	1	4	0	1	2
Page Fault	Ｐ	Ｐ	Ｐ	Ｐ	Ｐ	Ｐ	Ｐ			Ｐ	Ｐ	Ｐ

LRU 4kbyte
アクセス順序	0	1	2	3	0	1	4	0	1	2	3	4
最新のページ	0	1	2	3	0	1	4	0	1	2	3	4
:		0	1	2	3	0	1	4	0	1	2	3
:			0	1	2	3	0	1	4	0	1	2
最古のページ				0	1	2	3	3	3	4	0	1
Page Fault	Ｐ	Ｐ	Ｐ	Ｐ			Ｐ			Ｐ	Ｐ	Ｐ

　この戦略では４ページ分のメモリがある場合の、新しい方３つ分のマップは、３ページしかない場合のマップと完全に一致します。この性質があるような戦略の場合、４ページでページフォルトが起きるなら３ページのほうでも必ずページフォルトが生じます。一方３ページだと起きるが、４ページだと起きない場合はあり得ます。

　この LRU の様に、n ページ分のメモリがあるときの動作が、 n+1ページある時の動作と一致する部分が存在するようなアルゴリズムのことをスタックアルゴリズムと言います。この、スタックアルゴリズムの場合はページ数が増えた場合に、ページフォルトの回数が増えてしまうなどということは起きません。

　たしかに n ページよりも n+1 ページメモリがある方がページフォルトの回数が少ないのは事実なのですが、ここには重大な問題があります。

　3kbyte しかメモリがない場合に、 FIFO ならば 9回のページフォルトしか起きないのに、 LRU だと 10回のページフォルトが起きるのです。

どういう時に気をつければいいのか

　Belady の例外は、特定のリソースサイズだけに特化したシステムをデザインする場合、
「その場合の最適解」
は
「リソースの増減を考慮して、リソース量に応じた応答性能を出すための解」
よりも最適な場合が多いが、ほんの少しリソース量を変化させただけでパフォーマンスは大幅に落ちてしまうことも多いということを意味しています。

　このような、性能のピーキーさから来る問題はリソース量がぎりぎりな世界、たとえば PDA 用のソフトを開発するときに特に注意が必要です。

　PDA は値段や大きさの理由から、特に初期のバージョンにリソースの少ないものが多いのですが、一方で、パフォーマンスは可能な限り高い必要があります。このため、OS などの根幹部に「その場合の最適解」をついつい選んでしまいがちです。ところが、そのパフォーマンスゆえに売れ出すと、より多くのリソースを持つバージョンが生産的に妥当なモデルとなってきます。こうなると、それまでパフォーマンスを得るために最適だったデザインは、ただの禍根に早変わりしてしまいます。

　自分が本当に目的としているのは何なのか丁寧に考える必要があることを、 Belady の例外は示してくれています。