multithreading - Perl を使用してタスクの部分的な順序を同時に処理するにはどうすればよいですか?

Question

部分的に順序付けられた一連のタスクがあります。各タスクについて、部分的な順序で厳密にその前にあるすべてのタスクは、実行する前に実行する必要があります。合計実行時間を最小限に抑えるために、関連していないタスクを (前後に) 同時に実行したいのですが、依存関係が完了する前にタスクを開始する必要はありません。

タスクは (Perl 以外の) 子プロセスとして実行されます。

Perl を使用してこのような問題を解決するにはどうすればよいですか? どのような同時実行制御機能とデータ構造が利用可能ですか?

Answer 1

配列のハッシュを使用します。タスクごとに、そのすべての前提条件が対応する配列に記載されます。

$prereq{task1} = [qw/task2 task3 task4/];

完了したタスクを別のハッシュに保持してから、

my @prereq = @{ $prereq{$task} };
if (@prereq == grep exists $completed{$_}, @prereq) {
    run($task);
}

Answer 2

完全なソリューションはNP-complete のようです。

部分的な解決策としては、なんらかの形式の参照カウントを使用して、どのジョブを実行する準備ができているかを判断し、Forks::Super::Jobを使用してバックグラウンド ジョブを実行し、それらのステータスをチェックし、POSIX::pauseを使用して最大数のジョブをスリープ状態にします。ジョブが生成されます。

すでに個別のプロセスを扱っているため、スレッドは関与しません。

実行可能なジョブの優先順位を決定するために考えられるアルゴリズム/ヒューリスティックについては、最初のリンクを参照してください。