Моделирование и обработка данных · Электронные таблицы
Задание 22 ЕГЭ по информатике: параллельные процессы и зависимости — разбор и примеры
В задании 22 дан файл-таблица с описанием вычислительных процессов: у каждого процесса есть номер (ID), время выполнения и список процессов, которые должны завершиться до его начала. Процессы могут выполняться параллельно, количество одновременно работающих процессов не ограничено, и каждый процесс стартует сразу, как только завершились все процессы, от которых он зависит. Нужно найти минимальное время завершения всех процессов или ответить на связанный вопрос. Задание решается и в электронной таблице, и программой.
Что проверяет задание
- умение моделировать процесс по табличным данным;
- понимание зависимостей: процесс B, зависящий от A и C, начинается в момент, когда закончился последний из них;
- навык считать по формуле «время окончания = собственное время + максимум времён окончания предшественников»;
- умение обрабатывать файл в Excel или на Python без ошибок переноса.
Типичные формулировки
- «Определите минимальное время, через которое завершится выполнение всех процессов» — основной вариант.
- «Сколько процессов выполнялось в момент времени t?» — нужно знать начало и конец каждого процесса.
- «На какое наибольшее время можно задержать начало процесса X, чтобы общее время выполнения не увеличилось?» — вопрос о резерве процесса.
- «Какое максимальное количество процессов выполнялось одновременно?»
Зависимости в файле обычно записаны в одной ячейке через точку с запятой, а у независимых процессов там стоит 0.
Пошаговый метод
- Для каждого процесса вычислите время окончания. Если зависимостей нет — окончание равно времени выполнения. Иначе окончание = время выполнения + максимум окончаний процессов из списка зависимостей.
- Считайте в порядке зависимостей. В файле процессы обычно упорядочены так, что предшественники стоят выше; если это не так, используйте рекурсию с запоминанием.
- Общее время — максимум окончаний по всем процессам (не окончание последнего в таблице!).
- Начало процесса = окончание минус время выполнения. Процесс работает в момент t, если начало ≤ t < окончание.
- Резерв процесса = позднее допустимое окончание минус раннее окончание. Позднее окончание считается «с конца»: для последних процессов это общее время, для остальных — минимум по зависящим от него процессам значения «позднее окончание минус время выполнения».
Разбор примера
Дана таблица процессов (время в миллисекундах; в столбце зависимостей номера через точку с запятой, 0 — зависимостей нет).
| ID | Время, мс | Зависит от |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 5 | 1 |
| 4 | 2 | 1; 2 |
| 5 | 6 | 2 |
| 6 | 3 | 3; 4 |
| 7 | 4 | 5 |
| 8 | 2 | 6; 7 |
Вопрос 1. Минимальное время выполнения всех процессов.
Считаем окончания по порядку:
- процесс 1: 4; процесс 2: 3;
- процесс 3: 5 + 4 = 9; процесс 4: 2 + max(4, 3) = 6; процесс 5: 6 + 3 = 9;
- процесс 6: 3 + max(9, 6) = 12; процесс 7: 4 + 9 = 13;
- процесс 8: 2 + max(12, 13) = 15.
Ответ: 15 мс. Цепочка 2 → 5 → 7 → 8 (3 + 6 + 4 + 2 = 15) называется критическим путём: любая задержка на ней увеличивает общее время.
Вопрос 2. Сколько процессов выполнялось в момент t = 8? Начала и окончания: процесс 3 — с 4 до 9, процесс 5 — с 3 до 9, процесс 6 начинается только в 9, процесс 4 закончился в 6. В момент 8 работают процессы 3 и 5. Ответ: 2.
Вопрос 3. На сколько можно задержать процесс 4? Процесс 8 должен закончиться к 15, значит, начаться не позже 13; процесс 6 должен закончиться к 13 и начаться не позже 10; процесс 4 должен закончиться к 10. Раннее окончание процесса 4 — 6, поэтому резерв равен 10 − 6 = 4 мс.
Решение в электронной таблице
Добавьте столбец «Окончание». Для строки без зависимостей формула равна времени, для остальных — время плюс МАКС от окончаний нужных строк. Если зависимостей много, удобно сначала разнести их по отдельным столбцам («Данные → Текст по столбцам» с разделителем «;»), а потом использовать ВПР или ИНДЕКС для поиска окончания по номеру. Общее время — МАКС по столбцу окончаний.
Код на Python
Если таблицу сохранить как текстовый файл (столбцы через табуляцию), решение занимает несколько строк. Рекурсия с запоминанием не зависит от порядка строк в файле.
from functools import lru_cache
time, deps = {}, {}
for line in open('22.txt', encoding='utf-8'):
pid, t, d = line.strip().split('\t')
time[int(pid)] = int(t)
deps[int(pid)] = [int(x) for x in d.split(';') if int(x) != 0]
@lru_cache(None)
def finish(p):
return time[p] + max((finish(d) for d in deps[p]), default=0)
total = max(finish(p) for p in time)
print(total) # 15
t = 8
print(sum(finish(p) - time[p] <= t < finish(p) for p in time)) # 2
@lru_cache(None)
def latest(p):
after = [q for q in time if p in deps[q]]
return min((latest(q) - time[q] for q in after), default=total)
print(latest(4) - finish(4)) # 4Максимум одновременно работающих процессов
Если спрашивают, какое наибольшее число процессов выполнялось одновременно, достаточно проверить моменты начала процессов: число работающих процессов может вырасти только в момент, когда какой-то процесс стартует. Для каждого начала посчитайте, сколько процессов работает в этот момент, и возьмите максимум. В нашем примере в момент 0 работают процессы 1 и 2, в момент 4 — процессы 3, 4 и 5, в момент 9 — процессы 6 и 7. Наибольшее значение — 3. В Python это одна строка: перебрать все начала и для каждого применить ту же проверку «начало ≤ t < окончание», что и в вопросе 2.
Частые ошибки
- Складывают времена всех предшественников вместо того, чтобы брать максимум: параллельные процессы идут одновременно.
- Берут окончание последней строки таблицы как ответ. Последняя строка не обязательно завершается последней.
- Неверно считают «в момент t». Процесс, закончившийся ровно в момент t, уже не выполняется, а начавшийся в момент t — выполняется; уточняйте договорённость в условии.
- Теряют зависимость при разборе ячейки. Пробелы после точки с запятой и значение 0 нужно обработать аккуратно.
- Путают резерв процесса и резерв всей цепочки. Задержка процесса может «съесть» резерв следующих процессов — считайте позднее окончание с конца.
Потренируйтесь
Решите задания № 22 в банке двумя способами — в таблице и на Python — и сравните ответы. Похожие приёмы работы с таблицами разобраны в статье «Электронные таблицы: формулы и рабочие шаблоны». Следующее по порядку — задание 23: анализ графов.