応用情報技術者 2016年 春期 午前2 問18

LRUアルゴリズム【午前2解説】

正解の理由

解法ステップ

1. 各選択肢が扱う概念（ページ置換、ページテーブル、ページフォールト、フラグメンテーション）を特定する。
2. LRU の定義を確認し、選択肢アが正確かを判定する。
3. 残る選択肢について、OS の仮想記憶・ページングの仕組みと照らし合わせて誤りを排除する（ページテーブルの構造、ページフォールト処理、フラグメンテーションの種類と原因を確認）。
4. 最終的に LRU の定義が一致する選択肢を正解とする。

選択肢別の誤答解説

• ア（正しい）: LRU は「最も長い間参照されていない」ページを置換するアルゴリズムであり、選択肢の記述どおりです。実機では真の LRU はコストが高いため近似手法（Clock アルゴリズムや参照ビットの集計など）がよく使われます。
• イ（誤り）: 「アドレス変換をインデックス方式で行う場合は、主記憶に存在する全ページ分のページテーブルが必要になる。」という記述は不正確です。通常のページテーブル（仮想ページ番号をインデックスにする方式）は仮想アドレス空間のページ数分のエントリを持ちますが、インバーテッド（逆）ページテーブルは物理フレーム数分（実際に主記憶にあるフレーム数分）のエントリで済みます。つまり「インデックス方式」として何を指すかで必要エントリ数は変わり、選択肢は一義的に正しいとは言えません。階層化ページテーブルやハッシュ化（逆ページテーブル）など、実装上の工夫で主記憶の消費を抑えます。
• ウ（誤り）: ページフォールトは参照されたページが主記憶にないときに発生する例外で、OS は該当ページをディスクから読み込んで主記憶に割当てる（必要なら置換して追い出す）処理を行います。ガーベジコレクション（GC）はメモリ管理（主にプログラミング言語のランタイム）における不要オブジェクトの回収であり、ページフォールトの発生そのものに必須な処理ではありません。従ってこの選択肢は誤りです。
• エ（誤り）: フラグメンテーションとはメモリ上に利用できない細かい空き領域が生じる現象を指しますが、文中の「ページングが繰り返されるうちに多数の小さな空きメモリ領域が発生する」との記述は誤解を招きます。ページング（固定サイズページ方式）は連続割当てに伴う外部フラグメンテーション（小さな穴が生じる問題）を防ぎますが、ページ単位で割り当てるためページ内の未使用領域（ページサイズに起因する内部フラグメンテーション）は発生し得ます。また、ページングが頻繁に発生して性能が劣化する状態は「スラッシング（thrashing）」と呼ばれます。したがって元の記述は正しくありません。

よくある誤解

1. ページングはフラグメンテーションを完全に防ぐと思い込む
   • 実際は外部フラグメンテーションは防げますが、ページ内部の未使用領域（内部フラグメンテーション）は発生します。ページサイズ選定でトレードオフがあります。
2. ページテーブルのエントリ数は常に「主記憶にあるページ数」だけで良いと考える誤り
   • 通常の（直線的な）ページテーブルは仮想ページ数分のエントリが必要です。逆ページテーブルは物理フレーム数分のエントリでよい、という違いを押さえておきましょう。
3. ページフォールト＝メモリ管理（GC）の起動と結びつける混同
   • ページフォールトは I/O（スワップ）操作を伴う OS の例外処理であり、GC はランタイムのメモリ回収。別概念です。

補足コラム

• LRU の実装コストと近似手法
  真の LRU を実現するには各ページ参照のたびに完全な時刻管理やリスト更新が必要で、オーバーヘッドが大きいです。実際の OS やハードウェアでは以下の近似が多用されます。
  • Clock（Second Chance）: 参照ビットを用い、リングバッファで走査して置換候補を決める。
  • 参照カウンタ（n ビットの参照履歴）: 時間窓での参照パターンを簡易に保持する。
  • ハードウェア支援（アクセスビット、修正ビット）を利用した実装。
• ページテーブルの構造
  仮想アドレス空間が大きい場合、単純な一次配列のページテーブルは巨大になるため階層化（多段階）ページテーブル、逆ページテーブル（インバーテッド）、またはハッシュテーブル方式が使われます。これらはメモリ使用量と変換速度のトレードオフです。

from collections import OrderedDict

class SimpleLRU:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.cap = capacity

    def access(self, key, value=None):
        if key in self.cache:
            # 最近使われたので末尾へ移動
            self.cache.move_to_end(key)
        else:
            if len(self.cache) >= self.cap:
                # 最も古い（最久使用）を削除
                self.cache.popitem(last=False)
            self.cache[key] = value

FAQ