Задание №59088 ЕГЭ Информатике

Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы и любой процесс был расположен после всех процессов, от которых он зависит. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов. 

Далее рассчитаем время выполнения оставшихся процессов:

f(4) = 7 + f(3) = 7 + 9 = 16;

f(5) = 6 + f(3) = 6 + 9 = 15;

f(6) = 2 + f(5) = 2 + 15 = 17;

f(8) = 2 + f(7) = 2 + 22 = 24;

f(11) = 6 + f(9) = 6 + 7 = 13;

f(12) = 6 + f(10) = 6 + 8 = 14;

f(3) = 5 + max(f(1), f(2)) = 5 + 4 = 9;

f(7) = 5 + max(f(4), f(6)) = 5 + 17 = 22;

Построим диаграмму выполнения каждого процесса и рассмотрим когда могут выполняться одновременно 4 процесса.

Заметим, что первые четыре процесса можно начинать в любой промежуток времени, так как они независимы. Тогда, если сдвинуть время начала процессов 9 и 10 (новое время обозначено красным), можно получить максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов:

Максимальная продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов равна 7.