ワーキングセットモデルとスラッシングの数理

なぜモデルが要るのか：局所性という前提

プログラムのメモリ参照は均一ではありません。ある時間帯にはループ本体・作業配列・直近のスタックフレームといった 少数のページに集中 し、別の時間帯には別の集合へ移ります。これが 局所性の原理（principle of locality） です。時間的局所性（最近触ったページはまた触られやすい）と空間的局所性（隣接アドレスは続けて触られやすい）の二つからなり、デマンドページングや先読みが効くのも、ページ置換で過去から未来を推測できるのも、すべてこの偏りが前提です。

局所性があるなら、「いま実際に必要なページ集合」を物理メモリに常駐させ続ければフォルトは局所性の境界を越えたときだけに収まります。問題は 「いま必要な集合」をどう定義し、どう測るか です。これを形式化したのが Denning の ワーキングセットモデル で、スラッシングの発生条件と多重度制御を数理で導く土台になります。

ワーキングセットの定義とウィンドウ

プロセスの ワーキングセット を、時刻 t から過去 τ の窓に参照された 相異なるページの集合 と定義します。

WS(t, τ) = { 区間 (t-τ, t] に参照されたページ番号 }
w(t, τ) = |WS(t, τ)|        # ワーキングセットの大きさ（ページ数）

ここで τ は ワーキングセットウィンドウ（窓幅）です。単位は実時間ではなく 参照回数（メモリ参照の論理時刻）で測るのが原典の流儀で、「直近 τ 回の参照に登場したページの種類数」が w(t, τ) です。重要な性質を二つ押さえます。

• τ に対し単調非減少：窓を広げれば登場するページ種は減らないため、w(t, τ) は τ について増えるか変わらないかのどちらかです。
• 局所性により飽和する：あるプログラム局面で実際に触るページ集合は有限です。τ を局所性の滞在時間程度まで広げると w(t, τ) は その局面の作業集合サイズで頭打ち になり、τ をさらに広げてもほとんど増えません。

この「飽和してから急に伸びる」形が、後述の τ 選びと PFF 制御の鍵になります。局面が切り替わる瞬間（フェーズ遷移）には、古い集合と新しい集合が一時的に窓内で重なり w(t, τ) が跳ね上がります。

τ の選び方：窓幅とフォルト率のトレードオフ

τ をどう取るかで常駐させるべきページ数が変わり、フォルト率が決まります。

τ を小さくすると、まだ使うページまで窓の外へ落ち、追い出した直後に再フォルトします。τ を大きくすると、もう使わない古いページまで「ワーキングセット内」とみなして常駐させ続け、メモリを浪費します。実用上の τ は ページフォルト率の曲線が平坦になる手前 に置くのが定石で、局所性の滞在時間に対応します。WSClock の窓幅 τ は、この論理を実時間の近似（参照ビットのクリア周期）で実装したものに相当します。

スラッシングの数理：閾値はΣ|WS|とmの大小

ここからが本題です。システムに物理フレームが全部で m ページあり、同時に n 個のプロセスが動いているとします。各プロセスが快適に走るには、自分のワーキングセットが物理メモリに 同時に載っている 必要があります。全プロセスの総和が m を超えるかどうかが分岐点です。

D(t) = Σ w_i(t, τ)        # 全プロセスのワーキングセット総需要（i = 1..n）

D(t) ≤ m  → 各プロセスの作業集合が同時に常駐でき、フォルトは局所性の境界だけに収まる
D(t) >  m  → 作業集合が載り切らず、追い出した直後にまた要る ＝ スラッシング

D(t) > m の状態が スラッシング（thrashing） です。各プロセスは自分の作業集合を維持できず、あるプロセスのフォルトが別プロセスの常駐ページを追い出し、追い出された側もすぐフォルトして取り返す、という 奪い合い が連鎖します。CPU はほぼ常にページイン I/O を待ち、実効的な仕事が進みません。

この閾値の本質は、置換アルゴリズムでは越えられない点にあります。LRU だろうが WSClock だろうが、D(t) > m では「追い出すべきでないページしか残っていない」ため、どれを選んでもすぐ再フォルトします。賢い置換はフォルトを 減らす が、需要が容量を超えた領域では 救えない。本質的対策は需要 D(t) を下げる（多重度を減らす）か、容量 m を上げる（メモリ増設）の二択です。

