問15 LRU 方式のページ置換え

応用情報​技術者試験 令和7年度 春期 午前、全80問のうちの問15。

出典:令和7年度 春期 応用情報技術者試験 午前 問15

仮想記憶管理におけるページ置換えアルゴリズムとして LRU 方式を採用する。主記憶のページ枠が,4⁠0⁠0⁠0,5⁠0⁠0⁠0,6⁠0⁠0⁠0,7⁠0⁠0⁠0 番地(いずれも 1⁠6 進数)の 4 ページ分で,プログラムが参照するページ番号の順が,1 → 2 → 3 → 4 → 2 → 5 → 3 → 1 → 6 → 5 → 4 のとき,最後の参照ページ 4 は何番地にページインされているか。ここで,最初の 1 → 2 → 3 → 4 の参照で,それぞれのページは 4⁠0⁠0⁠0,5⁠0⁠0⁠0,6⁠0⁠0⁠0,7⁠0⁠0⁠0 番地にページインされるものとする。

  1. ア4⁠0⁠0⁠0
  2. イ5⁠0⁠0⁠0
  3. ウ6⁠0⁠0⁠0
  4. エ7⁠0⁠0⁠0
答えと解説を開く

正解はウです。

LRU 方式は、ページ枠が足りないとき、最後に参照されてから最も時間がたったページを追い出します。参照を順に追います。1〜4 番目で、4⁠0⁠0⁠0 に 1、5⁠0⁠0⁠0 に 2、6⁠0⁠0⁠0 に 3、7⁠0⁠0⁠0 に 4 が入ります。5 番目の 2 は主記憶にあるので置換えはありません。6 番目の 5 では、最後の参照が最も古い 1 (1 番目) を追い出し、4⁠0⁠0⁠0 に 5 が入ります。7 番目の 3 はあります。8 番目の 1 では、最も古い 4 (4 番目) を追い出し、7⁠0⁠0⁠0 に 1 が入ります。9 番目の 6 では、最も古い 2 (5 番目) を追い出し、5⁠0⁠0⁠0 に 6 が入ります。1⁠0 番目の 5 はあります。1⁠1 番目の 4 では、残る 5 (1⁠0 番目)、6 (9 番目)、3 (7 番目)、1 (8 番目) のうち最も古い 3 を追い出し、6⁠0⁠0⁠0 に 4 が入ります。正解はウです。

ほかの選択肢が違う理由

  • ア4⁠0⁠0⁠0 には 6 番目でページ 5 が入り、1⁠0 番目でも参照されています。最後の時点では最も新しく使われたページなので、追い出されません。
  • イ5⁠0⁠0⁠0 には 9 番目でページ 6 が入っています。3 (7 番目) より後に使われているので、追い出す候補になりません。
  • エ7⁠0⁠0⁠0 は最初にページ 4 が入った場所ですが、4 は 8 番目の参照でページ 1 に追い出されています。最初に入った物を先に出す FIFO 方式で考えると、4 が残って 7⁠0⁠0⁠0 のままになります。

仕組み

仮想記憶では、プログラムの全部を主記憶に置かず、使う部分 (ページ) だけを主記憶に読み込みます。主記憶にないページを参照すると、補助記憶から読み込むページインが起きます。

LRU は「しばらく使っていない物は、この先も使わないだろう」と考える方式です。入った順で追い出す FIFO より、実際の使われ方に合いやすいとされます。

この問に出る言葉