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

正解

ウ. C

正答率 78.9%（998人中 787人が正解）

問題の解説

正解はウ。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ステップずつ追って確認する.