Задание 22 КЕГЭ: таблица процессов с зависимостями — как определить время выполнения?
Задание 22 про многопроцессорную систему: дана таблица процессов, у каждого время выполнения и ID процессов, от которых он зависит (должны завершиться раньше). Надо найти, за какое минимальное время выполнятся все при достаточном числе процессоров. Я не понимаю, как учитывать зависимости. Подскажите подход.
2 ответа
При достаточном числе процессоров каждый процесс стартует, как только закончились ВСЕ, от кого он зависит. Время завершения процесса = (момент готовности всех зависимостей) + (его длительность).
Алгоритм — посчитать время окончания каждого процесса по зависимостям:
# процессы: id -> (длительность, [зависимости])
proc = {
1: (4, []),
2: (3, [1]),
3: (1, [1]),
4: (5, [2, 3]),
}
finish = {}
def end(pid):
if pid in finish:
return finish[pid]
dur, deps = proc[pid]
start = max((end(d) for d in deps), default=0) # ждём всех зависимостей
finish[pid] = start + dur
return finish[pid]
print(max(end(p) for p in proc)) # всё закончится, когда закончится последний
Идея: процесс без зависимостей стартует в 0. Процесс с зависимостями стартует в момент, когда закончился самый поздний из тех, кого он ждёт. Общее время — максимум по всем процессам.
Частая путаница: "минимальное время при достаточном числе процессоров" — это длина самой длинной цепочки зависимостей по времени (критический путь), а не сумма всех длительностей. Параллельные ветки идут одновременно, поэтому складываются только те процессы, что стоят друг за другом по зависимостям.