ページ置換アルゴリズム とは？

物理メモリが満杯のときに「どのページを追い出して新しいページの場所を空けるか」を決めるルールだよ。満席の映画館で新しいお客さんを入れるために、誰に席を譲ってもらうかを決める仕組みみたいなものだね。

代表的なのは3つ。FIFO（先に入ったページから追い出す）、LRU（最近一番使われていないページを追い出す）、OPT（将来最も長く使われないページを追い出す）だよ。OPTは理論上最適だけど未来予知が必要だから実装できない、あくまで比較基準なんだ。

理論的にはOPTに近い性能が出るから優秀なんだけど、すべてのページアクセスの時刻を記録する必要があって実装コストが高いんだ。だから実際のOSではClockアルゴリズム（参照ビットを使ったLRUの近似）がよく使われているよ。Linuxカーネルも改良版のClockベースの方式を採用しているんだ。

FIFOには「Beladyの異常」という厄介な現象があるんだ。物理メモリのフレーム数を増やしたのに、逆にページフォールトが増えることがあるんだよ。直感に反するけど、古い順に追い出すだけだと「頻繁に使うページ」も容赦なく追い出してしまうのが原因だね。

ページ置換アルゴリズムの選択はシステム全体の性能に直結するよ。不適切な方式だとページフォールトが多発してスラッシングに陥ることもある。最近のOSは単純なアルゴリズムではなく、ワーキングセット（プロセスが頻繁にアクセスするページ群）の大きさを追跡して、メモリ割り当て量自体を動的に調整する仕組みも組み合わせているんだよ。