ページ置換はどう機能し、何がスラッシングを引き起こしますか?

Question

IT Interview Practice · Accepted Answer

物理 RAM が満杯なのにプロセスがさらにページを必要とすると、OS は場所を空けるために常駐ページを **追い出さ (evict)** ねばなりません — ダーティなら **swap** (ディスク) に書き出します。どのページを追い出すかが **ページ置換 (page replacement)** の決定で、これを誤るとパフォーマンスが台無しになります。

## 置換ポリシー

理論的最適は、将来最も先に使われるページを追い出すこと (**Bélády の OPT**) — 未来は見えないので不可能です。そこで **LRU (least recently used — 最近最も使われていない)** を近似します: 最も長く使われていないページを追い出す。真の LRU はアクセスごとにタイムスタンプが必要 (高コスト) なので、実際のカーネルは **clock (second-chance) アルゴリズム** を使います:

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

Clock は O(1) のコストで LRU 相当の結果を出します。Linux は **active/inactive の LRU リスト** でさらに洗練させています。

## Working set とスラッシング

プロセスの **working set** は、ある時間窓の中でそれが活発に使うページの集合です。paging は *結合された working set が RAM に収まる限り* うまく機能します。収まらないと:

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

スラッシングは坂ではなく崖です: 限界を少し超えるだけでスループットが崩壊します。ほぼすべてのアクセスがミスするからです。症状: CPU はほぼアイドルなのにディスク I/O が飽和し、レイテンシが爆発します。

## 修正 / 回避

- **RAM を追加** するか **負荷を減らす** (同時プロセスを減らす) ことで working set を収める。
- scheduler はプロセス全体を **サスペンドして swap-out** し、需要を縮められます (中期スケジューリング)。
- Linux の **OOM killer** は最後の手段 — 永遠にスラッシュするよりプロセスをキルします。
- **局所性 (locality)** を改善して working set 自体を小さくする。

## なぜ重要なのか

これはメモリの物語全体を結びつけ、シニアお気に入りの質問です。スラッシングが現実の production 障害モードだからです: N ユーザーでは問題ないサービスが、working set が RAM を超える N+1 で崖から落ちます。その特徴 (重い paging、飽和したディスク、停滞した CPU) を認識し、レバー (RAM、負荷制限、局所性 — そして swap がメモリ不足をレイテンシの大惨事に変えること) を知っていることが、数分で診断するのと、謎めいてフリーズした箱を見つめるのとの違いです。

置換ポリシー

Working set とスラッシング

修正 / 回避

なぜ重要なのか

関連する質問