Задание №22: Многопроцессорные системы и параллельные процессы

(Е. Джобс) В файле 22-58.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Для одного из процесса неизвестно, после какого процесса х он должен начать работать. Известно, что минимальное время выполнения всех процессов равно 17 мс. Найдите номер процесса х.
Типовой пример организации данных в файле:
Пусть минимальное время выполнения данной совокупности процессов равно 10 мс. В данном случае минимальное время окончания процесса 1 – 4 мс от начала запуска процессов, процесса 2 – 3 мс, процесса 4 – 6 мс (3 мс + 3 мс), следовательно, третий процесс может завершиться за 10 мс. Так как время его выполнения 6 мс, то он должен начаться не позднее, чем через 4 мс после начал выполнения всех процессов. Через 4 мс заканчивается только один процесс – процесс 1. Значит, х равен 1.