Зависимости процессов и время выполнения
Ожидание предшественников, критический путь и различие между ранним расписанием и допустимым сдвигом работ.
У вычислительных работ есть длительности и зависимости: одни могут выполняться одновременно, другим нужны готовые результаты предшественников. Чтобы определить время выполнения, недостаточно сложить все длительности. Нужно установить, какие работы неизбежно следуют друг за другом, а какие перекрываются во времени. Расписание выражает это через моменты начала и окончания каждого процесса.
Зависимость и параллельность
Процесс — работа, которая после запуска выполняется непрерывно в течение заданного времени. Если процессу 3 нужен результат процесса 1, процесс 3 не может начаться до завершения процесса 1. Эта зависимость изображается стрелкой 1\to3: направление идёт от предшественника к зависимой работе.
Несколько предшественников означают совместное требование. Запись 1;2 разрешает запуск только после завершения и 1, и 2. При этом сами предшественники могут выполняться параллельно. Если зависимостей нет, процесс называется независимым; в таблице это обозначается числом 0.
Параллельность не ограничивается числом строк или порядком их записи. В рассматриваемых задачах нет отдельного ограничения на количество процессоров, поэтому все работы, которым не мешают зависимости, допускают одновременное выполнение. Взаимная цепочка зависимостей с возвратом к исходному процессу сделала бы запуск этих работ невозможным; корректное расписание опирается на зависимости без таких циклов.
Моменты времени и длительности
Для процесса с номером i длительность обозначается d_i, начало — S_i, окончание — F_i. Нулевой момент расположен перед первой миллисекундой. Поскольку процесс не прерывается, F_i=S_i+d_i, или, что то же самое, d_i=F_i-S_i.
Интервал выполнения записывается как [S_i,F_i). Левая граница включена: работа уже началась. Правая исключена: в момент окончания работа уже завершена, и её результат доступен следующему процессу. Так один процесс может закончиться, а зависимый от него начаться в один момент без дополнительной паузы.
Номер миллисекунды — другая величина. При целочисленных началах и длительностях работа с S_i=4 и F_i=12 занимает миллисекунды с 5-й по 12-ю. Их восемь: 12-4=8. Поэтому работа на миллисекунде с номером k определяется условием S_i<k\le F_i, а работа в момент времени t — условием S_i\le t<F_i.
Почему ожидание определяется максимумом
Если предшественники заканчиваются в разные моменты, все результаты становятся доступны после самого позднего окончания. Сумма окончаний не имеет такого смысла: эти моменты отсчитаны от одного начала времени и могут относиться к параллельным работам. Минимум тоже не подходит, поскольку оставляет часть зависимостей незавершённой.
Обозначим список предшественников процесса i через P_i. Самый ранний запуск задаётся формулой S_i=\max_{j\in P_i}F_j. Если список пуст, S_i=0. Затем к моменту старта прибавляется собственная длительность процесса.
Ниже приведены пять строк таблицы с ожиданием двух предшественников ↗. Все работы, необходимые для расчёта этих строк, включены в фрагмент.
| ID | Длительность, мс | Предшественники |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 2 | 0 |
| 3 | 8 | 1; 2 |
| 4 | 5 | 0 |
| 5 | 7 | 3; 4 |
При раннем запуске F_1=4, F_2=2, F_4=5. Процесс 3 ждёт до \max(4,2)=4 и заканчивается в 4+8=12. Процесс 5 ждёт окончания 3 и 4, поэтому S_5=\max(12,5)=12 и F_5=12+7=19. Ожидание более короткой ветви не прибавляется второй раз: оно уже прошло одновременно с длинной.
Критический путь и минимальный общий срок
Зависимости образуют цепочки последовательных работ. Длительности внутри одной цепочки складываются, потому что каждое следующее звено ждёт предыдущее. Критический путь — самая длинная по времени цепочка. Её суммарная длительность даёт нижнюю границу для окончания всей совокупности.
В приведённом фрагменте цепь 1\to3\to5 длится 4+8+7=19 мс. Следовательно, все пять работ невозможно закончить быстрее 19 мс. Раннее расписание заканчивается ровно в 19 и тем самым достигает границы. Для полной таблицы критический путь может продолжаться через другие процессы; фрагмент не определяет общий ответ всей задачи.
Почему ранний запуск даёт минимальный общий срок? Независимые работы нельзя начать раньше нулевого момента. Если все предшественники уже имеют самые ранние возможные окончания, зависимая работа не может начаться раньше их максимума. Повторение этого рассуждения по зависимостям даёт самое раннее окончание каждой работы. Наибольшее из них, T=\max_iF_i, является минимальным сроком всей совокупности.
Порядок вычисления определяется готовностью предшественников, а не величиной ID. Строка с меньшим номером может зависеть от строки с большим. Если нужные окончания ещё не найдены, расчёт сначала переходит к этим зависимостям.
Допустимый сдвиг и резерв времени
Допустимость расписания требует S_i\ge F_j для каждого предшественника j. Равенство самому позднему окончанию задаёт ранний запуск. Строгое превышение означает, что готовая работа некоторое время ждала. Такое ожидание разрешено, если условие не требует начать немедленно.
Требование минимального общего срока допускает ожидание лишь там, где оно не сдвигает окончание всей совокупности. Например, в фрагменте выше процесс 4 длится 5 мс и нужен процессу 5 к моменту 12. Его можно начать в 7 и закончить в 12. Начало процесса 5 и общий срок фрагмента останутся прежними. Эта возможность задержки называется резервом времени.
Для расписания с установленным минимальным сроком T сдвиг проверяется по всей цепочке последователей. Должны сохраниться зависимости и условия F_i\le T для всех работ. Наличие свободного места возле одной строки ещё не доказывает допустимость переноса.
Счёт завершений и одновременная работа
Момент завершения заданного количества процессов находится по упорядоченному списку F_i. Каждая работа учитывается отдельно, даже если несколько заканчиваются одновременно. Число завершённых к сроку t — количество строк, удовлетворяющих F_i\le t. Оба вопроса используют окончания, но выбирают из них разные величины.
Для одновременной работы нужны и начала, и окончания. Если фиксирована группа процессов, её общий интервал начинается в самый поздний старт и заканчивается в самое раннее окончание. Если начало не раньше конца, положительной длительности совместной работы нет.
Когда задано только число работающих процессов, фиксировать состав группы нельзя. В задаче об интервале работы пяти процессов ↗ процесс 110 может закончиться в момент 11, а зависимый от него 112 — начаться в тот же момент. Остальные четыре продолжают работу, поэтому общее число сохраняется. Для подсчёта длительности важен непрерывный участок с нужным числом, а не общая часть интервалов одной неизменной группы.
Число работающих меняется только в моменты запусков и завершений. Между соседними такими событиями оно постоянно. Это позволяет разделить ось времени на участки, посчитать число работ на каждом и объединить соседние подходящие участки. Длина объединённого интервала равна разности его правой и левой границ.
Применение к условию задачи
Как из полной таблицы зависимостей получить минимальный срок и отличить его от времени отдельного завершения? Когда перенос готовой работы увеличивает интервал одновременного выполнения, оставаясь допустимым? В статье «Задание №22. Зависимости процессов» эти вопросы разобраны на двух настоящих входных файлах: с расчётом всех строк и с обоснованием максимального интервала.