← コンピュータ基礎 一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：仮想記憶とページング　|　関連：メモリ階層とキャッシュ・ディスクとストレージ階層

要点（BLUF）

• 物理メモリ（フレーム）が満杯のときページフォルトが起きると、OSはどれかを追い出して新しいページを入れる。その選び方が置換アルゴリズム。
• **OPT（最適）**は「最も遠い将来に使うページ」を追い出す理論上の最善（未来が必要なので実装不可、比較の基準）。LRUは「最も長く使われていない」を追い出す近似。FIFOは「最も古く入れた」を追い出す単純法。
• FIFOにはBeladyの異常（フレームを増やすとフォルトが増えることがある）という落とし穴がある。フォルトが多発する状態がスラッシング。

概念 ── 追い出す相手を選ぶ

仮想記憶とページング のデマンドページングでは、必要なページをディスクから持ってきます。でも物理フレームは有限。満杯のときに新しいページが要れば、誰かを追い出して空きを作る必要があります。

ページフォルトはディスクアクセス（ディスクとストレージ階層）を伴い、メモリの数万倍遅い。だからフォルト数をいかに減らすかが死活問題で、追い出す相手の選び方が効いてきます。

仕組み ── 3つの方式

OPT（最適置換）

「この先、最も長く使われないページ」を追い出す。フォルト数を理論上最小にできることが証明されています。が、未来の参照列を知る必要があり実装不可能。現実の方式が「どれだけOPTに近いか」を測る物差しとして使います。

LRU（Least Recently Used）

「最も長く使われていないページ」を追い出す。「最近使ったものはまた使う」という時間的局所性（メモリ階層とキャッシュ）への賭け。OPTの良い近似だが、厳密な実装は全アクセスに時刻記録が要り高コスト。実OSはクロックアルゴリズム等で近似します。

FIFO（First-In First-Out）

「最も古く入れたページ」を追い出す。実装は最も簡単（キュー1本）。だが「古い＝もう使わない」とは限らず、よく使うページも順番が来れば追い出してしまう。

具体例 ── フォルト数を計算で比べる

同じ参照列・フレーム3で3方式を比較します（[[#対応ラボ]] の 03-03_page_replacement.py）。

refs = [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]
# fifo / lru / opt を実装して faults を数える

実行結果（実機）:

== フレーム数3 のページフォルト数 ==
FIFO: 15  /  LRU: 12  /  OPT(最適): 9

OPT(9) < LRU(12) < FIFO(15)。LRUはOPTにかなり近く、FIFOは見劣りします。局所性を考慮するかどうかの差が、フォルト数＝実速度に効いています。

落とし穴 ── Beladyの異常

直感では「フレーム（物理メモリ）を増やせばフォルトは減る」はず。LRUとOPTでは確かに成り立ちます。ところがFIFOでは、フレームを増やすとフォルトが増えることがある。これがBeladyの異常です。

seq = [1,2,3,4,1,2,5,1,2,3,4,5]
for f in (3, 4):
    print(f"FIFO フレーム{f}: フォルト {fifo(seq,f)}")

実行結果（実機）:

FIFO フレーム3: フォルト 9
FIFO フレーム4: フォルト 10

フレームを3→4に増やしたのにフォルトが9→10に増えた。FIFOは「使用頻度」を見ず「入れた順」だけで追い出すため、メモリを増やしても良くなる保証がないのです。LRU/OPTのようなスタックアルゴリズム（フレーム数を増やすと中身が必ず包含関係になる方式）ではこの異常は起きません。これがFIFOが敬遠される決定的な理由です。

関連現象 ── スラッシング

物理メモリに対し、走らせるプロセスのワーキングセット（当面必要なページ群）が大きすぎると、ページを入れては追い出し、追い出してはまた入れる、を繰り返します。CPUは計算でなくページの出し入れ（ディスクI/O）に追われ、スループットが急落する。これがスラッシングです。

flowchart LR
    load["多重度を上げる（プロセスを増やす）"] --> up["スループット上昇"]
    up --> peak["最適点"]
    peak --> thrash["これ以上増やすと…"]
    thrash --> down["スラッシング（フォルト多発でI/O律速・性能急落）"]

対策は、各プロセスのワーキングセットを見積もり、収まらないなら多重度を下げる（一部プロセスをスワップアウトして待たせる）こと。「詰め込みすぎると全員遅くなる」典型です。

仕組みの直観 ── なぜこの設計か

• OPTを基準にする理由：実装できない理想を物差しにすることで、現実の方式の「伸びしろ」を定量化できる。
• LRUが効く理由：プログラムは局所性を持つ（メモリ階層とキャッシュ）。「最近使った＝また使う」が高確率で当たるから、過去から未来を予測できる。
• FIFOが使われにくい理由：単純だが局所性を無視し、Beladyの異常という非単調性まで持つ。実OSはLRU近似（クロック）を採る。

⚠️ よくある誤解・落とし穴

• 「メモリを増やせば必ず速くなる」→ FIFOではBeladyの異常で逆もある。一般には増設は有効だが、スラッシング域では劇的に効く一方、十分なら頭打ち。
• 「LRUは簡単に実装できる」→ 厳密LRUは全アクセスの記録が要り高コスト。実装は近似。
• 「ページフォルトが多い＝バグ」→ 初回アクセスのフォルトは正常。問題は定常的な多発（スラッシング）。
• 「置換はアプリが制御する」→ OSの仕事。アプリは局所性の高いアクセスで間接的に助ける。

対応ラボ

cs-foundations-study/labs/03-03_page_replacement.py（実行して上記フォルト数とBeladyの異常を確認済み）。

• 確認できること：FIFO/LRU/OPTの比較、Beladyの異常の再現

関連

• フォルト時に読みに行く先の遅さは ディスクとストレージ階層
• 局所性とキャッシュの相似は メモリ階層とキャッシュ
• ページングの基盤は 仮想記憶とページング

← 第3章 メモリ管理 目次