Задание 22 ЕГЭ: параллельные процессы — таблица и решение на Python

Что требуется в задаче на процессы

В таблице даны номера процессов, их длительности и зависимости: какие процессы должны закончиться до запуска следующего. Например, запись «1, 2» у процесса 4 означает: он ждёт и первый, и второй. Ноль в нашем столбце зависимостей означает отсутствие предшественников, а не отдельный процесс №0.

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

Начало отсчёта — момент t = 0. Длительности заданы в миллисекундах. В задачах с неизвестной длительностью, разрешённой задержкой старта или вопросом о числе одновременно работающих процессов потребуется дополнительный анализ условия.

Формула: максимум, затем своя длительность

Для независимого процесса старт равен 0. Для зависимого — моменту, когда закончит самый поздний предшественник:

Старт = max(финиши предшественников)
Финиш = старт + длительность

Если процесс ждёт два других с финишами 4 и 7 мс, раньше 7 мс он не начнётся. Их время не складывают: оба могли выполняться одновременно. При собственной длительности 3 мс финиш равен 7 + 3 = 10 мс.

Когда финиши всех процессов найдены, ответ — самый большой финиш. Последний номер в таблице не обязательно завершится последним.

Пример из семи процессов: считаем вручную

1. Процессы 1 и 2 независимы: стартуют в 0, заканчиваются в 4 и 7.
2. Процесс 3 ждёт первый: старт 4, финиш 4 + 6 = 10.
3. Процесс 4 ждёт первый и второй: старт max(4, 7) = 7, финиш 10.
4. Процесс 5 ждёт второй: 7 + 5 = 12.
5. Процесс 6 ждёт третий и четвёртый: max(10, 10) + 2 = 12.
6. Процесс 7 ждёт пятый и шестой: max(12, 12) + 4 = 16.

Вся работа закончится через 16 мс. Сумма длительностей равна 31 мс, но она описывала бы выполнение всех процессов строго по одному. У нас часть работы идёт параллельно.

Временная шкала и ловушка «плюс один»

На этой шкале процесс 4 работает в интервале [7; 10): момент 7 входит, момент 10 — уже его завершение. Продолжительность равна 10 − 7 = 3 мс. Для такой записи процесс работает в момент t, если start ≤ t < finish.

Если условие нумерует миллисекунды с 1, тот же процесс занимает 8-ю, 9-ю и 10-ю миллисекунды. Тогда формулы для номеров тактов другие: start = 1 + max(finish предков), finish = start + duration − 1. Независимый процесс начинает с 1-й мс, а активность проверяют как start ≤ t ≤ finish.

Выберите одну систему отсчёта и не смешивайте их. Общее время нашего примера в обоих случаях — 16 мс. Различаются обозначения начала и правила включения границ.

Решение на Python и файл для скачивания

Скачать CSV с семью процессами · Скачать программу Python.

Сохраните оба файла в одной папке. Программа должна иметь расширение .py; если браузер сохранил .py.txt, уберите последнее .txt. В CSV столбцы разделены точкой с запятой, несколько предшественников — запятой. Это собственный учебный файл, не официальное приложение к варианту ЕГЭ.

import csv
from functools import lru_cache
from pathlib import Path

# CSV должен лежать рядом с этим файлом программы.
path = Path(__file__).with_name("learn-ege-22-processes.csv")
processes = {}
with path.open(encoding="utf-8-sig", newline="") as f:
    for row in csv.DictReader(f, delimiter=";"):
        number = int(row["id"])
        duration = int(row["duration"])
        parents = [int(x) for x in row["depends"].split(",")
                   if int(x) != 0]
        processes[number] = (duration, parents)

@lru_cache(maxsize=None)
def finish(number):
    duration, parents = processes[number]
    start = max((finish(p) for p in parents), default=0)
    return start + duration

for number in sorted(processes):
    duration, _ = processes[number]
    end = finish(number)
    print(number, end - duration, end)

print("Общее время:", max(finish(p) for p in processes))

После запуска появятся столбцы «номер, старт, финиш» с числами из таблицы и строка «Общее время: 16». Функция finish сначала находит результаты предшественников. default=0 нужен для независимого процесса; lru_cache сохраняет уже вычисленные результаты.

Этот код рассчитан на корректный файл без циклических зависимостей, с существующими номерами предшественников и положительными длительностями. Для очень длинных цепочек удобнее вычислять финиши последовательно в порядке зависимостей: кеш не снимает ограничение глубины рекурсии.

Если исходник в Excel, сначала экспортируйте данные в CSV с нужными разделителями и заголовками либо адаптируйте чтение. Файл .xlsx нельзя просто переименовать в .csv. Описание чтения CSV и кеширования — в документации Python.

Что изменится, если ускорить или замедлить процесс

Уменьшим длительность процесса 1 с 4 до 2 мс. Процесс 3 теперь завершится в 8. Но процесс 4 по-прежнему ждёт второй до 7 и заканчивается в 10. Поэтому процесс 6 заканчивается в 12, а седьмой — в 16. Ускорили один процесс, но общее время не изменилось.

Вернём исходные данные и увеличим длительность процесса 4 с 3 до 10 мс. Он закончится в 7 + 10 = 17. Шестой — в max(10, 17) + 2 = 19, седьмой — в max(12, 19) + 4 = 23. Изменения распространяются по цепочке зависимостей.

Для проверки исправьте соответствующее число в CSV и запустите программу заново. Меняйте только одно условие за раз. Если изменяете словарь внутри уже запущенной программы, перед новым расчётом вызовите finish.cache_clear(), иначе кеш сохранит старые результаты.

Как перейти к экзаменационной практике

1. Прочитайте, что именно спрашивают: общий срок, момент запуска, число работающих процессов или неизвестное время.
2. Уточните модель: все ранние старты или разрешены задержки; ограничены ли ресурсы.
3. Выпишите зависимости и выберите систему отсчёта времени.
4. Для базовой модели посчитайте финиши через максимум предшественников и свою длительность.
5. Проверьте итог вручную хотя бы на одной ветке; затем запустите код.

В самопроверке ниже шесть заданий. Первые два используют маленький независимый пример, остальные — таблицу из семи процессов. После них откройте задания 22 ЕГЭ. Если теряетесь в вызовах функции, сначала пригодится разбор рекурсии.

Проверьте себя

Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.