マルチスレッドを使用して新しいスケジューリング手法を実装しようとしています。各スレッドには、独自のプライベート ローカル キューがあります。アイデアは、タスクがプログラム スレッドから作成されるたびに、キューの中から最小のキュー サイズ (タスクの数が少ないキュー) を検索し、その中にエンキューする必要があるということです。スレッド間のロード バランシングの方法。ビジーでないキューがより多くエンキューされます。
プログラミングの観点から、指定されたキューの中から最小サイズのキューを動的に見つける方法をいくつかのロジック (または) アイデアを提案してください。
マルチレート同期データ フロー パラダイムを実装する独自のマルチスレッド ライブラリで、Visual Studio 2008、C++ プログラミング言語に取り組んでいます。
ご覧のとおり、負荷の低いキューを見つけようとするのは面倒であり、負荷の高いタスクが 1 つしかないキューにさらに作業を追加する可能性があるため、非効率的な方法になる可能性があります。
作業を盗むヒューリスティックを使用することをお勧めします。スレッドが独自のジョブで完了すると、他のスレッドのキューを調べて、アイドル状態を維持したり終了したりする代わりに、いくつかの作業を「盗みます」。
次に、システムは、すべての人に十分な作業がなくなるまで、各スレッドがアクティブになるように自動的にバランスを取ります。
アイドル状態のスレッドや作業が処理を待機している状況は避けるべきです。
本当にこれを試してみたい場合は、タスクがプッシュ/ポップされると、各キューがパブリックな「int カウント」メンバーを保持するだけでなく、アトミックな inc/dec で更新できますか?
そのような設計が、別のスレッドが非常に短いジョブをキューから取り出そうとしているときに、たまたま非常に長いジョブを実行しているスレッドにタスクがキューに入れられるときの管理オーバーヘッドと時折の「間違い」に見合う価値があるかどうかは、別の問題です。
スレッド間でカウンターを同期できます。しかし、これはあなたが望むものではないと思います。
データフローを使用してすべてを実装したいので、すべてをキューにする必要があります。
最初のオプションは、キュー内のジョブ数を照会することです。単一のリーダー/ライター パターンが必要な場合は、おそらくこの操作にロックを使用する必要があるため、これは簡単ではないと思いますが、これは望んでいるものではありません。注: ここではロックフリー キューを使用できないと推測しています。カウンターを持っているか、2 つのポインターの差を取るか、いずれにしてもロックを持っています。
2 つ目のオプション (ロックフリー コードで実行できます) は、コマンドをディスパッチャー スレッドに送り返し、ワーカー スレッド x がジョブを消費したことを伝えます。このアプローチを使用すると、それぞれ 1 つのワーカー スレッドからディスパッチャ スレッドまで、さらに n 個のキューができます。
スレッドが「マスター」作業キューから作業を取得しないのはなぜですか?
マスターソースから一連のワーカーに作業項目を実際に分散しようとしている場合は、あなたが言うように、負荷分散を行っています。その場合、単純にラウンドロビン スタイルのバランシングを行わない限り、実際にはスケジューリングについて話していることになります。スケジューリングは、コンピューティングの非常に深いテーマであり、数週間または数か月かけて学習することは簡単です。