multithreading - How do I process a partial order of tasks concurrently using Perl?

Question

I have a partially ordered set of tasks, where for each task all of the tasks that are strictly before it in the partial order must be executed before it can be executed. I want to execute tasks which are not related (either before or after one other) concurrently to try to minimise the total execution time - but without starting a task before its dependencies are completed.

The tasks will run as (non-perl) child processes.

How should I approach solving a problem like this using Perl? What concurrency control facilities and data structures are available?

Answer 1

Looks like a full solution is NP-complete.

As for a partial solution, I would use some form of reference counting to determine which jobs are ready to run, Forks::Super::Job to run the background jobs and check their statuses and POSIX::pause to sleep when maximum number of jobs is spawned.

No threads are involved since you're already dealing with separate processes.

Read the first link for possible algorithms/heuristics to determine runnable jobs' priorities.

Answer 2

我会使用数组的散列。对于每个任务，其所有先决条件都将在相应的数组中提及：

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

我会将已完成的任务保存在不同的哈希中，然后就

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