ITパスポート|アルゴリズムとプログラミング 問9
ファイルを 4 冊だけ置くことができる机で、A~F の 6 冊のファイルを使って仕事をする。机上に 5 冊目のファイルを置きたいとき、机上の 4 冊のファイルのうち、最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。ファイルが A、B、C、D、B、A、E、A、B、F の順で必要になった場合、最後に引き出しにしまうファイルはどれか。
正解:ウ
解説
最後に使ってから最も時間がたったものを追い出す LRU 方式(Least Recently Used)です。順に机の上の状態を追います。
- A,B,C,D
- 机の上は A、B、C、D で満杯
- B,A
- すでに机の上にある
- E
- 最後の参照が最も古いのは C なので、C をしまう → A、B、D、E
- A,B
- すでに机の上にある
- F
- 最後の参照が古い順に D、E、A、B なので、D をしまう
- ウ 正解。
もう一歩深く
A、B、C、D で机がいっぱいになり、B と A を参照すると、最後に参照してから時間がたった順は C、D、B、A になります。E を置くとき、最も前に参照した C をしまい、机は D、B、A、E になります。A、B を参照した後、F を置くときは、机の上で最も前に参照したのは D なので、D をしまいます。この考え方は、主記憶のページの置換えなどで使われる LRU 方式と同じです。
出典:平成21年度春期 ITパスポート試験 公開問題 問85(読点「,」を「、」に改変)