ページ置換アルゴリズム（LRU・FIFO）とは？

ページ置換アルゴリズム（LRU・FIFO）の意味

主記憶に空きページ枠が無いとき、どのページを追い出すかを決める規則。LRUは最後に参照された時刻が最も古いページを、FIFOは最も早く読み込まれたページを、LFUは参照回数が最も少ないページを追い出す。実際のOSは実装コストを抑えたLRU近似（参照ビットを用いるクロック方式）を使うことが多い。応用情報では参照列を与えられ、方式ごとのページフォールト回数を数える問題が定番。

ページ置換アルゴリズム（LRU・FIFO）の具体例

枠が3で参照列が1,2,3,1,4のとき、4を入れる場面でFIFOは最初に入った1を追い出すが、LRUは直前に1が参照されているため2を追い出す。この差がそのまま実行時間に効くため、DBのバッファプールは多くがLRU系を採用する。

ページ置換アルゴリズム（LRU・FIFO）は試験でどう引っ掛けられる？

FIFOは枠を増やすとかえってページフォールトが増える「ベラディの異常」が起こり得る。LRUやLFUでは起きない。「枠を増やせば必ず速くなる」と決めつけると誤る。

ページ置換アルゴリズム（LRU・FIFO）と関連する用語

• デマンドページングとページフォールト
• ワーキングセットモデル
• スラッシング
• セグメント方式と動的アドレス変換

ページ置換アルゴリズム（LRU・FIFO）が出た過去問

• 仮想記憶方式に関する記述のうち，適切なものはどれか。

  正解：LRUアルゴリズムは，使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。

  要点：LRUは最長未使用ページを置換する。局所性が前提

  LRU（Least Recently Used）は最後に参照されてから最も時間が経ったページ、すなわち最長未使用のページを追い出すアルゴリズムである。参照の局所性から、直近に使われていないページは今後も使われにくいという前提に立つ。ページ置換方式としてFIFOより一般にヒット率が高い。

  出典：平成28年度 春期 高度共通_午前I試験 am1 問6（IPA）

• 4ブロックのキャッシュメモリC0〜C3が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2のブロックを置換…

  正解：LRU

  要点：LRUは最終参照が最古、FIFOはロードが最古を追い出す

  C2は最終参照時刻が0:05で4つの中で最も古く、最後に使われてから最も長く放置されている。最長未使用のブロックを追い出すのはLRUである。FIFOならロード時刻が最も古いC0、LIFOなら最も新しいC3、LFUなら参照回数が最少のC1が対象になる。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問6（IPA）

• 4ブロックのキャッシュメモリC0〜C3が表に示す状態である。ここで、新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき、C2のブロックを置換…

  正解：LRU

  要点：LRUは最終参照時刻が最も古いブロックを置き換える

  LRU（Least Recently Used）は最終参照時刻が最も古いブロックを追い出す方式である。表の最終参照時刻はC0が0:08、C1が0:06、C2が0:05、C3が0:10なので、最も古いC2が置換対象になる。

  出典：令和7年度 秋期 高度共通_午前I試験 am1 問6（IPA）

• 仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。主記憶のページ枠が、4000, 5000, 6000, 7000番地（いずれも16進数）…

  正解：6000

  要点：LRUは最後に参照してから最も時間が経ったページを追い出す

  LRUは最後に参照されてから最も時間が経ったページを追い出す。初期状態は4000＝1、5000＝2、6000＝3、7000＝4である。5の参照で最も古い1（4000番地）が置き換わり、次の1の参照で4（7000番地）が、6の参照で2（5000番地）が置き換わる。最後の4の参照時に最も古いのは3（6000番地）なので、ページ4は6000番地にページインされる。

  出典：令和7年度 春期 高度共通_午前I試験 am1 問6（IPA）