Решение: Параллельное выполнение процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение пяти процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
5 шаговПредставим зависимости процессов в виде ориентированного графа: ребро направлено от процесса к процессу, который зависит от него.
Для каждого процесса вычислим наиболее раннее время начала. Оно равно нулю для независимых процессов, а для остальных определяется окончанием наиболее позднего процесса-зависимости:
$$start(B)=\max_i finish(A_i)$$Время окончания процесса равно сумме времени его начала и продолжительности выполнения:
$$finish(B)=start(B)+t_B$$По полученным интервалам выполнения определим все точки начала и окончания процессов. На каждом промежутке между соседними точками подсчитаем число одновременно выполняющихся процессов.
Максимальный непрерывный промежуток, на котором одновременно выполняются пять процессов, имеет продолжительность $7$ мс.
Где здесь ошибаются
Учитывают только непосредственные зависимости и не учитывают цепочки зависимостей.
Начинают процесс после завершения первого из его предшественников, а не после завершения всех.
Складывают времена всех процессов, хотя независимые процессы могут выполняться параллельно.
Считают общую длительность выполнения пяти процессов вместо длины общего участка времени.