ワーキングセット法による多重度制御

ワーキングセットモデルは、そのまま メモリ割当と多重度の制御則 になります。OS は各プロセスの w_i(t, τ) を周期的に推定し、総需要 D(t) を物理フレーム数 m と突き合わせます。

周期ごとに:
    各プロセス i の w_i(t, τ) を推定（窓内に参照されたページ数）
    D = Σ w_i
    if D ≤ m:
        全プロセスを実行可能に保つ
        余裕(m - D)があれば、待機中プロセスを新規にアクティブ化（多重度↑）
    else:                       # D > m：スラッシング域
        プロセスを1つ選んでサスペンド（丸ごとスワップアウト）し
        その w を D から外す。D ≤ m になるまで繰り返す（多重度↓）

要点は プロセス単位でメモリを丸ごと退避させる ことです。ページ単位で少しずつ削っても、作業集合を割り込まれた全プロセスがフォルトし続けて状況は変わりません。一つを完全に止めてそのフレームを残りに明け渡せば、生き残ったプロセスは作業集合を確保でき、全体のスループットがむしろ上がります。サスペンドされたプロセスは需要が下がった後に再開（スワップイン）されます。退避の仕組みは スワップ機構の内部実装 を参照してください。

PFF制御：フォルト率を直接フィードバックする

w_i(t, τ) の推定は、窓内に触れたページを追跡するコストがかかります。より直接的なのが PFF（page-fault frequency, ページフォルト頻度）制御 です。ワーキングセットの大きさを測る代わりに、その 結果であるフォルト発生率を直接観測 し、各プロセスへのフレーム割当をフィードバック制御します。

原理は単純です。フォルトが頻発する＝割当フレームが作業集合より少ない、フォルトがほとんど起きない＝割当が作業集合より多い（過剰）。そこで上限と下限の二つの閾値を置きます。

連続するフォルト間隔（前回フォルトからの経過）を測る:
    フォルト発生率 = 1 / フォルト間隔

    if フォルト率 > 上限しきい値 U:     # 割当が足りない
        このプロセスにフレームを追加割当
    elif フォルト率 < 下限しきい値 L:   # 割当が過剰
        余ったフレームを回収（他へ回す）
    # L ≤ フォルト率 ≤ U の帯では割当を据え置き（安定）

上限 U を超えたら割当を増やして作業集合を収め、下限 L を割ったら余剰フレームを取り上げて他プロセスに回します。U と L の間に 不感帯（デッドバンド） を設けるのは、割当の発振（増減の繰り返し）を防ぐためです。系全体でフレームの追加要求に応えられなくなった時点が、まさに D(t) > m の合図であり、ここで多重度を下げる判断につながります。

ワーキングセット法とPFF制御の比較

両者は「作業集合に見合うフレームを与え、スラッシングを防ぐ」という目的を共有しますが、測る対象が違います。

実システムは厳密などちらかを実装するより、参照ビットの近似（WSClock 的な窓）とメモリ圧の監視を組み合わせ、両者の長所を取り込んだ近似制御を行うのが普通です。

まとめ

• ワーキングセット WS(t, τ) は直近 τ の窓に参照された相異なるページ集合で、その大きさ w(t, τ) は τ について単調非減少。局所性により適切な τ で飽和する。
• スラッシング は全プロセスのワーキングセット総和が物理フレーム数を超える Σw_i > m で発生する。多重度を上げ過ぎると CPU 利用率が崖のように急落し、正のフィードバックで悪化する。
• ワーキングセット法 は需要 Σw を直接見て、超過時にプロセスを丸ごとサスペンドして多重度を下げる。PFF 制御 はフォルト率を上限/下限の二閾値でフィードバックしてフレーム割当を増減する。
• スラッシングは 置換アルゴリズムでは救えない。本質的対策は多重度を下げるか物理メモリを増やすかの二択。

前提となる仕組みは 仮想記憶（ページング） と ページングとスワップ を、追い出しの論理は ページ置換アルゴリズム、退避の実体は スワップ機構の内部実装、多重度の調停は プロセススケジューリング も合わせて読むと全体像が繋がります。