「応用情報技術者試験/平成31年春季午前問19」LRU方式のページ参照問題

問題

出典:応用情報技術者平成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
エ:7000

用語解説

LRU方式を知っていればただ地道に手を動かす問題である。

LRU方式

LRU方式とは、最後に参照されてからの時間が最も長い物を置換え対象にするアルゴリズムである。

解説

初期状態を以下とする。
4000番地:1(最後に参照されてからの時間:3)
5000番地:2(最後に参照されてからの時間:2)
6000番地:3(最後に参照されてからの時間:1)
7000番地:4(最後に参照されてからの時間:0)

次の値「2」
4000番地:1(最後に参照されてからの時間:4)
5000番地:2(最後に参照されてからの時間:0)
6000番地:3(最後に参照されてからの時間:2)
7000番地:4(最後に参照されてからの時間:1)

次の値「5」
4000番地:5(最後に参照されてからの時間:0)
5000番地:2(最後に参照されてからの時間:1)
6000番地:3(最後に参照されてからの時間:3)
7000番地:4(最後に参照されてからの時間:2)

次の値「3」
4000番地:5(最後に参照されてからの時間:1)
5000番地:2(最後に参照されてからの時間:2)
6000番地:3(最後に参照されてからの時間:0)
7000番地:4(最後に参照されてからの時間:3)

次の値「1」
4000番地:5(最後に参照されてからの時間:2)
5000番地:2(最後に参照されてからの時間:3)
6000番地:3(最後に参照されてからの時間:1)
7000番地:1(最後に参照されてからの時間:0)

次の値「6」
4000番地:5(最後に参照されてからの時間:3)
5000番地:6(最後に参照されてからの時間:0)
6000番地:3(最後に参照されてからの時間:2)
7000番地:1(最後に参照されてからの時間:1)

次の値「5」
4000番地:5(最後に参照されてからの時間:0)
5000番地:6(最後に参照されてからの時間:1)
6000番地:3(最後に参照されてからの時間:3)
7000番地:1(最後に参照されてからの時間:2)

次の値「4」
4000番地:5(最後に参照されてからの時間:1)
5000番地:6(最後に参照されてからの時間:2)
6000番地:4(最後に参照されてからの時間:0)
7000番地:1(最後に参照されてからの時間:3)

という事で、答えは6000番地のウ

解答

正解:ウ

アドセンス
改行

テックキャンプ