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

LRU置換法【ITパスポート解説】

正解の理由

解法ステップ

1. 状態表示は「MRU → LRU（最も最近使った順から最も古く使った順）」で統一して書く。これが混乱を防ぎます。
2. 参照が来たら：
   • 机にあればそのファイルを先頭（MRU）に移動する。
   • 机に無くて空きがあれば追加して先頭にする。
   • 机に無くて空きがないときは、末尾（LRU）を取り除き、新しいファイルを先頭にする。
3. 与えられた参照順 A, B, C, D, B, A, E, A, B, F を順に処理し、各ステップで MRU→LRU を書き出す。

1. A → A
2. B → B, A
3. C → C, B, A
4. D → D, C, B, A （ここで机は満杯）
5. B → B, D, C, A （B を先頭に移動）
6. A → A, B, D, C （A を先頭に移動）
7. E → E, A, B, D （机が満杯なので末尾 C を追い出す）
8. A → A, E, B, D （A を先頭に移動）
9. B → B, A, E, D （B を先頭に移動）
10. F → F, B, A, E （机が満杯なので末尾 D を追い出す）

選択肢別の誤答解説

• ア: A
  9手目で B が MRU、8手目で A は MRU になっているため、10手目時点では A は最近参照されており LRU ではありません。よって誤りです。
• イ: B
  9手目で B が直前に参照され MRU に位置しています。直後の置換で追い出されるような最も古い候補ではありません。
• ウ: D
  正解。10手目で机の末尾（LRU）になっており、F を置くために取り除かれます。
• エ: E
  E は7手目で置かれ、その後 8手目・9手目で A, B が参照されたため E は完全に最下位ではなく、10手目時点では D の方が古くなっています。

よくある誤解

• FIFO と混同する
  FIFO（First In First Out：先に入れたものから出す）は入れた順で追い出します。LRU は「最後に参照された時刻」を基準に追い出すので結果が異なります。
• 表示順の不統一で間違う
  MRU→LRU の順で一貫して表示すると見落としが減ります。途中で表示順を変えると誰でも混乱します。
• 「参照した順＝入れた順」と考える誤り
  既に机にあるファイルを参照しても「新たに入れる」のではなく位置を変える（MRU に移動）点を忘れると誤答します。

補足コラム

FAQ