Многопроцессорные системы и параллельные вычисления (задание 22 ЕГЭ)

Коротко о главном

Задание 22 — это задачи на параллельное выполнение работ несколькими процессорами (обычно 2 или 3). Даны работы с известным временем выполнения и зависимостями («работу B нельзя начать, пока не закончена работа A»). Нужно найти минимальное время, за которое все работы будут выполнены, распределив их между процессорами оптимально.

Главная идея: процессоры работают одновременно, но конкретная работа не может начаться раньше, чем закончатся все работы, от которых она зависит, и раньше, чем освободится процессор.

Определения и формулы/правила

Понятие	Описание
Процессор	Устройство, выполняющее ровно одну работу в момент времени
Работа (задача)	Имеет длительность $t_i$ и может иметь зависимости от других работ
Зависимость	Работа $B$ может начаться только после завершения всех работ, от которых она зависит
Время начала работы	$start_i = \max(\text{время освобождения процессора}, \max_{j \to i} finish_j)$
Время окончания работы	$finish_i = start_i + t_i$
Критический путь	Самая длинная цепочка зависимых работ; определяет нижнюю границу общего времени
Общее время выполнения	$T = \max_i(finish_i)$ по всем работам

Правило нижней оценки: $$T \ge \max\left(\dfrac{\sum t_i}{n_{проц}},\ L_{крит.путь}\right)$$

где $n_{проц}$ — число процессоров, $L_{крит.путь}$ — суммарная длительность самой длинной цепочки зависимостей.

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

Как применять (примеры)

Пример 1. Два процессора. Работы: A (3 мин, без зависимостей), B (2 мин, зависит от A), C (4 мин, без зависимостей).

• Процессор 1: A (0–3), затем B (3–5).
• Процессор 2: C (0–4), простаивает до конца.

Общее время: $T = \max(5, 4) = 5$ минут.

Пример 2. Три процессора, работы: A(2), B(2), C(2), D(3, зависит от A и B).

• Процессор 1: A (0–2).
• Процессор 2: B (0–2).
• Процессор 3: C (0–2).
• D может начаться в момент $\max(2,2)=2$, выполняется на любом свободном процессоре: (2–5).

Общее время: $T = 5$ минут.

Пример 3. Один процессор, работы A(1), B(2) зависит от A, C(1) зависит от B.

Цепочка строго последовательна: $T = 1+2+1 = 4$ минуты — процессор простаивать не может, так как всё зависимо.

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

• Забывают, что работа может начаться только после всех зависимостей, а не после первой из них.
• Считают, что $T = \dfrac{\sum t_i}{n}$ всегда точно — но это лишь нижняя оценка при отсутствии зависимостей; с зависимостями критический путь может быть больше.
• Неправильно распределяют работы между процессорами: назначают длинную зависимую цепочку последней, из-за чего процессоры простаивают.
• Не учитывают, что процессор может простаивать, ожидая готовности следующей подходящей работы — это нормально и не ошибка.
• Путают понятия «начало работы» и «начало доступности» (работа доступна, когда выполнены зависимости, но реально начинается только когда освободится процессор).

Где встречается на экзамене

Это классическое задание №22 ЕГЭ по информатике. Обычно даётся таблица или список работ с временем выполнения и зависимостями, указано число процессоров (2 или 3), и требуется найти минимальное суммарное время выполнения всех работ. Иногда просят построить расписание (порядок работ на каждом процессоре) или указать, при каком минимальном числе процессоров время не сократится дальше.