デマンドページングとスラッシング — メモリが足りないとき起きること
一言でいうと
ページを必要なときにだけ載せれば、物理メモリより大きなプログラムも動かせますが、フォルト1回のコストがメモリアクセスの数万倍も高いので、フォルト率が少し上がるだけでシステムが崩れます。
なぜ必要なのか
プログラム全体をメモリに載せる必要はありません。エラー処理コードのようにほとんど実行されない部分も多く、大きな配列の一部だけが実際に使われる場合もよくあります。必要な時点でだけ載せれば(デマンドページング)、より多くのプロセスを同時に動かせ、プログラムの起動も速くなります。
どう動くのか
ページテーブルエントリに有効ビットを置きます。有効でないページにアクセスすると、ページフォルトが発生し、次の順序で処理されます。
- トラップがかかり、カーネルに入ります。
- 不正なアクセス(アドレス範囲外)なのか、まだ載せていないだけなのかを判断します。
- 空きフレームを探します。なければ犠牲ページを選んで追い出します。そのページが変更された状態(dirty)なら、先にディスクに書き込みます。
- ディスクからページを読み出してフレームに載せます。
- ページテーブルを更新し、フォルトを起こした命令からもう一度実行します。
コストを計算してみると恐ろしくなります。メモリアクセスが200ns、ページフォルトの処理が8msだとします。フォルト確率がpのとき、実効アクセス時間は(1引くp)掛ける200足すp掛ける8,000,000です。
- p = 0.001、つまり1,000回に1回フォルトが起きると、実効アクセス時間は約8,200nsで、フォルトがないときより40倍遅くなります。
- 性能低下を10パーセント以内に抑えるには、pが約0.0000025以下でなければなりません。40万回に1回です。
ページ置換アルゴリズムの性格も知っておく価値があります。参照列7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1にフレームを3つ与えると、FIFOはフォルト15回、LRUは12回、理論上の最適であるOPTは9回です。FIFOには、フレームを増やしたのにフォルトが増えるベレイディの異常まであります。実務のシステムは、純粋なLRUの代わりに、参照ビットを利用したクロック(second-chance)アルゴリズムを使います。LRUに近い性能をはるかに安いコストで得られるからです。
スラッシングは、フレームが不足してフォルトが急増し、そのせいでCPUが遊び、OSが「暇だからプロセスをもっと載せよう」と判断して、状況がさらに悪化する悪循環です。対応は、ワーキングセット(最近の一定区間で実際に参照されたページの集合)を追跡してその分のフレームを保証するか、フォルト率を直接モニタリングしてフレームを調整することです。
現場での姿
コンテナにメモリ制限をかけたとき、2つの結末があります。スワップがオフなら、OOM Killerがプロセスを殺します。突然ですが、原因は明確です。スワップがオンなら、代わりにスラッシングが始まります。プロセスは生きているのに応答が数十倍遅くなり、CPU使用率は低いのにiowaitだけが跳ね上がります。死ぬほうがまだ診断しやすいという言葉が出る理由です。Kubernetesが長い間スワップをオフにするよう要求してきた背景にも、この予測不可能性があります。
続くクイズで確認すること
ページフォルトのコスト計算を自分でできるか、スラッシングがなぜ自分自身を強化する悪循環なのかを説明できるか確認します。