Задание 22 ЕГЭ по информатике: многопроцессорная система и процессы

Задание 22 ЕГЭ по информатике проверяет построение математической модели многопроцессорной системы: процессы зависят друг от друга, и нужно найти общее время работы или число процессов, которые выполняются в заданную миллисекунду. Решают его в электронной таблице, где для каждого процесса считают время начала и окончания.

Как решать

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

В электронной таблице добавьте к данным столбец окончаний. Для независимого процесса окончание равно длительности. Для зависимого запишите формулу =МАКС(D2;D3)+B5, где D2 и D3 — окончания предшественников, B5 — длительность самого процесса; ссылки на строки предшественников подставьте вручную. Порядок строк значения не имеет: таблица пересчитывает формулы сама.

Время завершения всей совокупности процессов — наибольшее значение в столбце окончаний. Если спрашивают о конкретной миллисекунде T, учтите нумерацию с единицы: процесс с началом t и длительностью d занимает миллисекунды с t + 1 по t + d. Добавьте столбец начала (окончание минус длительность) и посчитайте процессы, у которых начало меньше T, а окончание не меньше T, функцией СЧЁТЕСЛИМН.

На Python удобно записать процессы словарём «ID — длительность и список предшественников» и вычислять окончание функцией с запоминанием: она сама обойдёт зависимости в нужном порядке.

Примеры с решением

Пример 1

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

ID   Время, мс   Зависит от
1    4           0
2    3           0
3    6           1
4    2           1; 2
5    5           4
6    3           3; 5
7    7           2
8    2           6; 7

Значение 0 означает, что процесс независимый. Определите минимальное время в миллисекундах, через которое завершится выполнение всей совокупности процессов, если все независимые друг от друга процессы могут выполняться параллельно.

Проверка ответа на Python

# ID: (время в мс, список процессов, от которых зависит)
proc = {
    1: (4, []), 2: (3, []), 3: (6, [1]), 4: (2, [1, 2]),
    5: (5, [4]), 6: (3, [3, 5]), 7: (7, [2]), 8: (2, [6, 7]),
}
finish = {}
for pid in sorted(proc):                     # зависимости только от меньших номеров
    dur, deps = proc[pid]
    start = max((finish[d] for d in deps), default=0)
    finish[pid] = start + dur
print(max(finish.values()))

Ответ: 16

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

Пример 2

Задание выполняется с использованием прилагаемого файла. В файле три столбца, разделённых табуляцией: ID процесса, время его выполнения в миллисекундах и ID процессов, от которых он зависит, через точку с запятой; 0 означает, что процесс независимый. Первая строка содержит заголовки. Процессы выполняются по правилам из примера 1.

Определите, сколько процессов выполняется одновременно на 12-й мс, если каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1: процесс длительностью 3 мс, который начинается сразу, занимает 1-ю, 2-ю и 3-ю мс.

Файл данных: 22_ex2.txt — 31 строка, 287 байт. Первые строки файла:

ID	Время (мс)	Зависит от
1	4	0
2	5	0
3	2	0
4	3	0
5	5	0
6	1	1
7	2	4

Проверка ответа на Python

rows = [line.rstrip('\n').split('\t') for line in open('22_ex2.txt', encoding='utf-8')][1:]
proc = {}
for pid, dur, deps in rows:
    proc[int(pid)] = (int(dur), [int(d) for d in deps.split(';') if d != '0'])

finish = {}


def end(pid):
    """Момент окончания процесса при самом раннем запуске (в мс от начала)."""
    if pid not in finish:
        dur, deps = proc[pid]
        finish[pid] = max((end(d) for d in deps), default=0) + dur
    return finish[pid]


T = 12
running = 0
for pid, (dur, deps) in proc.items():
    start = end(pid) - dur                   # процесс занимает миллисекунды start+1 … start+dur
    if start + 1 <= T <= start + dur:
        running += 1
print(running)

Ответ: 5

После расчёта начала и окончания всех 30 процессов на 12-й мс выполняются пять: процесс 16 (с 10-й по 15-ю мс), 17 (с 6-й по 14-ю), 20 (с 10-й по 12-ю), 23 (с 9-й по 14-ю) и 27 (с 12-й по 17-ю). Процесс 20 заканчивается ровно на 12-й мс, а процесс 27 на ней начинается, поэтому оба учитываются.

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

Потренироваться на тренажёре

Частые вопросы

Что значит «самое раннее допустимое время»?

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

Как решить задание 22 в LibreOffice Calc?

Добавьте столбец окончаний и заполните его формулами вида =МАКС(…)+длительность со ссылками на строки предшественников. Затем найдите максимум столбца или посчитайте процессы нужной миллисекунды функцией СЧЁТЕСЛИМН.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 21 и задание 23.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.