Параллельное выполнение процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены через разделитель «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, указано значение 0.
Определите максимальную продолжительность отрезка времени в миллисекундах, в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно и время окончания работы всех процессов минимально.
Для выполнения задания используйте данные из прилагаемого файла.
Условие как в банке ФИПИ — открыть и сверить
| ||||||||||||||||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Представьте процессы в виде ориентированного графа зависимостей и определите моменты начала и окончания каждого процесса.
2Наводящая — какие числа считатьуровень 2 из 3
Процесс можно начать только после завершения всех процессов, от которых он зависит. Для минимального времени окончания запускайте независимые процессы одновременно.
3Прямая — фактически решениеуровень 3 из 3
Постройте интервалы выполнения процессов по данным файла, найдите отрезок, на котором одновременно выполняется максимальное число процессов, и вычислите его продолжительность: $9$ мс.