ITパスポート試験 ITパスポート 2016年 (平成28年 春期) 問82: ファイルを4冊まで置くことができる机で,A〜Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいときは,机上の4冊のファイルのうち,最後に参照

問題本文

ファイルを4冊まで置くことができる机で,A〜Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいときは,机上の4冊のファイルのうち,最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。ファイルをA,B,C,D,E,C,B,D,F,Bの順で机上に置いて参照するとき,最後に引き出しにしまうファイルはどれか。

選択肢

• ア.A
• イ.B
• ウ.D
• エ.E

正解

エ. E

解説

机に4冊までで,5冊目を置きたいときは最後に参照してから最も時間が経った1冊を引き出しにしまうのは,主記憶のページ置換アルゴリズムのLRU(Least Recently Used)方式と同じ動作である. 参照順A,B,C,D,E,C,B,D,F,Bに沿ってシミュレートする. A,B,C,Dで机上は{A,B,C,D}. E参照時に5冊目になり最古参照のA(時刻1)を引き出しへ→{B,C,D,E}. C,B,D参照で時刻更新→{E,C,B,D}(参照時刻順). F参照時に最古はE(時刻5)で引き出しへ→{C,B,D,F}. 最後にB参照,机上のまま. 引き出しに入れた順はA→Eなので,最後に引き出しにしまうのはEとなる.

選択肢ごとの解説

• ア.誤り. Aは机上が4冊になった後で5冊目のEを置く際に,その時点で最も参照時刻が古いとして最初に引き出しにしまわれるファイルである. その後さらにC,B,D,Fと参照を続ける中で別のファイルも引き出しに移されるため,本問の「最後にしまうファイル」としては不適切である.
• イ.誤り. Bは参照順A,B,C,D,E,C,B,D,F,Bの中で何度も参照されており,最後の参照(時刻10)が直近である. LRU方式では最も最近参照されたファイルが机上に残り続けるため,引き出しにしまわれる対象とはならない. したがって本問の「最後にしまうファイル」としては適切ではない.
• ウ.誤り. Dは時刻4と時刻8でそれぞれ参照されているため,Fが置かれる時刻9の時点でも参照時刻は比較的新しく,最も古い参照とはならない. F参照時に引き出しへ移されるのはE(時刻5)であるため,Dは引き出しへ移されず机上に残るので,本問の答えにはならない.
• エ.正しい. シミュレーションするとEは時刻5に置かれ,その後参照されないままFの追加時(時刻9)に最も古い参照として引き出しへ移される. Aは時刻5にすでに移されているため,引き出しに移される順はA→Eとなる. したがって,最後に引き出しにしまうファイルはEとなり本選択肢が正解となる.