Как мне обработать частичный порядок задач одновременно с использованием Perl?

Question

У меня есть частично упорядоченный набор задач, где для каждой задачи все задачи, которые находятся строго перед ней в частичном порядке, должны быть выполнены, прежде чем она может быть выполнена. Я хочу одновременно выполнять задачи, которые не связаны (ни до, ни после друг друга), чтобы попытаться минимизировать общее время выполнения, но без запуска задачи до завершения ее зависимостей.

Задачи будут запускаться как (не-perl) дочерние процессы.

Как мне подойти к решению такой проблемы с помощью Perl? Какие средства управления параллелизмом доступны и структуры данных?

Answer 1

Похоже, что полное решение NP-complete .

Что касается частичного решения, я бы использовал некоторую форму подсчета ссылок, чтобы определить, какие задания готовы к запуску, Forks :: Super :: Job для запуска фоновых заданий и проверки их состояний и POSIX :: pause для сна, когда создается максимальное количество заданий.

Нет потоков, поскольку вы уже имеете дело с отдельными процессами.

Прочтите первую ссылку на возможные алгоритмы / эвристики, чтобы определить приоритеты выполняемых заданий.

Answer 2

Я бы использовал хэш массивов.Для каждой задачи все ее предварительные условия будут указаны в соответствующем массиве:

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

Я бы оставил выполненные задачи в другом хеше, а затем просто

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