平成31年度 春期 応用情報技術者試験 午前 問19
テクノロジ／ソフトウェア仮想記憶管理におけるページ置換えアルゴリズムとして 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番地にページインされるものとする。
出典：平成31年度 春期 応用情報技術者試験 午前 問19
- ア4000
- イ5000
- ウ6000
- エ7000
正解：ウ
解説
LRU 方式は最も長く参照されていないページを置き換えます。最初の 1→2→3→4 で 4000:1，5000:2，6000:3，7000:4 となります。続く2はヒット，5は最も古い1を追い出して4000番地へ，3はヒット，1は最も古い4を追い出して7000番地へ，6は最も古い2を追い出して5000番地へ入り，5はヒットします。この時点で各ページ枠の内容は 4000:5，5000:6，6000:3，7000:1 で，最後に参照されてから最も時間が経っているのは6000番地の3なので，ページ4は6000番地にページインされます。
選択肢ごとの解説
- ア誤り。4000番地には直前に参照されたばかりの5が入っており，最も新しく使われたページなので置換対象になりません。
- イ誤り。5000番地のページは6の参照時に置き換えられており，その6は6000番地の3より後に参照されています。
- ウ正しい。最後の4の参照時点で最も長く参照されていないのは6000番地の3なので，ここが置き換えられます。
- エ誤り。7000番地は1の参照時に置き換えられており，その1は3より後に参照されているため置換対象になりません。