Work stealing とは

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

Blocking (computing) とは

計算において、プロセスは実行されているコンピュータプログラムのインスタンスである。プロセスは常に正確に1つのプロセス状態で存在します。ブロックされるプロセスは、リソースが使用可能になったり、I / O操作が完了したりするなど、何らかのイベントを待っているプロセスです。
マルチタスクコンピュータシステムでは、個々のタスクまたは実行スレッドは、システムのリソースを共有しなければならない。共有リソースには、CPU、ネットワークおよびネットワークインターフェイス、メモリおよびディスクが含まれます。
1つのタスクがリソースを使用している場合、他のタスクがリソースにアクセスすることは一般的に不可能であり、望ましくない。このような同時使用を防止するために相互排除の手法が使用されています。他のタスクがブロックされると、最初のタスクが共有リソースの使用を終了するまで実行できません。
プログラミング言語とスケジューリングアルゴリズムは、オーバーオールエフェクトブロッキングを最小限に抑えるように設計されています。ブロックするプロセスは、ローカル作業タスクの進行を妨げる可能性があります。この場合、「ブロッキング」はしばしば望ましくないと見なされます。ただし、このような作業タスクは、スケジューリングが続行されるため、他の作業に影響を与えないか、ほとんど影響を与えない独立したプロセスに割り当てることができます。一例は、チャネルのセマンティクスの一部である他の部分(ポーリングやスピンループなし)を受動的に待つ「チャネル上でのブロック」です。正しく設計されたものは、反応系を実現するために使用することができます。
デッドロックとは、プロセスが病理学的にお互いを円で待つことを意味します。したがって、それはブロッキングに直接関連していません。
プロセスが待機している(「ブロックされている」)イベントが発生すると、プロセスはブロックされた状態から実行可能な状態などの差し迫った状態に進みます。

Light-weight process とは

コンピュータオペレーティングシステムでは、軽量プロセス(LWP)がマルチタスクを実現する手段です。 Unix System VとSolarisで使用されていた従来の意味では、LWPは単一のカーネルスレッドの上でユーザー空間で実行され、アドレス空間とシステムリソースを同じプロセス内の他のLWPと共有します。スレッドライブラリによって管理される複数のユーザーレベルのスレッドは、1つまたは複数のLWPの上に置くことができます。これにより、マルチタスクがユーザーレベルで実行できるようになり、パフォーマンス上のメリットが得られます。
いくつかのオペレーティングシステムでは、カーネルスレッドとユーザースレッドの間に別個のLWPレイヤーが存在しません。つまり、ユーザースレッドはカーネルスレッドの上に直接実装されます。これらのコンテキストでは、軽量プロセスという用語は通常、カーネルスレッドを指し、用語「スレッド」はユーザスレッドを指すことができます。 Linuxでは、特定のプロセスがリソースを共有できるようにすることでユーザースレッドが実装されます。これらのプロセスを「軽量プロセス」と呼ぶことがあります。同様に、SunOS 4以降(Solarisより前)の「軽量プロセス」はユーザースレッドを指していました。

Coscheduling とは

コスケジューリングは、スケジューリング関連プロセスの同時システムが、異なるプロセッサ上で同時に(並行して)実行するための原則です。これを実現するための様々な具体的な実装が存在する。
アプリケーションが密接に連携しているプロセスの集合で構成されていて、すべてではないが一部のプロセスが実行スケジュールされている場合、実行中のプロセスは実行していないプロセスと通信しようとする可能性があり、最終的には他のプロセスの実行が予定されていますが、現時点では状況が逆転して他のプロセスとのやりとりがブロックされる可能性があります。結果として、アプリケーションは、タイムスライス当たり最大で1つのプロセス間相互作用の割合で進捗し、スループットが低く、レイテンシが高くなります。