LRU 方式でのページ置換え
出典: 令和7年度 春期 応用情報技術者試験 午前 問15 (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 番地にはページ 2 が、後でページ 6 が入ります。ページ 4 は入りません。
- ウ: 最後に参照されたページ 4 は、最も長く使われていないページ 3 の 6000 番地に入ります。正しい答えです。
- エ: 7000 番地にはもともとページ 4 が入りましたが、途中でページ 1 に置き換わっています。
ポイント
LRU は、最後に参照されてから最も時間がたったページを追い出します。
| 参照 | 動作 | 4000 | 5000 | 6000 | 7000 |
|---|---|---|---|---|---|
| 1,2,3,4 | 初期配置 | 1 | 2 | 3 | 4 |
| 2 | 既にある | 1 | 2 | 3 | 4 |
| 5 | 最も古い 1 を追い出す | 5 | 2 | 3 | 4 |
| 3 | 既にある | 5 | 2 | 3 | 4 |
| 1 | 最も古い 4 を追い出す | 5 | 2 | 3 | 1 |
| 6 | 最も古い 2 を追い出す | 5 | 6 | 3 | 1 |
| 5 | 既にある | 5 | 6 | 3 | 1 |
| 4 | 最も古い 3 を追い出す | 5 | 6 | 4 | 1 |
最後のページ 4 は 6000 番地 です。