【ページちかんアルゴリズム】
ページ置換アルゴリズム とは？
最終更新:
💡 メモリの場所を空けるとき、どのページを外すか決める
仮想メモリで空き領域を確保する際に、どのページを物理メモリから外すか決める方針。先に入ったページを選ぶFIFO、最後に使ってから最も時間がたったページを選ぶLRUなどがある。効果はアクセスの並びや実装の負担によって変わる。
📌 このページのポイント
- 物理メモリから外すページを選ぶ方針
- FIFOは入った順、LRUは最後に使った順を見る
- LRUがすべてのアクセスで最善とは限らない
- 実際のOSは近似や複数の条件を組み合わせる
ひよこ 何を、置き換えるの？
ペンギン先生 物理メモリの枠であるフレームに入っているページだよ。必要なページを読み込む場所が足りないときなどに、外すページを選ぶ。空きがあるページフォールトなら、置換せず読み込める場合もあるね。
ひよこ FIFOとLRUは、何が違う？
ペンギン先生 FIFOは先にメモリへ入ったページを選ぶ。LRUは最後に使ってから最も時間がたったページを選ぶよ。入った順がA、B、Cでも、直近にAを使えば、両方式が選ぶページは違うことがあるんだ。
ひよこ LRUなら、いつも最適？
ペンギン先生 いつもではないよ。効果はアクセスの並びによる。将来最も長く使わないページを外すOPTは比較の基準になるが、普通のOSは未来のアクセスを知れない。厳密なLRUにも履歴を管理する負担があるんだ。
ひよこ 実際のOSも、この2種類だけ？
ペンギン先生 ひよこ 外したページの内容は、消える？
ペンギン先生 ファイルから読み直せるページも、変更を保存してから外す必要があるページもあるよ。方式だけでなく、書き戻しの負担や使えるメモリも重要。ページの出し入れが頻発するスラッシングにも関係するんだ。
もっと詳しく知りたい人へ
メモリの枠を増やせば、必ずページフォールトは減る？
FIFOでは、同じアクセス列でも枠を増やすとページフォールトが増える場合があります。Beladyの異常と呼ばれ、OSTEPの教材でも例が示されています。アルゴリズムの性質による現象で、メモリを増やすと一般に性能が悪くなるという意味ではありません。
まとめ：ざっくりこれだけ覚えればOK！
「ページ置換アルゴリズム」って出てきたら「メモリの場所を空けるため、外すページを選ぶルール」と思えばだいたいOK！
📖 おまけ：英語の意味
「Page replacement algorithm」 ＝ ページを置き換える手順
💬 仮想メモリのページを扱う言葉だよ。Webページを差し替える話ではないんだ。