スレッドプールと作業窃取スケジューラ

なぜプールで使い回すのか

OSスレッドの生成・破棄は安くありません。カーネルがスタック領域（既定で数MB規模を予約。多くは遅延コミット）を確保し、スケジューラの管理構造を作り、破棄時に回収します。タスクごとに一つスレッドを立てれば、仕事そのものより準備と後始末が重くなる逆転が起きます。さらにスレッド数がコア数を大きく超えると、CPUがレジスタとキャッシュ状態を入れ替えるコンテキストスイッチが頻発し、実効スループットが落ちます。

スレッドプールは、少数の長命なワーカースレッドを最初に作って使い回すことでこの生成コストを償却します。仕事は「スレッド」ではなく**タスク（処理の単位）**として投入し、空いたワーカーが順に拾って実行します。これにより並行度をハードウェアに合わせて頭打ちさせつつ、タスク投入のコストをキューへの追加だけに抑えられます。並行設計全体の地図は並行性モデル（CSP・アクター・STM）に整理してあります。

[タスク投入] → [タスクキュー] → ワーカー1 (実行中)
                              → ワーカー2 (実行中)
                              → ワーカーN (アイドル→次を取得)
# スレッドは N 個のまま固定。タスクだけが流れていく

タスク粒度：細かすぎても粗すぎても損

タスク粒度（granularity）とは、1タスクが担う仕事量のことです。これは性能を左右する第一の設計変数です。

• 粒度が細かすぎる：1タスクの仕事に対してスケジューリングのオーバーヘッド（キュー操作、同期、ワーカーの起床）が相対的に大きくなり、管理コストが本体を食う。1要素ごとにタスク化するような分割がこれにあたります。
• 粒度が粗すぎる：タスク数がワーカー数を下回ると、遊ぶワーカーが出て並列度を使い切れない。最後の1個の巨大タスクを待つ間、他コアが空転します（テールレイテンシの悪化）。

経験則として、タスク数はワーカー数より十分多く保ち、かつ1タスクがスケジューリングコストを十分上回る仕事量を持つように刻むのが要諦です。Fork/Join型の分割では、ある閾値（cutoff）まで再帰分割し、それ未満は逐次処理に切り替える「分割をやめる境界」を設けるのが定石です。

プールのサイジング：CPUバウンドかI/Oバウンドか

最適なワーカー数は、タスクが何で時間を使うかで決まります。

CPUバウンドな処理は、コアが常に計算で埋まるため、ワーカー数を物理コア数前後にするのが上限です。これを超えると、追加スレッドは実行権を奪い合うだけでスループットは増えず、コンテキストスイッチとキャッシュ汚染でむしろ落ちます。

I/Oバウンドな処理は逆で、ワーカーが応答待ちでブロックしている間、そのコアは遊んでいます。待ち時間の分だけスレッドを増やせば、空いたコアで別タスクを進められます。古典的な見積もりが次の関係です。

ワーカー数 ≒ コア数 × (1 + 待機時間 / 計算時間)
# 計算時間に対して待機が長いほど、多くのスレッドが報われる
# 例: 計算1・待機3 → コア数 × 4 が目安

作業窃取の核心：ワーカーごとの両端キュー

単一の共有キューをN個のワーカーで奪い合うと、そのキューのロックが競合の一点になります。コア数が増えるほど、全員が同じロックを叩いてキャッシュ行を行き来させ、スケールしません。

作業窃取（ワークスティーリング）は、この一点集中を分散で解きます。各ワーカーが**自分専用の両端キュー（double-ended queue, deque）**を持ち、原則として自分のdequeだけを操作します。鍵は、自分と泥棒がdequeの反対側の端から触ることです。

オーナーはタスクを底にpushし、底からpopします（LIFO）。泥棒は他人のdequeの先頭からstealします（FIFO）。両者が逆端を触るため、普段の自分の push/pop は他ワーカーと競合せず、ほぼロックなしで進みます。窃取が実際に起きる稀なときだけ、底と先頭が出会う境界で不可分操作（CASなど）による調停が必要になります。

ワーカーAのdeque:   top → [t1][t2][t3][t4] ← bottom
                     ↑泥棒はここから奪う    ↑自分はここで push/pop
# 自分: t4 を pop（一番新しい＝キャッシュに乗っている）
# 泥棒B: t1 を steal（一番古い＝Aがしばらく触っていない）

なぜこの非対称が効くのか。理由は、新しいタスクほどキャッシュ局所性が高いからです。直前に生成したタスクが触るデータは、生成元ワーカーのL1/L2キャッシュにまだ残っている可能性が高い。だからオーナーはLIFOで熱いタスクを自分で処理します。一方、dequeの先頭にある古いタスクは「しばらく放置された＝もうキャッシュから追い出されている」ので、どのコアで動かしても局所性の損は小さい。さらにFork/Join型では先頭側ほど分割の上流＝大粒のタスクなので、一度盗めば泥棒は当面困らず、窃取の頻度自体が下がります。キャッシュ局所性の一般論はメモリレイアウトとデータ局所性に詳しくあります。

Fork/JoinとTokio：二つの実装

この原理を実装した代表が、JavaのFork/Join FrameworkとRustのTokioランタイムです。狙う負荷は違いますが、骨格は同じ作業窃取です。

Fork/Joinは、大きな計算を fork で部分問題に分け、join で結果を待ち合わせる分割統治に最適化されています。join で子の完了を待つ間、ワーカーは遊ばず自分のdequeから別タスクを引いて進める（あるいは他から盗む）ため、待ち合わせがコアを止めません。ブロッキングが避けられない場合は ManagedBlocker で補償スレッドを一時的に足し、並列度の枯渇を防ぎます。

Tokioは非同期ランタイムで、扱う「タスク」はasync/awaitとコルーチンの内部実装で解説する Future です。await で中断したタスクは、I/O完了などの通知で再びキューに戻され、空いたワーカーが拾います。Tokioのワーカーは通常のdequeに加えて直近に起こされたタスクを置くLIFOスロットを持ち、関連タスク間のキャッシュ局所性を強めています。ただし1タスクが他へ譲らず長時間計算し続けると、そのワーカーのキューが滞り公平性が崩れるため、計算の重い処理は明示的に譲るか別プールへ逃がす設計が要ります。

全体像と設計判断

作業窃取スケジューラの強みは、負荷が偏っても自律的に均すことです。中央のディスパッチャが割り当てを決めるのではなく、暇になったワーカーが自発的に仕事を探しに行く——プッシュではなくプルの分散制御だからこそ、特定ワーカーへの偏りが自然に解消されます。

まとめ

スレッドプールは(1) 少数の長命ワーカーでタスクを回し生成コストを償却する仕組みで、その効きはタスク粒度とプールサイズ（CPUバウンドならコア数前後、I/Oバウンドなら待機比に応じて多め）で決まります。(2) 作業窃取はワーカーごとの両端キューで共有ロックの一点集中を分散し、(3) **オーナーは底からLIFO（局所性）、泥棒は先頭からFIFO（低競合・大粒）**という逆端アクセスで、キャッシュ局所性と負荷分散を同時に取ります。Fork/JoinもTokioもこの骨格を共有し、違いは対象（CPU計算か非同期I/Oか）とブロック隔離の作法にあります。待ち合わせの基礎は同期処理と非同期処理で補強できます。