2019年(平成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番地にページ因されるものとする。

　ア 　4000
　イ 　5000
　ウ 　6000
　エ 　700

答え　ウ

【解説】
1→2→3→4の参照でページ枠の状態は(( )内の数字は最後にアクセスした古い順番です。)

4000 5000 6000 7000
1(1) 2(2) 3(3) 4(4)
次の2はページにあるので置き換えは発生せず、その次の5は最後にアクセスしてから最も時間の経っている1と置き換え
4000 5000 6000 7000
5(4) 2(3) 3(1) 4(2)
その後の3はページにあるので入れ替えは発生せず、その次の1は最後にアクセスしてから最も時間の経っている4と置き換え
4000 5000 6000 7000
5(2) 2(1) 3(3) 1(4)
その次の6は最後にアクセスしてから最も時間の経っている2と置き換え
4000 5000 6000 7000
5(1) 6(4) 3(2) 1(3)
その後の5はページにあるので入れ替えは発生せず、その次の4は最後にアクセスしてから最も時間の経っている3と置き換え
4000 5000 6000 7000
5(3) 6(2) 4(4) 1(1)
になる。

【キーワード】
・ページ置換えアルゴリズム

【キーワードの解説】

戻る 一覧へ 次へ