Bélády’s anomaly

問題

仮想記憶のページの置換えアルゴリズムの一つであるFIFOの特徴のうち，適切なものはどれか。

• LRUアルゴリズムより置き換えるページを決定する処理に時間がかかる。
• LRUアルゴリズムよりもページフォールトの回数が少なくなる。
• ある種のページ参照列に対して，割当て主記憶量を増やすと，かえってページフォールトの回数が増加する。
• ページサイズを小さくすると，ページフォールトの回数が減る。

答え

ある種のページ参照列に対して，割当て主記憶量を増やすと，かえってページフォールトの回数が増加する。

解説

ページ置換アルゴリズム FIFO (First-In First-Out)

FIFOページ置換アルゴリズムはオーバヘッドの少ないアルゴリズムのひとつで、OS内でちょっとした記録をとる。名前からもわかるとおり、プロセスに割り当てたページを割り当てた順番にキューに載せる。ページ置換が必要になったとき、キューの先頭のページ（最も古いページ）を選択する。FIFO構造はコストがかからないし簡単なのだが、実際のアプリケーションにこのアルゴリズムを適用すると性能は悪くなる。そのため、そのままの形で使われることはない。このアルゴリズムではBéládyの例外（英語版）と呼ばれる状況が発生しうる。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

FIFO(First-In First-Out)は、置き換え対象の中で、最も古くから存在するページ（つまり、一番最初に入ったページ）を一番最初に追い出す「先入れ先出し」を行います。

Bélády’s anomaly

In computer storage, Bélády’s anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns. This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm. In FIFO, the page fault may or may not increase as the page frames increase, but in Optimal and stack-based algorithms like LRU, as the page frames increase the page fault decreases. László Bélády demonstrated this in 1969.^[1]

From Wikipedia, the free encyclopedia

以下意訳。

Bélády’s anomalyとは、ページフレームの数を増やすことで、逆に特定のメモリアクセスパターンでページフォールトの数が増えてしまう現象です。 この現象は、FIFOを用いたページ置換アルゴリズムを使用する場合に発生します。 FIFOでは、ページフレームが増加すると、ページフォールトが増加する場合としない場合があります。LRUなどの最適なスタックベースのアルゴリズムでは、ページフレームが増加するとページフォールトが必ず減少します。

ページフレームが3つの場合で考えます。

上の例の場合は、太字部分でページフォルトが発生しており、合計9回のページフォルトが発生します。

ページフレームを4つに増やし、上と同じようにページをリクエストします。

ページフレームを増やしたにも関わらず、合計10回のページフォルトが発生しています。