LRU 方式のページ置換え
出典: 平成31年度 春期 応用情報技術者試験 午前 問19 (IPA)
仮想記憶管理におけるページ置換えアルゴリズムとして LRU 方式を採用する。主記憶のページ枠が，4000，5000，6000，7000 番地（いずれも 16 進数）の 4 ページ分で，プログラムが参照するページ番号の順が，1→2→3→4→2→5→3→1→6→5→4 のとき，最後の参照ページ 4 は何番地にページインされているか。ここで，最初の 1→2→3→4 の参照で，それぞれのページは 4000，5000，6000，7000 番地にページインされるものとする。
- ア 4000
- イ 5000
- ウ 6000
- エ 7000
正解と解説を見る
正解: ウ
- ア: 4000 番地には途中でページ 5 が入り、その後も参照されているので追い出されません。
- イ: 5000 番地にはページ 6 が入っており、直前に参照されたばかりです。
- ウ: 最後の参照時点で最も長く参照されていないのは 6000 番地のページ 3 なので、ここにページ 4 が入ります。正しい答えです。
- エ: 7000 番地には途中でページ 1 が入っており、ページ 3 より後に参照されています。
ポイント
LRU は、最後に参照されてから最も長い時間がたったページ を追い出します。
- 1→2→3→4: 4000=1、5000=2、6000=3、7000=4。
- 2: ヒット。5: 最も古いのは 1 → 4000=5。3: ヒット。
- 1: 最終参照が最も古いのは 4 → 7000=1。
- 6: 最も古いのは 2 → 5000=6。5: ヒット。
- 4: 最も古いのは 3 (最終参照は 7 番目) → 6000=4。
よって最後の 4 は 6000 番地 にページインされます。