Диаграмма Ганта и планирование — Alterna

Диаграмма Ганта — это визуальный способ показать, какой процессор что делает в каждый момент времени.

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

ФГОС · углублённый ЕГЭ · № 22

Что такое диаграмма Ганта?

Визуализация расписания выполнения задач на процессорах

ЕГЭ · № 22

Определение

Диаграмма Ганта — это горизонтальная временна́я шкала, где каждая строка представляет один процессор (или ресурс), а цветные блоки показывают, какая задача выполняется в каждый момент времени.

Простой пример

Допустим, есть 3 независимых процесса: A = 5 с, B = 3 с, C = 4 с, и 2 процессора.

Вариант 1: P1 = {A(5), C(4)} = 9 с, P2 = {B(3)} = 3 с. Общее время = 9 с.

Вариант 2: P1 = {A(5)} = 5 с, P2 = {B(3), C(4)} = 7 с. Общее время = 7 с.

Вариант 3: P1 = {A(5), B(3)} = 8 с, P2 = {C(4)} = 4 с. Общее время = 8 с.

Правило Оптимальное расписание минимизирует максимальное время загрузки любого процессора (makespan).

Нижняя оценка (lower bound)

Минимально возможное время не может быть меньше:

⌈Сумма всех времён / N⌉ — если бы загрузка была идеально равномерной
max(время одного процесса) — самый длинный процесс нельзя разделить

В нашем примере: ⌈12/2⌉ = 6, max = 5. Нижняя оценка = max(6, 5) = 6. Но достичь 6 не удалось — лучший вариант = 7.

Алгоритм решения 1. Посчитайте сумму всех времён и нижнюю оценку.
2. Попробуйте распределить задачи так, чтобы загрузка была максимально равномерной.
3. Начинайте с самых длинных процессов — их сложнее «пристроить».
4. Проверьте: если makespan = нижней оценке, это точно оптимум.

Жадный алгоритм (LPT — Longest Processing Time first)

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

Рис. 1. Диаграмма Ганта: оптимальное расписание для A(5), B(3), C(4) на 2 процессорах

Конвейерная обработка

Как ускорить обработку, разбив задачу на стадии

ЕГЭ · № 22

Идея конвейера

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

Аналогия: конвейер на заводе. Пока одна машина красится, другая собирается, третьая проходит контроль качества.

Ключевая формула

Формула конвейера T = Σtᵢ + (n − 1) · max(tᵢ)

Где:
Σtᵢ — сумма времён всех стадий (время прохождения первой команды)
max(tᵢ) — время самой медленной стадии («узкое место»)
n — количество команд

Почему именно так?

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

Пример

Конвейер из 3 стадий: 2 нс, 4 нс, 3 нс. Обработать 8 команд.

Σtᵢ = 2 + 4 + 3 = 9 нс (первая команда)

max(tᵢ) = 4 нс (стадия 2 — узкое место)

Ещё 7 команд: 7 × 4 = 28 нс

Итого: 9 + 28 = 37 нс

Сравнение с последовательным выполнением Без конвейера: 8 команд × (2+4+3) = 8 × 9 = 72 нс.
С конвейером: 37 нс. Ускорение: 72/37 ≈ 1.95 раза.

Чем больше команд, тем ближе ускорение к числу стадий (но никогда не превышает его).

Частный случай: все стадии одинаковые

Если все k стадий длятся t нс, формула упрощается:

T = (k + n − 1) · t

Пример: 5 стадий по 1 нс, 100 команд → T = (5 + 100 − 1) × 1 = 104 нс.

Обратная задача «Сколько команд обработается за T нс?» — выразите n из формулы:
n = (T − Σtᵢ) / max(tᵢ) + 1 (округлить вниз)

Зависимости между задачами

Когда задачи не могут выполняться в произвольном порядке

ЕГЭ · № 22

Граф зависимостей (DAG)

Часто задачи связаны: задача B не может начаться, пока не завершится задача A. Это описывается ориентированным ациклическим графом (DAG).

A → B означает: B зависит от A, B стартует не раньше, чем A завершится.

Критический путь

Критический путь — самый длинный путь в графе от начала до конца. Он определяет минимальное время выполнения всего проекта, даже если у нас бесконечно много процессоров.

Алгоритм нахождения критического пути 1. Для каждой задачи вычислите самое раннее время старта:
start(X) = max(finish(Y) для всех Y → X)
finish(X) = start(X) + время(X)
2. Для начальных задач (без зависимостей): start = 0.
3. Ответ = max(finish(X) для всех X).

