Многопроцессорные системы

(Е. Джобс) В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

У одного из процесса неизвестно, после какого процесса х он должен начать работать. Известно, что минимальное время выполнения всех процессов равно 17 мс. Найдите процесс х.

Типовой пример организации данных в файле:

Пусть минимальное время выполнения данной совокупности процессов 10 мс. В данном случае минимальное время окончания процесса 1 – 4 мс от начала запуска процессов, процесса 2 – 3 мс, процесса 4 – 6 мс (3 мс + 3 мс), следовательно, третий процесс может завершиться за 10 мс. Так как время его выполнения 6 мс, то он должен начаться не позднее, чем через 4 мс после начал выполнения всех процессов. Через 4 мс заканчивается только один процесс – процесс 1. Значит, х равен 1.