基本情報技術者 2012年 春期 午前（科目A） 問22
問題文
ページ置換えアルゴリズムにおけるLRU方式の説明として、適切なものはどれか。
選択肢
ア：最後に参照されたページを置き換える方式
イ：最後に参照されてからの経過時間が最も長いページを置き換える方式（正解）
ウ：最も参照回数の少ないページを置き換える方式
エ：最も古くから存在するページを置き換える方式
🔒 解説は解答すると表示されます
LRUページ置換え方式【午前解説】
正解の理由
選択肢の中でLRU（Least Recently Used）の定義に合致するのは、最後に参照されてからの経過時間が最も長いページを置き換える方式であるためです。LRUは「最後にいつ使われたか」を基準にしており、長時間参照されていないページほど将来参照される確率が低いと仮定します。この説明は選択肢イと完全に一致するため正解です。
解法ステップ
- 問題文のキーワードを確認：「LRU方式」「最後に参照された」「最も長い経過時間」など時間に関する文言を探す。
- 選択肢を「時間基準（LRU）」「回数基準（LFU）」「順序基準（FIFO）」「最近参照（MRU）」に分類する。
- LRUの定義は「最後に参照されてからの経過時間が最も長いものを置き換える」なので、それに一致する選択肢を選ぶ。
- 実装や例外（シーケンシャルアクセスでの劣化など）を理解しておくと記述式でも差がつく。
選択肢別の誤答解説
- ア: 最後に参照されたページを置き換える方式
誤り。これは「Most Recently Used（MRU）」の説明に近く、LRUとは逆の基準です。 - イ: 最後に参照されてからの経過時間が最も長いページを置き換える方式
正解。LRUの定義そのもので、最近参照されていないページを追い出す方式です。 - ウ: 最も参照回数の少ないページを置き換える方式
誤り。参照回数で判断する方式はLFU（Least Frequently Used）であり、LRUとは別です。 - エ: 最も古くから存在するページを置き換える方式
誤り。挿入順（到着順）で追い出す方式はFIFOに相当し、LRUの定義とは異なります。
よくある誤解
- 「LRUは参照回数で決まる」と混同する誤解：参照回数はLFUの基準で、LRUは時間（最終参照時刻）で判断します。
- 「一番古くから存在するページを追い出す＝LRU」とする誤解：その説明はFIFOに近く、挿入時刻（寿命）を基準にしています。
- 実装が簡単だと考える誤解：厳密なLRUは全参照の時刻管理やスタック操作が必要で、実装コストや性能問題が生じます。
補足コラム
LRUの主な実装方法には厳密LRU（スタック、双方向リスト＋ハッシュでO(1)参照）と近似LRU（参照ビット＋周期的クリア、Clockアルゴリズムなど）があります。厳密LRUは正確ですがオーバーヘッドが大きいため、実用OSではClockやAgingといった近似法が多用されます。また、Beladyの最適アルゴリズム（オプティマル）は未来の参照が分かる理想的手法で、LRUはそれに近い現実的な近似と考えられます。
FAQ
Q1: LRUとLFUの違いは？
A1: LRUは「最後にいつ使われたか（時間）」を基準にし、LFUは「どれだけ使われたか（回数）」を基準にします。用途や参照パターンで有利不利が変わります。
A1: LRUは「最後にいつ使われたか（時間）」を基準にし、LFUは「どれだけ使われたか（回数）」を基準にします。用途や参照パターンで有利不利が変わります。
Q2: なぜLRUは万能ではないのか？
A2: シーケンシャルアクセス（長いストリームを一回ずつ読む）では直近に参照されたデータが再利用されないため、LRUは多くのページを不必要に保持し劣化します。
A2: シーケンシャルアクセス（長いストリームを一回ずつ読む）では直近に参照されたデータが再利用されないため、LRUは多くのページを不必要に保持し劣化します。
Q3: 実装上の現実的な選択肢は？
A3: 厳密LRUはコスト高なので、参照ビットを使ったClockアルゴリズムやAgingがよく使われます。これらはLRUの近似で実行効率が良好です。
A3: 厳密LRUはコスト高なので、参照ビットを使ったClockアルゴリズムやAgingがよく使われます。これらはLRUの近似で実行効率が良好です。
関連キーワード: LRU、ページ置換、LRU実装、FIFO、LFU、Clockアルゴリズム、局所性、ページフォールト、キャッシュ戦略、Beladyの最適解
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！