Пример

Задачи: A(3), B(2), C(4), D(5), E(2). Зависимости: A→C, B→D, C→E, D→E.

Рис. 2. Граф зависимостей: A→C→E и B→D→E

Решение:

A: start=0, finish=3
B: start=0, finish=2
C: start=3 (ждёт A), finish=3+4=7
D: start=2 (ждёт B), finish=2+5=7
E: start=max(7,7)=7 (ждёт C и D), finish=7+2=9

Критический путь: A→C→E = 3+4+2 = 9 (или B→D→E = 2+5+2 = 9). Оба пути одинаковой длины!

Типичная ошибка Нельзя просто сложить все времена! Задачи на разных ветках выполняются параллельно. Сумма всех времён = 3+2+4+5+2 = 16, но ответ = 9.

Закон Амдала

Почему бесконечное число ядер не даёт бесконечного ускорения

ЕГЭ · № 22

Формула

Закон Амдала S = 1 / ((1 − p) + p / N)

p — доля параллельного кода (от 0 до 1)
N — число процессоров
S — ускорение (во сколько раз быстрее)

Смысл

Часть программы (1 − p) — последовательная, её нельзя ускорить никаким числом ядер. Она всегда выполняется за своё время. Параллельная часть p ускоряется в N раз.

Примеры

p (паралл.)	N ядер	Ускорение S	Комментарий
80%	4	2.5	Из 4 ядер выжали 2.5×
90%	10	5.3	10 ядер → только 5.3×
99%	100	≈50	100 ядер → только 50×
50%	1000	≈2	1000 ядер, а ускорение всего 2×

Теоретический предел

При N → ∞: S_max = 1 / (1 − p)

Если 90% кода параллельно, максимальное ускорение = 1/0.1 = 10 раз, даже с миллионом ядер.

Обратная задача: сколько ядер нужно? Дано: ускорение S, доля p. Найти N.
N = p / (1/S − (1−p))

Пример: p=0.9, S=4. N = 0.9 / (0.25 − 0.1) = 0.9/0.15 = 6 ядер.

Стратегия решения ЕГЭ №22

Четыре типа задач и алгоритм для каждого

Тип 1: Распределение независимых процессов

Алгоритм 1. Найдите сумму всех времён и нижнюю оценку ⌈сумма/N⌉.
2. Отсортируйте процессы по убыванию.
3. Распределяйте, начиная с самых длинных, на наименее загруженный процессор.
4. Ответ = makespan (максимальная загрузка).

Тип 2: Конвейер

Алгоритм 1. Найдите Σtᵢ (сумма стадий) и max(tᵢ) (узкое место).
2. Подставьте в формулу: T = Σtᵢ + (n−1)·max(tᵢ).
3. Для обратной задачи: n = ⌊(T − Σtᵢ) / max(tᵢ)⌋ + 1.

Тип 3: Зависимости (критический путь)

Алгоритм 1. Нарисуйте граф зависимостей.
2. Для каждой задачи: start = max(finish всех предшественников), finish = start + время.
3. Начальные задачи: start = 0.
4. Ответ = max(finish всех задач).

Тип 4: Закон Амдала

Алгоритм 1. Определите p (доля параллельного кода) и N (число ядер).
2. Подставьте: S = 1 / ((1−p) + p/N).
3. Для предела: S_max = 1 / (1−p).
4. Для обратной задачи: N = p / (1/S − (1−p)).

Ловушки ЕГЭ • «Независимые процессы» ≠ «зависимые» — читайте условие внимательно.
• В конвейере: Σtᵢ — это время первой команды, а не одной стадии.
• В зависимостях: нельзя складывать все времена — параллельные ветки не суммируются.
• В Амдале: p — это доля параллельного кода, а не последовательного.

📊

Симулятор диаграммы Ганта

введите процессы и число процессоров

интерактив

Введите времена процессов через запятую и укажите число процессоров. Симулятор построит оптимальную диаграмму Ганта.

Процессы (через запятую):

Процессоров:

⚙️

Калькулятор конвейера

формула T = Σtᵢ + (n−1)·max(tᵢ)

интерактив

Введите времена стадий и количество команд — калькулятор покажет пошаговое решение.

Стадии конвейера (нс, через запятую):

Количество команд:

Банк задач ЕГЭ №22

50 задач · 10 случайных · перемешать для новой подборки

ЕГЭ · № 22

Не удалось загрузить задачи. Убедитесь, что файл gantt-tasks.json доступен.

Решено: 0 / 10