Work stealing とは

並列コンピューティングでは、ワークスティールはマルチスレッドコンピュータプログラムのスケジューリング戦略です。固定数のプロセッサ(またはコア)を使用して、静的マルチスレッドコンピュータ上で新しいスレッドの実行を「スポーン」する動的マルチスレッド計算を実行する問題を解決します。実行時間、メモリ使用量、プロセッサ間通信の両面で効率的です。
ワークスティールスケジューラでは、コンピュータシステムの各プロセッサは、実行すべき作業項目(計算タスク、スレッド)の待ち行列を有する。各作業項目は一連の命令で構成され、順次実行されますが、実行中に他の作業と並行して実行可能な新しい作業項目が生成されることもあります。これらの新しい項目は、最初に作業項目を実行するプロセッサの待ち行列に置かれる。プロセッサの作業がなくなると、他のプロセッサのキューを調べ、作業項目を「盗む」。事実、作業窃取は、スケジューリング作業をアイドル状態のプロセッサに分散させ、すべてのプロセッサが処理する必要がある限り、スケジューリングオーバーヘッドは発生しません。
ワークスティールは、ワークシェアリングとは対照的です。ワークシェアリングは、動的マルチスレッドの一般的な別のスケジューリング手法で、各ワークアイテムは、スポーンされたときにプロセッサにスケジュールされます。このアプローチと比較すると、すべてのプロセッサーが作業するときにこのようなマイグレーションが発生しないため、ワークスティールはプロセッサー間のプロセスマイグレーションの量を削減します。
仕事盗みの考え方は、Multilispプログラミング言語の実装に戻り、1980年代の並列関数プログラミング言語に取り組んでいます。 Cilkプログラミング言語、Java fork / joinフレームワーク、および.NET Task Parallel Library用のスケジューラで使用されています。