作業中に使うページがメモリに収まらないと、入れ替えばかりで処理が進まなくなる

用語

ページング

仮想メモリを一定サイズのページに分け、物理メモリの枠へ対応付ける管理方式。ページング自体にストレージへの退避が必須とは限らない。

ページフォールト

ページへのアクセスをそのまま実行できず、OSの処理が必要になること。すべてがストレージI/Oを伴うわけではない。

ワーキングセット

ある時間区間に、その処理が活動的に参照するページの集合。同時に動く処理の合計も容量に影響する。

スラッシング

必要なページの入れ替えが頻発し、その待ちや処理が有用な計算を大きく圧迫する状態。

LRU

最も長い間使われていないページを追い出す置換方式。ここでは計算モデルとして使い、実OSが厳密なLRUを使うとは仮定しない。

図と例

計算モデル：物理メモリの枠は3つ、LRUで置換し、初めは空とする。ページA→B→C→Dを3周参照する。4ページが3枠に収まらず、空き枠がなくなると次に必要なページを毎回追い出すため12参照すべてがフォールトになる。4枠なら最初の4参照だけで済む。全ページはストレージに保存済みで、フォールト時に読み戻すものとする。実OSの置換方式やプリフェッチを再現した測定ではない。

実際のサービス・製品では

• Linux / GNU time

  GNU timeは、経過時間とCPU時間に加えてメジャー・マイナーフォールトを表示できる。manページは、メジャーフォールトをストレージからの読み取りが必要なものとして説明している。

  資料を読む

解説

並列ワーカーを増やした後に、処理件数が伸びずストレージI/Oと遅延が増える場面で使う。メモリ量、ストレージの読み取りを伴うメジャーフォールト、スワップI/Oを同じ時間軸で確認する。ワーカーを減らす、小分けに処理する、メモリを増やす案を比べる。ページフォールトの総数だけでスラッシングと断定しない。

仮想アドレスのページを物理メモリの枠へ対応付けるのがページングである。必要なページが未配置などでそのままアクセスできないとページフォールトが起き、OSが対応する。初回のゼロ初期化など、ストレージを読まないフォールトもある。退避したページを読み戻す場合は、I/O待ちが必要になる。空き枠がなければ別のページを置換するが、すぐ再利用するページを追い出すと、次の参照でまた読み戻すことになる。この繰り返しが処理の大半を占める状態がスラッシング。短い時間に繰り返し使うページの集合をワーキングセットと呼び、同時実行する仕事の合計が収まるかを考える。スワップなしなど退避できない条件では、入れ替えで耐える前にメモリ確保の失敗やOOM終了へ進む場合もある。

さらに学ぶ

• OSTEP — Beyond Physical Memory: Mechanisms
• OSTEP — Beyond Physical Memory: Policies
• Linux man-pages — time(1)

チェック

空の3枠にLRUでページを置く。A→B→C→A→Dの順で参照したとき、Dを入れるために追い出すのはどのページ？

1. B（最後の参照が最も古い）
2. A（最初に入れたページ）
3. C（Aを再参照する前に最後に入れたページ）