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