ITパスポート 2009年 春期 問85

4冊しか置けない机での「最後に引き出しにしまうファイル」はどれか【ITパスポート 解説】

正解の理由

解法ステップ

1. A → 机に A を置く
   状態: A
2. B → B を追加
   状態: A, B
3. C → C を追加
   状態: A, B, C
4. D → D を追加（満杯）
   状態: A, B, C, D （MRU→LRU：D, C, B, A）
5. B → B はすでに机上にある（ヒット）。B を最新扱いにする
   状態: B, D, C, A （MRU→LRU）
6. A → A はヒット。A を最新扱いにする
   状態: A, B, D, C
7. E → 新しいファイル。満杯なので LRU（最も古い）= C を引き出しにしまう。C を外して E を置く
   状態: E, A, B, D （C が排除）
8. A → A はヒット。A を最新扱いにする
   状態: A, E, B, D
9. B → B はヒット。B を最新扱いにする
   状態: B, A, E, D
10. F → 新しいファイル。満杯なので LRU = D（最後に参照されたのが最も古い）を引き出しにする。よって D を引き出しにしまう。

選択肢別の誤答解説

• ア: A
  誤り。A は 10 ステップ直前（ステップ8）に参照されており、D よりも新しい参照なので最後に引き出される候補にはなりません。
• イ: B
  誤り。B はステップ9で参照され、直前に使用されているため最後に引き出す対象にはなりません。
• ウ: D
  正解。D はステップ4で参照された後、ステップ7以降は参照されておらず、F を置く直前の時点で最も「古く」なっているため引き出されます。
• エ: E
  誤り。E はステップ7に置かれ、その後ステップ8・9でも D よりは新しい状態なので、最後に引き出されるのは D です。

よくある誤解

1. FIFO（先入れ先出し）と混同する
   • FIFO は「先に入れたもの」を出す方式です。LRU は「最後に使われた時間」を基準にします。初期の4つ（A, B, C, D）のうち最初に入れた C を追い出すのではなく、実際の参照履歴で判断します。
2. 「最後に参照した」の意味を取り違える
   • 「最後に参照してから最も時間が経過している」とは、直近の参照時刻が一番古いものを指します。逆に「最後に参照したもの」を出す（最新を出す）わけではありません。
3. ヒット（既に机上にあるファイルを参照した）時に更新を忘れる
   • ファイルが机にあった場合、その参照で「最新（MRU）」になることを必ず反映させないと誤答になります。

補足コラム

• LRU（Least Recently Used）はコンピュータのキャッシュや仮想記憶（ページ置換：メモリ管理でページを入れ替える方法）でよく使われるアルゴリズムです。考え方は「しばらく使われていないものは今後も使われない可能性が高い」と仮定する点にあります。
• 他の代表的な置換アルゴリズム：FIFO（先入れ先出し）、LFU（Least Frequently Used：参照頻度が最も低いものを置換）など。問題文の条件（「最後に参照してから最も時間が経過」）は LRU を指しています。

FAQ