Решение: Параллельное выполнение процессов
В файле содержится информация о совокупности $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 |
Типовой пример организации данных в файле:
Решение по шагам
5 шаговПо данным файла для каждого процесса строится интервал выполнения. Если процесс не имеет зависимостей, его выполнение начинается в момент времени 0.
Для процесса, имеющего зависимости, начало выполнения определяется максимальным временем окончания всех процессов-предшественников.
На общей временной шкале отмечаются интервалы выполнения всех процессов. Между соседними моментами начала или окончания число одновременно выполняющихся процессов постоянно.
Для каждого такого отрезка подсчитывается количество выполняющихся процессов. Выбирается максимальное количество, а затем складываются длины всех отрезков, на которых это количество достигается.
По данным прилагаемого файла максимальная продолжительность требуемого отрезка равна 10 миллисекундам.
Где здесь ошибаются
Считать суммарное время выполнения всех процессов вместо времени участка с максимальным числом параллельно работающих процессов.
Не учитывать зависимости между процессами.
Считать процессы выполняющимися параллельно до момента окончания всех зависимых процессов.
Учитывать только один из процессов-предшественников вместо самого поздно заканчивающегося.