プロンプトとコンテキスト
固定された N 人のワーカーを持つスケジューラを実装してください。そのパブリックAPIは submit(task)、shutdown()、および awaitTermination() です。各ワーカーはdequeを所有します。オーナーはローカルワークをLIFO順で取得し、アイドル状態のワーカーは反対側の端からFIFO順でスチール（盗取）します。タスクはさらにタスクを作成できますが、シャットダウン開始後は新しいルートの投入は拒否されます。
まずはミューテックスで保護された正確性のベースラインから始め、その後Chase–Levスタイルのロックフリーdequeでそれをどのように置き換えるかを説明して構いません。スケジューラはタスクを失ったり、2回実行したりしてはなりません。タスクの失敗によってワーカーのループが終了してはなりません。空のキュー、スチール対象の不在、シャットダウンの競合、ブロッキングワーカーを網羅してください。
面接官がテストしていること
優れた回答では、単に「スレッドプールを使用する」と言うのではなく、オーナーの操作とスチールの間の並行性境界を明確にします。ローカルのLIFOは局所性と深さ優先の振る舞いを維持し、リモートのFIFOはスティーラー（盗むワーカー）により古く、往々にしてより大きなワークを与えます。面接官はまた、投入、受け付け停止、ドレイニング（排気処理）、ワーカーの終了が明示的な状態マシンを形成しているか、そしてタスクの取得を一意にする線形化ポイント（linearization point）を特定できるかも確認します。
明確化のための質問
- タスクはI/Oでブロックされる可能性がありますか？もしそうなら、独立したI/Oプールまたはカウント付きブロッキング補償を使用してください。すべてのワーカーがブロックされている場合、スチールを増やしても解決になりません。
submitはfutureを返しますか？もしそうなら、例外の伝播とキャンセルを定義してください。この回答ではfutureを返し、キャンセルはまだ取得されていないワークが実行されないことのみを保証します。- dequeはロックフリーかつ無制限である必要がありますか？そうでなければ、まずはロック付きdequeを実装し、競合とメモリ回収の要件が証明された場合にのみアップグレードしてください。
- シャットダウンは即時ですか、それともグレースフル（段階的）ですか？この回答はグレースフルです。新しいルートを拒否し、受け入れ済みのワークをドレインしてから終了します。
30秒の回答
各ワーカーにdequeを与え、オーナー側でLIFO、スチール側でFIFOを使用します。まずロック付きベースラインを構築します。submitはキューを選択してワーカーを起こし、ワーカーはローカルワークをポップし、空のときは他のキューからスチールします。タスクは1つの操作がそれを正常に削除した後にのみ実行されるため、2回取得されることはありません。シャットダウンは新規投入を停止し、スケジューラがドレイニング中であり、未処理ワークがゼロで、すべてのキューが空である場合にのみワーカーが終了します。テストでは並行投入、スチールの競合、子タスクの作成、例外、シャットダウン、アイドル待機をカバーします。
ステップバイステップの詳細解説
状態 accepting、draining、および terminated を定義します。accepting 中は、submitは負荷の低いdequeにワークを配置し、未処理カウンターをアトミックにインクリメントしてワーカーを起こします。draining 中に、実行中のタスクが子タスクを作成できるかどうかは規約の一部です。このバージョンでは子タスクを許可し、カウントがゼロになるまでドレインを続けます。
type Task = () => void;
class WorkStealingScheduler {
private readonly queues: Array<Deque<Task>>;
private accepting = true;
private outstanding = 0;
submit(task: Task): void {
if (!this.accepting) throw new Error("scheduler is shutting down");
const queue = this.chooseQueue();
queue.pushBottom(task);
this.outstanding += 1;
this.wakeOneWorker();
}
run(workerId: number): void {
while (true) {
const task = this.queues[workerId].popBottom()
?? this.stealFromOtherQueues(workerId);
if (!task) {
if (!this.accepting && this.outstanding === 0) return;
this.parkBriefly();
continue;
}
try { task(); } finally { this.outstanding -= 1; }
}
}
}このスニペットは、状態遷移を示すための意図的なシングルスレッド疑似コードです。実際の実装では、submit、outstanding、シャットダウン、およびウェイクアップに対して単一の同期プロトコルを使用する必要があります。空チェックの直後にタスクが到着するロストウェイクアップ（lost-wakeup）競合を回避するには、単純なスリープではなく、条件変数、セマフォ、またはカウント付きイベントを使用します。
ロック付きベースラインは3つの不変条件を維持します。タスクはdequeからの正常な削除後にのみ実行されること、2つの操作が同じタスクを削除できないこと、そして outstanding が受け入れ済みだが未完了のワークと等しいことです。実行中のタスクが子タスクを作成する場合、親をデクリメントする前に子を登録してください。そうしないと、一時的なゼロによって早期終了が引き起こされる可能性があります。
公平性は被害者（スチール対象）の選択とスチールのバッチサイズに依存します。純粋なランダム性は長期間偏る可能性があり、固定ラウンドロビンは1つのホットなキューに多くのスティーラーを集中させる可能性があります。ランダム化された開始位置、スチール失敗時のバックオフ、有界バッチを使用してください。小さく均一なタスクは単一または小規模なスチールに適しており、再帰的なワークロードはより古く大きなチャンクを取得することで恩恵を受けることがよくあります。
ロックフリーは最適化であり、デフォルトの回答ではありません。OracleのForkJoinPoolはワークスティーリングを使用し、チューニング用にスチール数を公開しています。Chase–Lev dequeはさらにアトミックなインデックス、メモリオペレーションの順序付け（メモリオーダリング）、拡張、安全なメモリ回収を必要とします。明示的な単一オーナー/複数スティーラーモデルと回収計画がなければ、自作の「ロックフリー」コードはロック付きベースラインよりも作業を重複させたり解放済みストレージを使用したりする可能性が高くなります。
期待されるローカルのpush/popコストはO(1)です。スチールはO(1)またはO(batch)であり、単純にV個の対象をスキャンするとO(V)かかります。空間計算量はO(T + N)で、ここでTは未完了のワーク、Nはワーカー数です。ブロッキングI/Oはアイドル状態のワーカーが常にスチールできるという前提を無効にするため、ブロッキングワークを分離するか上限を設定してください。
高品質な模範解答
まずはロック付きの正しいバージョンを提示し、その後にロックフリーへのアップグレードについて議論します。各ワーカーはプライベートなdequeを持ちます。オーナーは下部でLIFOを使用し、スティーラーは上部でFIFOを使用し、オーナーとスチールの同期は分離されます。タスクは成功したポップまたはスチールの後にのみ実行に入ります。これがタスク取得の線形化ポイントです。
投入とシャットダウンは別個の関心事です。シャットダウンは新しいルートを拒否し、未処理ワークがゼロになるのを待ちます。実行中のタスクが子タスクを作成できる場合、ドレイニング規約で明示的にそれらを許可しカウントする必要があります。そうでなければ拒否し、タスクにエラーを処理させます。ワーカーはスピンするのではなく条件変数やセマフォで待機し、タスクの例外はワーカーのループから漏れ出さずにfutureやメトリクスにキャプチャされます。
バリアを使用して短時間および長時間のタスクを同時に解放し、正確に1回限りの実行と実際のスチールをアサートし、キューがドレインされることを確認します。次に、子の作成、スチール中のシャットダウン、ブロッキングワーク、タスク例外、シャットダウンの繰り返し呼び出しを注入します。競合と測定結果がそれを正当化する場合にのみ、メモリ順序付けと回収が指定されたChase–Lev dequeでベースラインを置き換えます。
よくある間違い
- 1つのグローバルキュー → すべてのワーカーが1つのロックで競合する → ワーカーごとのdequeを使用し、不均衡はスチールで処理する。
- 空でないことの確認とポップを別々に実行する → 操作の間に別のスティーラーがキューを変更する → 正常な削除をアトミックな取得操作とする。
- シャットダウン中にキューが空に見えたときに終了する → 実行中の親タスクが直後に子を作成する可能性がある → ドレイニング状態と未処理カウンターの不変条件を使用する。
- タスクの例外がワーカーループから脱出するのを放置する → 1つの不良タスクが並行性を低下させる → futureにキャプチャしてスケジューリングを継続する。
- メモリ規則や回収規則なしでロックフリーコードを手書きする → 作業の重複やUse-After-Freeの発生 → まずロック付きセマンティクスを検証し、実績のあるアルゴリズムに従う。
- 常に1つの対象からスチールする → ホットなキューが競合し続ける → ランダム化された開始、バックオフ、有界バッチをメトリクスと組み合わせる。
フォローアップの質問と回答
ブロッキングワークがすべてのワーカーを停止させるのを防ぐにはどうすればよいですか？
シャットダウン時に子タスクが決して失われないことをどのように証明しますか？
単一タスクのスチールよりもバッチスチールが優れているのはどのような場合ですか？
ブロッキングI/Oは独立したプールまたはカウント付きマネージドブロッキングメカニズムに属します。スチールは待機中のワークを移動させるだけです。シャットダウンの証明には状態マシンとカウンターの不変条件を使用します。新しいルートを停止し、親を完了する前に子を登録し、未処理ワークがゼロのドレイニング状態でのみ終了します。バッチスチールはタスクの作成が高密度で各同期のコストが高い場合に役立ちます。極小のキューや極小のタスクでは、移動と公平性のコストが節約分を上回る可能性があります。