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

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

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

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.