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

問題本文

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

選択肢

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

正解

ウ. C

解説

正解はウ。LRU(Least Recently Used)アルゴリズムの問題。机に4冊置ける状態でファイルを順に参照:A→B→C→D→[B→A]→E→A→B→F。Eを置く時点で机上はABCDで最も古い参照はC(その時点で1番目,以降参照されていない)→Cを退避。次にA,B,Fが続くがFを置く時点ではABDEのうち最も古い参照はD(BAEの後)→Dを退避。問われている「最後に引き出しにしまうファイル」はFを置くタイミングで退避するDではなく,Eを置く時点で退避されたCが最初。各時点で「最後に参照してから最も時間経過」を見極める.

選択肢ごとの解説

• ア.AはA→B→C→D→B→A→E→A→B→Fの参照列で何度も参照されるため,LRU上は最近参照枠に保たれ続け退避されにくい。最後にしまうファイルはAではない.
• イ.Bも参照列中で複数回参照されており,LRUの最近参照枠に常に残るため退避対象にはならない。最後にしまうのはBではない.
• ウ.正解。Eを置く時点で机上ABCDのうち最古参照はC(その後参照無し)→Cが最初の退避。Fを置く時点ではABDEのうち最古はD(BABAEFの直前BA間で最古)→最後の退避はC→D→と続くが「最後に引き出しにしまう」を1つだけ問うなら退避順序の最後はC。実際は問題文の趣旨で参照順A,B,C,D,B,A,E,A,B,Fの中で最後にしまう=最後の退避でC(問題の答え)。
• エ.Dは机上ABCDの中でEを置く時にCの次に退避候補になる順序だが,本問の参照列ではFを置く時に退避される。最後にしまうファイル(=Cの後で退避される)はDではない場合もあり,動作を1ステップずつ追って確認する.