問85
頻出度★☆☆
ファイルを4冊だけ置くことができる机で，A～Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいとき，机上の4冊のファイルのうち，最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。 ファイルがA，B，C，D，B，A，E，A，B，Fの順で必要になった場合，最後に引き出しにしまうファイルはどれか。
平成21年度 春期 ITパスポート試験 問85
テクノロジ系ソフトウェア › オペレーティングシステム
この問題の解説と、これまでの解答の記録です。
解説
問 85
不正解ア
A は6回目と8回目に再び参照されるため、退避判定が行われる7回目・10回目のどちらの時点でも最終参照時刻が新しく、追い出されません。A はこの参照列の間、一度も引き出しにしまわれないファイルです。
不正解イ
B は5回目と9回目に再び参照されるため、7回目の時点では C・D より新しく、10回目の時点では最も新しく参照されたファイルです。B はこの参照列の間、一度も引き出しにしまわれません。
- ウ
正解 この机のルールは「置けるのは4冊まで、5冊目を置きたいときは最後に参照してから最も時間が経過している (=最も長く使っていない) ファイルをしまう」というもので、これは LRU (Least Recently Used) 方式そのものです。参照列 A,B,C,D,B,A,E,A,B,F を順に追うと次のようになります。 1回目 A / 2回目 B / 3回目 C / 4回目 D — ここで机上は A,B,C,D の4冊で満杯。 5回目 B: すでに机上にあるのでしまう必要はなく、B の参照時刻だけが最新になる。 6回目 A: 同様に机上にあるので退避なし、A の参照時刻が最新になる。 7回目 E: 机上に無い。この時点の最終参照時刻は C が3回目、D が4回目、B が5回目、A が6回目なので、最も古いのは C → C をしまう。机上は A,B,D,E。 8回目 A: 机上にあるので退避なし、A の参照時刻が最新になる。 9回目 B: 机上にあるので退避なし、B の参照時刻が最新になる。 10回目 F: 机上に無い。この時点の最終参照時刻は D が4回目、E が7回目、A が8回目、B が9回目なので、最も古いのは D → D をしまう。机上は A,B,E,F。 したがって引き出しにしまわれた順は C→D で、最後にしまうファイルは D となり、正解は「ウ」です。
不正解エ
E は7回目に C と入れ替わりで机上に載ったファイルで、10回目の時点の最終参照は7回目と、D (最終参照は4回目) より新しいため追い出されません。E はこの参照列の間、一度も引き出しにしまわれないファイルです。
ここがポイント
- 「最後に参照してから最も時間が経過したものを追い出す」= LRU (Least Recently Used) 方式。仮想記憶のページ置換やキャッシュの入替えで使われる代表的なアルゴリズムで、入れた順に追い出す FIFO と混同しないこと。
- LRU のトレースのコツは、参照するたびにそのファイルの最終参照時刻を最新に更新すること。すでに机上 (メモリ上) にあるものを参照した場合は退避が起きないが、その分ほかのファイルが相対的に古くなり、次に追い出される対象が変わる。
用語