ページ置換アルゴリズムとは（全体像）
ページ置換アルゴリズムは、メモリがいっぱいになったとき、新しいページを入れる場所を空けるため、どのページを追い出すかを選ぶルールのこと。
身近にたとえると、机の上がいっぱいになったときに、どの本を本棚へ戻すかだ。古く置いた本から戻す（FIFO）、最近読んでいない本を戻す（LRU）、読みかけマークを見て戻す（Clock）、と、選び方にいくつか流派がある。
押さえるのは、「どれを追い出すかの基準」がアルゴリズムごとに違うこと。理想は「これから使わないものを追い出す」ことだが、未来は読めないので、近い判断をする工夫が生まれた。
詳しく：4つのアルゴリズムの違いだけ覚えれば戦える
ここが記事の心臓部。代表的な4つを比べましょう。
ページ置換アルゴリズム4つ
| 方法 | 追い出すページ | 特徴 |
|---|---|---|
| FIFO | 最初に入れた（古い）ページ | 単純。Beladyの異常あり |
| LRU | 最近いちばん使っていないページ | 理想に近いが実装が重い |
| Clock | 参照マークを見て選ぶ | LRUの軽い近似。実用的 |
| OPT | これから先いちばん使わないページ | 理論上の最適。実装できない |
FIFO（先入先出）は、最初に入れた古いページから追い出す方法。単純ですが、Beladyの異常という弱点があります。これは「メモリを増やしたのに、かえって性能が悪くなることがある」という不思議な現象で、FIFOだけに起こります。
LRU（最近最も使われていない）は、最近いちばん使っていないページを追い出す方法。直感的に良い選び方ですが、毎回「いつ使ったか」を記録するため実装が重いです。
そこで実用で使われるのがClock（二次機会）です。各ページに参照マーク（使ったら1）を持たせ、時計の針のように順に見て、マークが1なら0に戻して見逃し、0なら追い出します。LRUに近い性能を、軽い実装で実現できます。
ここで取り違えやすいのがFIFOとLRUです。FIFOは「入れた時刻（到着順）」、LRUは「最後に使った時刻」で選びます。基準が違うので、別物です。
最後にOPT（最適）。これは「これから先いちばん長く使わないページ」を追い出す、理論上いちばん良い方法ですが、未来の使われ方を知っている前提なので実装できません。ほかの方法の良し悪しを測る基準として使います。
わかりやすく言い換えると
要するに、机の本のたとえで覚えるとラクです。
①FIFO・LRU … FIFOは古く置いた本から戻す（到着順）、LRUは最近読んでいない本を戻す（最後に使った順）
②Clock … 読みかけマークを見て戻す（LRUを軽く実装）
③OPT … これから読まない本を戻す（理想だが未来を知る前提で実装できない）
つまり、「FIFOは到着順・LRUは最近使った順」「ClockはLRUの軽い近似」、この2点が試験の急所です。
試験のツボ
🔴 一番出る：FIFOとLRUの違い
①FIFO ＝ 最初に入れた（到着順が古い）ページを追い出す
②LRU ＝ 最後に使った時刻がいちばん古いページを追い出す
🔴 次に出る：Beladyの異常とClock
①Beladyの異常 ＝ FIFOでメモリを増やすと性能が悪化することがある（LRU・Clock・OPTにはない）
②Clock ＝ 参照マークで判定するLRUの軽い近似
🟡 押さえると安定：OPT
①OPT ＝ これから先いちばん使わないページを追い出す理論上の最適
②未来を知る前提なので実装できない（評価の基準に使う）
よくある間違い
①「FIFOとLRUは同じ基準で選ぶ」→ ✗ FIFOは入れた時刻（到着順）、LRUは最後に使った時刻。基準が違う。
②「OPT（最適アルゴリズム）は実際に実装できる」→ ✗ OPTは未来の参照を知っている前提。実用システムには実装できない理論モデル。
③「Beladyの異常はLRUでも起こる」→ ✗ Beladyの異常（メモリ増で性能悪化）はFIFOの弱点。LRU・Clock・OPTには起こらない。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（FIFOとLRU）
FIFOとLRUに関する次の記述のうち、正しいものはどれか。
- FIFOは最後に使った時刻で選び、LRUは最初に入れた到着順で選ぶ方式とされているのだ
- FIFOは最初に入れたページを追い出し、LRUは最近いちばん使っていないページを追い出す
- FIFOもLRUもまったく同じ基準で選び、追い出すページに違いはないものとされているのだ
- FIFOもLRUも紙に印刷する手順のことで、メモリ管理とは無関係なものとされているものだ
解答は 2 ですよ。
FIFOは最初に入れた古いページを追い出し、LRUは最近いちばん使っていないページを追い出しますね。FIFOは到着順、LRUは最後に使った順です。
選択肢1のFIFOとLRUが逆、選択肢3の「同じ基準」、選択肢4の「印刷する手順」はどれも誤りですよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | FIFOとLRUの基準が逆 |
| 2 | ✓ | FIFOは到着順・LRUは使った順 |
| 3 | ✗ | 選ぶ基準が違う |
| 4 | ✗ | 印刷する手順ではない |
オリジナル問題2（Beladyの異常）
Beladyの異常に関する次の記述のうち、正しいものはどれか。
- Beladyの異常はLRUの弱点で、メモリを減らすと必ず性能が上がる現象とされているものだ
- Beladyの異常はすべてのアルゴリズムで必ず起こり、避ける方法はないものとされているのだ
- Beladyの異常はFIFOの弱点で、メモリを増やしたのに性能が悪化することがある現象だ
- Beladyの異常は紙に印刷する装置の故障のことで、メモリとは無関係なものとされている
解答は 3 ですよ。
Beladyの異常はFIFOの弱点で、メモリを増やしたのに性能が悪化することがある現象ですね。LRU・Clock・OPTには起こりません。
選択肢1の「LRUの弱点」、選択肢2の「すべてで起こる」、選択肢4の「印刷する装置の故障」はどれも誤りですよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | FIFOの弱点・メモリ増で悪化 |
| 2 | ✗ | LRUなどでは起こらない |
| 3 | ✓ | FIFOでメモリ増でも悪化しうる |
| 4 | ✗ | 印刷装置の故障ではない |
オリジナル問題3（ClockとOPT）
ClockとOPTに関する次の記述のうち、正しいものはどれか。
- Clockは参照マークで選ぶLRUの軽い近似で、OPTは未来を知る前提で実装できない最適だ
- ClockもOPTもまったく同じ方法で、参照マークも未来予知も使わないものとされているのだ
- Clockは未来を完全に知って選び、OPTは参照マークで選ぶ実用的な方法とされているものだ
- ClockもOPTも紙に印刷する手順のことで、メモリ管理とは無関係なものとされているものだ
解答は 1 ですよ。
Clockは参照マークで選ぶLRUの軽い近似、OPTは未来を知る前提で実装できない最適ですね。OPTは評価の基準に使います。
選択肢2の「同じ方法」、選択肢3のClockとOPTが逆、選択肢4の「印刷する手順」はどれも誤りですよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | ClockはLRU近似・OPTは実装不可 |
| 2 | ✗ | 参照マークと未来予知で別物 |
| 3 | ✗ | ClockとOPTの説明が逆 |
| 4 | ✗ | 印刷する手順ではない |
まとめ
押さえどころ
- 🔴 FIFOとLRU ＝ FIFOは最初に入れた（到着順）、LRUは最後に使った時刻がいちばん古いページを追い出す。
- 🔴 Beladyの異常とClock ＝ FIFOはメモリ増で性能悪化することがある（Beladyの異常）。ClockはLRUの軽い近似。
- 🟡 OPT ＝ これから先いちばん使わないページを追い出す理論上の最適。未来を知る前提で実装できない。
次に学ぶ
- ページング（TLB・階層化） ── ページ置換が起こる土台、アドレス変換とTLBのしくみ。
- OS（オペレーティングシステム） ── メモリ管理を担うカーネルを含む、OSの構成と役割。
執筆: SikakuQuest編集部