Решение: Параллельное выполнение процессов
В прилагаемом файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
В файле данные представлены в виде таблицы: в первом столбце указан идентификатор процесса, во втором — время его выполнения в миллисекундах, в третьем — через разделитель «;» указаны идентификаторы процессов, от которых зависит данный процесс. Для независимого процесса указано значение 0.
Определите максимальную продолжительность отрезка времени в миллисекундах, в течение которого возможно одновременное выполнение максимального количества процессов, если все независимые друг от друга процессы могут выполняться параллельно.
Решение по шагам
4 шагаПо таблице из файла строится граф зависимостей процессов. Процесс можно запустить только после завершения всех указанных для него процессов-предшественников.
Для каждого процесса вычисляются самое раннее время начала и время окончания. Независимые процессы запускаются одновременно, а зависимые — после завершения необходимых предшественников.
$$t_{\text{нач}}(B)=\max_{A\in P(B)}t_{\text{кон}}(A)$$На временной шкале отмечаются все моменты запуска и завершения процессов. Для каждого получившегося интервала подсчитывается число выполняющихся процессов.
Выбираются интервалы, на которых достигается максимальное количество одновременно выполняющихся процессов. Суммарная продолжительность таких интервалов равна 8 мс.
$$T=8$$Где здесь ошибаются
Считать параллельными процессы, между которыми существует зависимость.
Запускать зависимый процесс до завершения всех его предшественников.
Складывать длительности всех процессов вместо подсчёта времени интервалов с максимальной параллельностью.
Учитывать только один из процессов-предшественников, если их несколько.