Задание №22. Зависимости процессов
Расчёт времени начала и окончания процессов, подсчёт завершений и поиск интервала одновременной работы.
В таблице перечислены вычислительные процессы: сколько времени длится каждый и результаты каких процессов нужны для его запуска. Независимые работы могут идти параллельно, а зависимая работа ждёт завершения всех своих предшественников. По этой информации требуется определить срок выполнения, число завершённых или работающих процессов либо длительность их одновременной работы. Основа решения — расписание с моментами начала и окончания; способ получить ответ зависит от последнего вопроса условия.
Как читать зависимости
Процесс — работа с заданной продолжительностью. После запуска он выполняется непрерывно: приостановка не допускается. Если процессу нужны результаты другого, второй является его предшественником. Зависимость 1\to3 означает, что процесс 3 может начаться только после окончания процесса 1.
В столбце зависимостей запись 1;2 означает ожидание обоих процессов: 1 и 2. Число 0 обозначает отсутствие зависимостей, а не отдельный процесс с номером 0. Независимые процессы не обязаны ждать друг друга. Ограничения на число одновременно работающих процессоров в рассматриваемых условиях нет.
Нулевой момент — начало отсчёта, перед первой миллисекундой. Для процесса с номером i обозначим длительность d_i, момент начала S_i, момент окончания F_i. Если работа начинается в момент 4 и длится 8 мс, то заканчивается в момент 4+8=12.
Расписание с самым ранним запуском
Когда каждый процесс запускается при первой возможности, независимые работы начинаются в момент 0. Зависимая работа ждёт того предшественника, который заканчивается последним. Поэтому её начало равно максимуму моментов окончания предшественников, а не сумме их длительностей:
S_i=\max_{j\in P_i}F_j, F_i=S_i+d_i. Здесь P_i — список предшественников процесса i. Для пустого списка принимается S_i=0.
Это правило применяется к строке только после расчёта всех её предшественников. В исходной таблице они не обязательно расположены выше. Если нужный момент окончания ещё неизвестен, сначала рассчитывается соответствующий процесс и его зависимости.
Полный пример: завершение всех процессов
В задаче о минимальном времени выполнения всей совокупности ↗ используется файл 2_22.xlsx. Ниже приведены все 16 строк этого вложения. Это полные входные данные задачи, а не типовой пример из текста условия.
| ID | Длительность, мс | Предшественники |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 2 | 0 |
| 3 | 8 | 1; 2 |
| 4 | 5 | 0 |
| 5 | 7 | 3; 4 |
| 6 | 9 | 3 |
| 7 | 10 | 5 |
| 8 | 5 | 5 |
| 9 | 10 | 8 |
| 10 | 8 | 7 |
| 11 | 7 | 6; 7 |
| 12 | 6 | 11 |
| 13 | 9 | 11 |
| 14 | 4 | 11 |
| 15 | 6 | 12; 13; 14 |
| 16 | 9 | 10; 9 |
От независимых работ к общему окончанию
Процессы 1, 2 и 4 независимы. Все три запускаются в момент 0 и заканчиваются соответственно в моменты 4, 2 и 5. Процесс 3 ждёт первые два: к моменту 2 готов только один результат, к моменту 4 — оба. Значит, S_3=\max(4,2)=4, а F_3=4+8=12.
Процесс 5 зависит от 3 и 4. Их окончания — 12 и 5, поэтому S_5=\max(12,5)=12. После ожидания нужны ещё 7 мс. Процесс 6 тоже может стартовать в 12, поскольку зависит только от 3. Запуски 5 и 6 не мешают друг другу. Дальше применяется то же правило; в таблице показаны все вычисления, включая эти первые шаги.
| ID | S_i, мс | F_i, мс |
|---|---|---|
| 1 | 0 | 0+4=4 |
| 2 | 0 | 0+2=2 |
| 3 | 4 | 4+8=12 |
| 4 | 0 | 0+5=5 |
| 5 | 12 | 12+7=19 |
| 6 | 12 | 12+9=21 |
| 7 | 19 | 19+10=29 |
| 8 | 19 | 19+5=24 |
| 9 | 24 | 24+10=34 |
| 10 | 29 | 29+8=37 |
| 11 | 29 | 29+7=36 |
| 12 | 36 | 36+6=42 |
| 13 | 36 | 36+9=45 |
| 14 | 36 | 36+4=40 |
| 15 | 45 | 45+6=51 |
| 16 | 37 | 37+9=46 |
Например, процесс 11 ждёт 6 и 7, завершившиеся в 21 и 29. Поэтому S_{11}=\max(21,29)=29, а окончание наступает в 36. В этот момент одновременно становятся доступны 12, 13 и 14; их окончания равны 42, 45 и 40. Процессу 15 нужны все три результата, поэтому S_{15}=\max(42,45,40)=45. Он заканчивается в 51.
Процесс 16 ждёт 10 и 9, завершившиеся в 37 и 34. Поэтому S_{16}=\max(37,34)=37, а F_{16}=37+9=46.
Общая работа закончена, когда завершён каждый процесс. Значит, нужен наибольший момент окончания во всём столбце: T=\max_i F_i=51 мс. Последняя строка даёт 46 мс, но к этому моменту процесс 15 ещё работает. Ответ — 51.
Почему быстрее невозможно
Цепочка зависимостей 1\to3\to5\to7\to11\to13\to15 требует последовательного выполнения всех входящих в неё работ. Сумма их длительностей равна 4+8+7+10+7+9+6=51 мс. Параллельный запуск других процессов не сокращает эту цепочку.
Она задаёт критический путь: менее 51 мс недостаточно. Расписание в таблице достигает 51 мс и соблюдает все зависимости. Совпадение необходимого времени и времени допустимого расписания доказывает минимум.
Другие вопросы к тому же расписанию
В следующих вариантах условие требует запуска каждого процесса в самое раннее допустимое время. Расчёт столбцов S_i и F_i сохраняется, но выбирать максимум всех окончаний уже не всегда нужно.
Когда завершится заданное количество процессов
Если требуется время завершения k процессов, все моменты F_i располагаются по возрастанию и выбирается k-й элемент. Одинаковые значения сохраняются: два процесса, завершившиеся одновременно, дают два завершения.
В задаче о завершении 17 процессов ↗ семнадцатое значение равно 12 мс, хотя вся совокупность заканчивается лишь в 21 мс. Число 17 обозначает количество завершений, а не идентификатор процесса.
Сколько процессов завершится за первые миллисекунды
Для заданного срока t считаются все строки с F_i\le t. Равенство включается: процесс, закончившийся точно в момент t, успел завершиться за отведённое время. В задаче о первых 17 мс ↗ этому условию соответствуют 12 процессов. Момент начала для такого подсчёта не заменяет момент окончания.
Сколько процессов работает на заданной миллисекунде
Номер миллисекунды обозначим k. Миллисекунда с номером 1 занимает время от 0 до 1, с номером 2 — от 1 до 2 и так далее. Процесс с целочисленными моментами начала и окончания занимает миллисекунды с номерами от S_i+1 до F_i включительно. Поэтому проверяется S_i<k\le F_i.
Например, процесс 3 из полного примера работает с момента 4 до момента 12: заняты миллисекунды 5–12, всего 8. На 12-й он ещё выполняется; на 13-й уже нет. В задаче о работе на 16-й миллисекунде ↗ условие S_i<16\le F_i выполняют 7 процессов.
Когда ранний запуск не даёт нужного максимума
Поиск самого длинного интервала одновременной работы — другой вопрос. Если в условии не требуется самый ранний запуск, готовый процесс разрешается начать позже. Его длительность при этом не меняется и прерывать его по-прежнему нельзя. Сдвиги могут совместить работы на более длинном общем отрезке.
В задаче о максимальной продолжительности работы пяти процессов ↗ нет требования раннего запуска. Файл 1_22.xlsx содержит следующие 14 процессов:
| ID | Длительность, мс | Предшественники |
|---|---|---|
| 101 | 4 | 0 |
| 102 | 3 | 0 |
| 103 | 1 | 101; 102 |
| 104 | 5 | 103 |
| 105 | 7 | 103 |
| 106 | 3 | 104 |
| 107 | 1 | 105; 106 |
| 108 | 2 | 107 |
| 109 | 8 | 0 |
| 110 | 6 | 0 |
| 111 | 16 | 109 |
| 112 | 5 | 110 |
| 113 | 14 | 111; 114 |
| 114 | 14 | 109 |
Допустимые сдвиги и полученный интервал
В первой группе процессы 101 и 102 можно выполнить с момента 0, а затем процесс 103 — с 4 до 5. После него готовы 104 и 105. Вместо немедленного запуска их начало переносится в момент 8, когда завершится независимый процесс 109 и станут доступны 111 и 114. Независимый процесс 110 запускается в момент 5, чтобы его работа и следующая за ней работа 112 перекрывали тот же участок времени.
Полное расписание ниже фиксирует оба сдвига и все последующие запуски. Интервал [S_i,F_i) включает начало и не включает момент окончания: в этот момент процесс уже завершён и его преемник может начать работу.
| ID | S_i, мс | F_i, мс |
|---|---|---|
| 101 | 0 | 4 |
| 102 | 0 | 3 |
| 103 | 4 | 5 |
| 104 | 8 | 13 |
| 105 | 8 | 15 |
| 106 | 13 | 16 |
| 107 | 16 | 17 |
| 108 | 17 | 19 |
| 109 | 0 | 8 |
| 110 | 5 | 11 |
| 111 | 8 | 24 |
| 112 | 11 | 16 |
| 113 | 24 | 38 |
| 114 | 8 | 22 |
Для 104 и 105 ожидание после готовности разрешено: процесс 103 закончен в 5, а их старт равен 8. Процесс 106 начинается в 13 после окончания 104. Процесс 107 ждёт окончания 105 и 106, то есть \max(15,16)=16, а 108 начинается после него в 17. Во второй группе 111 и 114 стартуют после 109 в 8, процесс 112 — после 110 в 11, а 113 — после обоих своих предшественников в \max(24,22)=24. Разность окончания и начала в каждой строке равна исходной длительности. Значит, расписание допустимо.
На отрезке от 8 до 15 состав работающих процессов меняется только в моменты 11 и 13. Между соседними такими моментами он постоянен:
| Интервал, мс | Работающие процессы |
|---|---|
| [8,11) | 104, 105, 110, 111, 114 |
| [11,13) | 104, 105, 111, 112, 114 |
| [13,15) | 105, 106, 111, 112, 114 |
В момент 11 работу 110 сменяет 112, а в момент 13 работу 104 сменяет 106. Число работающих процессов всё время остаётся равным пяти. Непрерывный интервал имеет длину 15-8=7 мс; требование не означает, что все семь миллисекунд должна работать одна и та же пятёрка.
Почему более длинного интервала нет
Данные разделяются на две независимые группы: 101–108 и 109–114. В первой одновременно возможны не более двух работ. До процесса 103 это пара 101 и 102; после него — процесс 105 вместе с 104 или следующим за ним 106. Процессы 107 и 108 идут уже после завершения этих ветвей и не добавляют параллельности.
Во второй группе одновременно возможны не более трёх работ: 111 и 114, а также одна из последовательных работ 110 и 112. Процесс 109 предшествует паре 111 и 114, а 113 следует после обоих, поэтому в эти периоды число работающих в группе не больше двух. Значит, пять процессов в общей совокупности возможны только при двух работах в первой группе и трёх во второй.
Совместная работа начальной пары 101 и 102 длится не более 3 мс — длительности более короткого процесса 102. Поздний участок с двумя работами первой группы требует непрерывной работы 105, длительность которого равна 7 мс. Объединить ранний и поздний участки в одно окно пяти работ нельзя: между ними обязательно выполняется процесс 103, и в первой группе тогда работает только он.
Следовательно, ни один непрерывный интервал работы пяти процессов не длиннее 7 мс. Построенное расписание достигает этой границы, поэтому ответ — 7. Один только ранний запуск здесь дал бы более короткий интервал и не доказал бы максимума.
Минимальный общий срок и ранний старт — разные условия
В задаче об одновременной работе при минимальном общем сроке ↗ и другой задаче с тем же ограничением ↗ требуется сохранить самое раннее завершение всей совокупности. Это не равнозначно требованию немедленно запускать каждую готовую работу: некоторые старты могут сдвигаться, если общий конец не меняется.
Сначала ранним расписанием находится минимальный общий срок T. При подборе сдвигов сохраняются зависимости, длительности и ограничение F_i\le T для всех процессов. Затем определяется максимально возможное число одновременных работ в этих пределах и наибольшая длительность непрерывного интервала с таким числом. Расписание, в котором окно стало длиннее только за счёт более позднего общего окончания, условию не соответствует.
Для выбранной фиксированной группы общая часть её интервалов начинается в самый поздний из стартов и заканчивается в самое раннее из окончаний. Но если условие говорит о количестве процессов, состав группы может меняться, как в примере выше. Тогда время делится по всем моментам запуска и завершения; соседние участки объединяются, пока нужное количество сохраняется без перерыва.
Возможные ловушки
- Сложить длительности предшественников. В примере с двумя зависимостями процесса 3 ↗ работы 1 и 2 идут параллельно. Ожидание длится до момента 4, а не 4+2=6. Для начала берётся максимум их окончаний; минимум, наоборот, запустил бы работу до готовности всех результатов.
- Выполнять строки подряд или брать конец последней. Независимость допускает одновременный запуск, а положение строки не задаёт зависимость. В том же полном примере последняя работа заканчивается в 46, но общий срок равен 51. Для общего окончания сравниваются все значения F_i.
- Подменить вопрос условием о всей совокупности. В задаче о 17 завершениях ↗ нужны семнадцать окончаний, а не процесс с номером 17 и не последний конец. Повторяющиеся моменты в сортировке не удаляются.
- Сместить миллисекунду на единицу. Для 16-й миллисекунды ↗ проверяется S_i<16\le F_i. Работа, стартующая в момент 16, начнёт занимать время только с 17-й миллисекунды. Проверка длительности через F_i-S_i=d_i не требует добавления единицы.
- Запретить сдвиги или зафиксировать состав группы без основания. В задаче об интервале пяти работ ↗ более поздние старты допустимы, а на границе интервалов одна работа сменяет другую. Проверяются зависимости, непрерывность окна и число работ, а не неизменность их идентификаторов.
- Забыть ограничение общего срока. При требовании минимального времени всей совокупности ↗ свободный сдвиг может нарушить условие. После переноса старта проверяются и зависимые работы, и окончание всех процессов не позже найденного T.
Архивные задания №22 с анализом программ, цифр числа и циклов относятся к прежнему формату. Их способ решения не переносится на таблицы зависимостей. Среди рассмотренных здесь вариантов различается именно вопрос к расписанию; этот перечень не объявляет все возможные формулировки номера исчерпанными.