¿Cómo se procesa una orden parcial de tareas al mismo tiempo con Perl?

Question

Tengo un conjunto de tareas parcialmente ordenadas, donde para cada tarea se deben ejecutar todas las tareas que están estrictamente ante él en el orden parcial antes de que se pueda ejecutar. Quiero ejecutar tareas que no están relacionadas (ya sea antes o después de otra) al mismo tiempo para intentar minimizar el tiempo de ejecución total, pero sin iniciar una tarea antes de que se completen sus dependencias.

Las tareas se ejecutarán como procesos hijo (no perl).

¿Cómo debo solucionar un problema como este usando Perl? ¿Qué instalaciones de control de concurrencia y estructuras de datos están disponibles?

Answer 1

Utilizaría un hash de matrices. Para cada tarea, todos sus prerrequisitos serán mencionados en la matriz correspondiente:

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

Me gustaría mantener las tareas completadas en un hash diferente, y luego simplemente

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

Answer 2

se ve como una solución completa es NP-complete.

En cuanto a una solución parcial, me gustaría utilizar alguna forma de recuento de referencias para determinar qué trabajos están listos para funcionar, Forks::Super::Job para ejecutar las tareas en segundo plano y comprobar sus estados y POSIX::pause a dormir cuando se genera el número máximo de puestos de trabajo.

No se trata de hilos, ya que se trata de procesos separados.

Lea el primer enlace para obtener posibles algoritmos/heurísticas para determinar las prioridades de los trabajos ejecutables.