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

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

正解の理由

解法ステップ

1. 初期状態は空の3フレームとする。
2. 参照ページを先頭から順に処理する。
   • 参照ページが既に実メモリにあればヒット：ページフォールトは起きない。該当ページを「最も最近使用された」扱いに更新する。
   • 実メモリになければページフォールト：空きフレームがあれば読み込む。空きがなければ「最も最近使われていない（LRU）」ページを追い出して新しいページを読み込む。読み込みはページフォールト1回としてカウントする。
3. 各参照ごとにフレームの中身とLRUで追い出されるページを明示し、ページフォールトの有無を判定する。
4. 全参照を終えたときのページフォールト総数が解。

参照列の逐次シミュレーション（詳細）

選択肢別の誤答解説

• ア: 9
  • 1回分足りない数になっている場合、どこかの参照をヒットと誤認している可能性が高いです。本問では特にステップ9または12での置換を見落とすミスが起きやすいです。
• イ: 10
  • 正解。上の逐次表で示したように合計10回のフォールトとなります。
• ウ: 11
  • 1回多い数を選ぶ誤りは、ヒットの参照（ステップ8や11）を誤ってフォールト扱いにしてしまったことが原因です。ヒット時は置換もフォールトも起こらない点を忘れがちです。
• エ: 12
  • すべての参照でフォールトが起きると仮定した誤りです。初期の空フレームを考慮しても最大で12とは限らず、ヒット発生箇所（本問ではステップ8と11）が存在するため過大評価になります。

よくある誤解

• LRUを使うのに「最初に入ったページを追い出す（FIFO）」と混同する。LRUは「最も長い間参照されていない」ページを追い出す点が異なります。
• ヒット時にページの「使用時刻（最近使用）」を更新しないまま処理を進めてしまい、次の置換判定で誤ったページを追い出す。特に本問のステップ8・11のヒット後の更新を忘れると誤答につながる。
• 初期フレームを全て空としない、または初期ロード時のフォールト数を適切にカウントしない（最初に読み込むページは各々フォールトとして数える）点。

補足コラム

• LRUの実装方法
  • スタック（または双方向連結リスト）で参照ごとにページを先頭に移動し、末尾を追い出す方法（O(1)に近い操作が可能）。
  • ハッシュ＋double-linked listで高速化する実装が一般的（OSやキャッシュの実装で用いられる）。
  • ハードウェア支援がない場合、完全なLRUはコストが高いため CLOCK（近似LRU）などが用いられることがある。
• 試験での省力化テクニック
  • 小さなフレーム数・参照列なら手で逐次シミュレーションするのが確実。フレームの中身と「直近使用順（MRU→…→LRU）」を簡潔にメモすることでミスを減らせます。

def lru_faults(refs, frames):
    mem = []
    faults = 0
    # mem を MRU->...->LRU の順で保持
    for p in refs:
        if p in mem:
            # ヒット：p を先頭（MRU）に移動
            mem.remove(p)
            mem.insert(0, p)
        else:
            # フォールト
            faults += 1
            if len(mem) < frames:
                mem.insert(0, p)
            else:
                # LRU は末尾を削除
                mem.pop()
                mem.insert(0, p)
    return faults

print(lru_faults([0,1,2,3,4,0,2,4,3,1,4,5], 3))  # -> 10

FAQ