Work-Stealing

computer-scienceconcurrencyschedulingalgorithm

並列タスクスケジューリングアルゴリズム。暇なスレッドが忙しいスレッドからタスクを「盗む」ことで負荷を動的に分散する。1999年の Cilk プロジェクト (MIT) で理論的基盤が確立された。rayon が Rust 実装として代表的。

基本構造

graph LR
    subgraph Pool["スレッドプール"]
        subgraph T0["Thread 0"]
            D0["Deque<br/>T_a ← push/pop (LIFO)<br/>T_b<br/>T_c"]
        end
        subgraph T1["Thread 1"]
            D1["Deque<br/>T_d<br/>T_e"]
        end
        subgraph T2["Thread 2 (idle)"]
            D2["Deque<br/>(empty)"]
        end
    end
    D2 -->|"steal (FIFO)<br/>底から盗む"| D0

各ワーカースレッドがローカルの deque (両端キュー) を持つ。

Deque (両端キュー) の二つの操作面

操作方向実行者特性
push / popLIFO (上端)オーナースレッドロック不要。キャッシュ局所性が高い
stealFIFO (底端)他のスレッドCAS ベースのロックフリー操作

この非対称性が work-stealing の性能の鍵:

Chase-Lev Deque

work-stealing で最も広く使われるロックフリー deque 実装。rayon は crossbeam-deque (Chase-Lev の Rust 実装) に依存している。

graph LR
    subgraph Deque
        direction LR
        T6["T6"] --- T5["T5"] --- T4["T4"] --- T3["T3"] --- T2["T2"] --- T1["T1"] --- T0["T0"]
    end
    B["bottom<br/>(オーナー側)<br/>push/pop"] --> T6
    Top["top<br/>(スティーラー側)<br/>steal"] --> T0

動作フロー

1. タスク生成

graph TD
    J["join(task_a, task_b)"] --> A["task_a を現スレッドで即座に実行"]
    J --> B["task_b を deque に push<br/>(他スレッドが steal 可能に)"]

2. タスク消費

loop {
    if let Some(task) = my_deque.pop() {
        // 自分の deque にタスクがある → 実行
        task.execute();
    } else {
        // 暇 → ランダムに他スレッドを選んで steal を試みる
        let victim = random_thread();
        if let Some(stolen) = victim.deque.steal() {
            stolen.execute();
        } else {
            // steal 失敗 → 再試行 or スリープ
            yield_or_sleep();
        }
    }
}

3. join の完了待ち

task_a が完了した後、task_b の状態に応じて分岐:

graph TD
    A["task_a 完了"] --> C{"task_b は<br/>盗まれた？"}
    C -->|No| D["自分の deque から pop して実行"]
    C -->|Yes| E["完了を待つ間<br/>他スレッドの仕事を steal して処理"]
    E --> F["task_b 完了通知を受け取る"]

この「待ちながらも steal する」動作が、スレッドを遊ばせない設計の核心。

分割統治との相性

work-stealing は再帰的な分割統治 (divide-and-conquer) と最も相性が良い:

fn parallel_sum(data: &[i32]) -> i32 {
    if data.len() <= THRESHOLD {
        // 十分小さければ逐次実行
        data.iter().sum()
    } else {
        let mid = data.len() / 2;
        let (left, right) = data.split_at(mid);
        // join: left を即実行、right を deque に push
        let (l, r) = rayon::join(
            || parallel_sum(left),
            || parallel_sum(right),
        );
        l + r
    }
}

分割のたびにタスクが deque に push され、暇なスレッドが steal する。データサイズに応じて自然に並列度が調整される。

理論的保証

Cilk プロジェクト (Blumofe & Leiserson, 1999) の証明による:

指標保証
期待実行時間T₁/P + O(T∞) (T₁: 逐次時間, P: プロセッサ数, T∞: クリティカルパス)
steal 回数の期待値O(P × T∞) — スレッド数とクリティカルパスに比例
空間使用量O(P × S₁) (S₁: 逐次実行時のスタック使用量)
線形スピードアップT∞ ≪ T₁/P なら ほぼ P 倍の高速化

直感的な解釈: 十分な並列性がある問題なら、work-stealing はほぼ最適に近い負荷分散を達成する。steal のオーバーヘッドはクリティカルパスに比例するだけで、全体の仕事量には比例しない。

他のスケジューリング手法との比較

手法負荷分散オーバーヘッドキャッシュ局所性
Work-Stealing動的。暇なスレッドが盗むsteal は稀。通常はローカル pop高い (LIFO)
Work-Sharing動的。タスク生成時に他スレッドに配布タスク生成ごとに通信低い
静的パーティショニング事前分割ゼロ最高
タスクキュー (共有)動的。全スレッドが1つのキューから取得キューがボトルネック低い

work-stealing は「通常はローカルで完結し、不均衡時だけ steal する」ため、バランスの良いワークロードでも不均衡なワークロードでも効率が良い。

実装上の注意点

steal 失敗時のバックオフ

全スレッドが暇な状態 (仕事がない) で steal を繰り返すと CPU を無駄に消費する。実装ではスピンループ → yield → futex/condvar wait と段階的にバックオフする。

キャッシュの考慮

デッドロックリスク

work-stealing プール内でブロッキング I/O やロック待ちを行うと、全スレッドがブロックされてデッドロックに陥る可能性がある。CPU バウンドな計算専用にすべき。

押さえどころ（カード化候補）

関連

Graph

Backlinks