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

LRUページ置換【午前2解説】

正解の理由

解法ステップ

1. 各選択肢が示す概念を一点ずつ確認する（LRU、ページテーブルの大きさ、ページフォールト時の処理、フラグメンテーション）。
2. LRUの定義を思い出す：最も長く使われていないページを置換する。
3. ページテーブルやインデックス方式、反転ページテーブルの違いを整理する（エントリ数が「仮想ページ数」か「物理フレーム数」かを確認）。
4. ページフォールト時の典型的な処理（ディスクから該当ページをロード、必要ならページ置換）とガーベジコレクションの役割は無関係であることを確認する。
5. ページングとフラグメンテーションの関係（外部/内部の区別）をチェックする。
6. 各選択肢を照らし合わせて正答を決定する。

選択肢別の誤答解説

• ア：正答。LRUは「最近参照されていない＝使用後の経過時間が最長」のページを置換するアルゴリズムであり、記述と一致します。実装上の注意点としては完全なLRUを実現するにはコストが高く、実用的には参照ビットや時計（Clock）アルゴリズムなどで近似します。
• イ：誤り。ここでの「インデックス方式」が何を指すか曖昧ですが、通常のページテーブル（単純な1次ページテーブル）は仮想アドレス空間のページ数分のエントリを持ちます（＝仮想ページ数に比例）。一方、反転ページテーブル（inverted page table）は物理メモリ中のフレーム数分のエントリしか持ちません。選択肢の「主記憶に存在する全ページ分のページテーブルが必要になる」という記述は誤解を招きます。正しくは、「反転ページテーブルは物理フレーム数分のエントリを持つ」が適切な表現です。
• ウ：誤り。ページフォールトは該当ページが主記憶に存在しないために発生する割り込みで、通常はディスク（補助記憶）からページを読み込む処理（ページイン）を行います。ガーベジコレクションはメモリ管理の別領域（主に言語ランタイムやヒープ管理）で不要になったオブジェクトの回収を行うものであり、ページフォールトの必須処理ではありません。
• エ：誤り。ページングは可変長割当てで発生する「多数の小さな空き領域（外部フラグメンテーション）」を解消する方式です。ただし固定ページサイズのために、各割当ての最後のページに未使用領域が生じることがあり、これを内部フラグメンテーションという点に注意が必要です。したがって「多数の小さな空きメモリ領域が発生すること」をフラグメンテーションの説明とするなら、ページング固有の説明としては誤り（外部ではなく内部フラグメンテーションが発生し得る）です。

よくある誤解

• ページングではフラグメンテーションが全く発生しない：誤り。ページングは外部フラグメンテーションを解消するが、固定ページ単位の割当てにより内部フラグメンテーション（ページ内の未使用領域）が発生し得る。平均的な内部フラグメンテーションはページサイズの半分程度になると考えられる（平均＝$ページサイズ/2$）。
• LRUは常に正確に実装される：誤り。完全なLRUは高コストなので、多くの実装は参照ビットや近似アルゴリズム（Clock、Agingなど）で擬似LRUを実現する。
• ページテーブルの大きさは常に主記憶のページ数に等しい：誤り。単純なページテーブルは仮想ページ数分、反転ページテーブルは物理フレーム数分のエントリを持つ。用途に応じて設計が異なる。

補足コラム

• LRUの実装例：ハードウェアで各ページに「参照ビット」を付けて定期的にシフトするAging法や、Clockアルゴリズムは実用的な近似手法です。完全LRUは各参照の順序を正確に管理する必要があり、高速な更新が求められるシステムでは非現実的なことがあります。
• ページテーブルの節約策：多階層ページテーブル（マルチレベル）やセグメントとページの組合せ、反転ページテーブルなどがあり、それぞれトレードオフ（メモリ使用量／アクセス速度）が異なります。
• 内部フラグメンテーションの期待値：割当てサイズがランダムならば、平均的な未使用領域はページサイズの半分程度になるため、ページサイズ設計はこの観点も考慮されます。

from collections import OrderedDict

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

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # 最近使ったものを末尾へ
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 最も古い（LRU）を削除

FAQ