Задание 22: анализ параллельных процессов

Считаем минимальное время выполнения набора процессов, часть из которых зависит от других, через «время готовности» каждого процесса.

Процесс B зависит от процесса A, если для старта B нужны результаты A; тогда B начинается не раньше, чем закончится A.

Что проверяет задание 22

Задание 22 — повышенный уровень, 1 балл. Дана таблица процессов: идентификатор, время выполнения и список процессов, от которых данный зависит. Независимые процессы могут выполняться параллельно, зависимые — только после своих «предков». Спрашивают, как правило, минимальное время выполнения всей совокупности (момент, когда закончится последний процесс) или сколько процессов могут идти одновременно.

Теория: время готовности и критический путь

Для каждого процесса введём время окончания finish(p). Процесс не может стартовать раньше, чем закончатся все, от кого он зависит. Значит:

finish(p) = max(finish(d) для всех зависимостей d) + время(p)
Если зависимостей нет, старт = 0, finish(p) = время(p).

Минимальное время выполнения всех процессов — это максимум из finish(p) по всем процессам. Эта величина называется длиной критического пути: самой длинной цепочки зависимых процессов.

Метод решения

1. Запишите процессы как словарь: id → (время, список зависимостей).
2. Рекурсивно (с мемоизацией) считайте finish(p).
3. Ответ на «минимальное время всех» — максимум finish по процессам.

Рекурсия безопасна, потому что зависимости образуют ациклический граф (процесс не зависит от себя ни прямо, ни через цепочку).

Решение на Python

from functools import lru_cache

# id: (время выполнения, [от кого зависит])
proc = {
    1: (4, []),
    2: (3, [1]),
    3: (5, [1]),
    4: (2, [2, 3]),
    5: (6, []),
    6: (1, [4, 5]),
}

@lru_cache(maxsize=None)
def finish(pid):
    t, deps = proc[pid][0], tuple(proc[pid][1])
    start = max((finish(d) for d in deps), default=0)  # ждём всех предков
    return start + t

total = max(finish(p) for p in proc)
print("Время окончания каждого:", {p: finish(p) for p in proc})
print("Минимальное время выполнения всех:", total)

Вывод:

Время окончания каждого: {1: 4, 2: 7, 3: 9, 4: 11, 5: 6, 6: 12}
Минимальное время выполнения всех: 12

Разберём: процесс 1 (4 мс) стартует сразу, заканчивается в 4. Процессы 2 и 3 зависят от 1 — стартуют в 4, заканчиваются в 7 и 9. Процесс 4 зависит от 2 и 3 — ждёт обоих, стартует в 9 (максимум), заканчивается в 11. Процесс 5 независим — заканчивается в 6. Процесс 6 ждёт 4 и 5 — стартует в 11, заканчивается в 12. Критический путь: 1 → 3 → 4 → 6 длиной 4+5+2+1 = 12.

Диаграмма Ганта

Те же расчёты можно изобразить диаграммой Ганта — каждый процесс рисуют отрезком на оси времени от старта до finish. Параллельные процессы идут на разных строках одновременно. Длина всей диаграммы и есть минимальное время.

время:  0    2    4    6    8    10   12
P1:     [==4==]
P2:           [=3=]
P3:           [==5==]
P5:     [===6====]
P4:                  [2]
P6:                     [1]

Сколько процессов идут одновременно

Иногда спрашивают максимальное число одновременно выполняемых процессов. Тогда для каждого процесса считают интервал [start, finish) и ищут момент, покрытый наибольшим числом интервалов. Удобный приём — «события»: на старте процесса счётчик активных +1, на финише −1; идём по времени и следим за максимумом.

from functools import lru_cache

proc = {
    1: (4, []),  2: (3, [1]), 3: (5, [1]),
    4: (2, [2, 3]), 5: (6, []), 6: (1, [4, 5]),
}

@lru_cache(maxsize=None)
def finish(pid):
    t, deps = proc[pid][0], tuple(proc[pid][1])
    return max((finish(d) for d in deps), default=0) + t

# интервал каждого процесса: [start, finish)
events = []
for p in proc:
    f = finish(p)
    start = f - proc[p][0]
    events.append((start, +1))   # процесс начался
    events.append((f, -1))       # процесс завершился

events.sort()
active = best = 0
for _, delta in events:
    active += delta
    best = max(best, active)
print("Макс. одновременно активных процессов:", best)

Вывод:

Макс. одновременно активных процессов: 3

Сортируя события по времени и накапливая счётчик активных, мы находим пиковую нагрузку. Тот же приём «развёртки по событиям» решает задачи про одновременные брони, звонки, посетителей — это полезный универсальный шаблон.

Типичные ошибки

• Берут сумму вместо максимума по зависимостям. Зависимые предки идут параллельно, поэтому ждём самого позднего, а не их сумму.
• Складывают время всех процессов. Это даёт последовательное выполнение; нужен критический путь (максимум finish).
• Путают «зависит от» и «нужен для». В таблице третий столбец — от кого зависит данный процесс.
• Не учитывают независимые процессы. Они тоже влияют на ответ, если их время больше критического пути зависимых.

Итог

• finish(p) = max(finish предков) + время(p); без зависимостей старт в 0.
• Минимальное время всех = максимум finish по процессам = длина критического пути.
• Зависимые предки идут параллельно → берём максимум их окончаний, а не сумму.