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