Тип 2
В предыдущих статьях мы освоили азы построения диаграммы Ганта и научились справляться с самыми простыми задачами типа 22. Пришло время подняться на новую ступень!
Теперь мы рассмотрим задания второго типа, в которых нам уже придётся строить диаграмму Ганта и передвигать процессы по временной оси для получения требуемого результата.
Ключевая фраза-маркер звучит так: «в течение которого возможно одновременное выполнение процессов». Именно в этих словах скрыта вся суть работы: нужно добиться того, чтобы независимые друг от друга процессы выстраивались параллельно и работали в одно время.
Чаще всего в таких заданиях требуется найти максимальную продолжительность отрезка времени, на протяжении которого одновременно работает заданное количество процессов. Алгоритм решения, обычно, заключается в следующем: перемещаем группы взаимосвязанных процессов так, чтобы на максимально длинном временном интервале работало нужное количество процессов.
Для успешного решения вам необходимо задать себе несколько вопросов:
- Как выделить блоки взаимосвязанных процессов среди всех остальных?
- Сколько максимально процессов может работать одновременно внутри каждого блока?
- Можно ли увеличить количество параллельно работающих процессов в блоках?
- Как долго работает это максимальное количество процессов в каждом блоке?
- Можно ли растянуть это время ещё больше?
Ответы на эти вопросы станут вашими инструментами при анализе диаграммы Ганта. Именно ими вы будете руководствоваться, перемещая процессы в поисках оптимального решения.
Что же, давайте перейдём от слов к делу. Начнём разбирать алгоритм решения с такой формулировки:
«В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а время окончания работы всех процессов минимально.»
Сразу обратите внимание на последнюю фразу «время окончания работы всех процессов минимально». Она говорит нам о том, что нам нельзя двигать никакой другой процесс дальше самого «долгого» процесса. То есть, процесс, время окончания которого наибольшее, будет для нас этакой границей: позже него не может заканчиваться ни один другой процесс.
Теперь приступим к решению. Подробно останавливаться на построении самой диаграммы Ганта в данной статье мы не будем. Все это уже разобрано в двух предыдущих статьях.
Открываем приложенный к заданию файл и оформляем таблицу.
Теперь добавляем временную шкалу. Для этого в ячейке «J1» поставим единицу, в следующей за ней ячейке «K1» напишем формулу: «=J1+1» и скопируем её до конца листа.
Для построения диаграммы Ганта осталось лишь построить сами «полоски» процессов. В ячейке «J2» прописываем формулу «=ЕСЛИ(И($G2<=J$1; J$1<=$H2); 1; «»)» и растягиваем её до конца вправо и вниз.
И теперь начинаем анализировать получившуюся диаграмму. Во-первых, добавим вспомогательную строку, в которой будем подсчитывать количество одновременно работающих процессов. В «J14» вставляем формулу «=СУММ(J2:J14)» и растягиваем её вправо.
Перемещаемся в конец диаграммы. Здесь мы видим процесс, который заканчивается позже всех.
Это означает, что позже 37 секунды ни один процесс заканчиваться не может. Иными словами, ни одна «полоска» не должна находиться правее столбца «AT». Его можно даже выделить цветом, чтобы точно понимать, не пересекает ли какой другой процесс установленную границу.
Следовательно, 112 процесс, как самый «поздний» не может быть сдвинут вообще. Давайте посмотрим, от каких процессов он зависит.
От 110 и 111 процессов, которые, в свою очередь, зависят от 109. Это означает, что ни один из них мы не можем сдвигать.
Что же, раз блок процессов 109-113 у нас жёстко зафиксирован, то, может, получится сдвинуть другие так, чтобы получить максимальную цепочку процессов, работающих одновременно?
На прошлом изображении мы видели, что процесс 108 критически близко подобрался в границе, буквально в одной клетке от неё. Давайте таким же образом проследим зависимости этого процесса:
- 108 зависит от 107
- 107 зависит от 105 (106 тут не важен)
- 105 – от 103
- 103 – от 101
И все эти зависящие друг от друга процессы образуют непрерывную «лестницу» потока выполнения процессов (выделена на изображении).
Сдвинув любой из них, мы сдвинем и 108, который уже переступит «границу».
Что это для нас означает? Что нам даже не стоит двигать никакие процессы. Давайте просто найдём сначала максимум процессов, а затем максимальную их длительность.
Здесь максимум 4 процесса выполняются параллельно, а максимальная длительность одновременной работы четырёх процессов достигается с 15 по 19 миллисекунды, то есть – 5 миллисекунд.
Число 5 и будет ответом на это задание.
Пример 1
Что же, в прошлом задании нам так и не удалось «подвигать» процессы. Давайте теперь разберём такое, в котором без этого не обойтись.
Формулировка будет следующая:
«В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а время окончания работы всех процессов минимально.»
Шаг с построением диаграммы Ганта мы опустим. Выглядеть она будет следующим образом.
Вспоминаем про последнюю фразу из условия и перемещаемся в конец диаграммы. Сразу отметим столбец «AT» красным, чтобы в будущем случайно его не пересечь.
Казалось бы, ситуация похожа на предыдущую, что же, снова не будем ничего двигать? Не спешите с выводами!
Итак, вспоминаем про наши 5 вопросов, о которых говорили в начале. В прошлом примере они нам не сильно пригодились, но сейчас как никогда кстати.
Давайте выделим блоки взаимозависимых процессов. Мы их будем определять единым «таймлайном», то есть рисовать непрерывную «лесенку» из зависимых процессов, идущих друг за другом. Первый блок состоит из процессов от 101 до 108.
Что такая «лесенка» означает? Что, сдвинув любой процесс, на котором нарисована стрелка, сдвинутся все остальные процессы со стрелками. То есть в нашем случае нельзя двигать процессы: 101, 103, 105, 107 и 108.
Но процессы без стрелок в этой группе можно двигать в пределах вертикальных линий. То есть процесс 102 можно сдвинуть на 1 ячейку, процессы 104 и 106 – вплоть до конца 33 миллисекунды.
Аналогичная история со вторым блоком взаимозависимых процессов: с 109 по 113.
Здесь 111 процесс можно двигать до конца 110, а 113 – вообще, как угодно, от него никто не зависит. Разве что этот процесс не должен заканчиваться позже 36 миллисекунды.
Переходим ко второму вопросу, сколько максимально процессов работают параллельно в каждом блоке? В обоих блоках одновременно работают по 2 процесса, значит, максимум, которого можно достичь – это 4 процесса, работающих в одно время. Больше сделать тут никак не получится.
Теперь, как долго работает это максимальное количество процессов в каждом блоке? В первом блоке два процесса работают 14 мс (с 19 по 32), во втором – столько же (с 9 по 22). Сделаем акцент на эти периоды времени и попытаемся «нарастить» длительность одновременной работы всех четырёх процессов.
Обратите внимание на форму группы процессов 111 и 113. Они так и просят передвинуть их на 8 ячеек вправо и сравнять «границы» 110 и 111 процессов.
Давайте так и поступим: у 111 процесса в колонке «Сдвиг» пишем число 8.
И получается вот такая красота.
Мы получили 4 одновременно работающих процессов на протяжении 12 миллисекунд. Но можно ли увеличить время работы этой цепочки?
Давайте обратим наш взгляд на правую часть диаграммы Ганта.
Во-первых, мы видим, что вторую группу процессов можно сдвинуть еще на одну ячейку. Во-вторых, вся длительность работы четырёх процессов ограничена именно вторым блоком, а именно, 113 процессом. Его конец в столбце «AM» соответствует окончанию длительности работы всех четырёх процессов.
Так что давайте сдвинем второй блок на одну миллисекунду. Второй блок начинается с 109 процесса, именно в его строке и впишем значение сдвига, равное 1.
Готово, теперь наша цепочка из четырёх процессов длится целых 13 миллисекунд.
В ответ запишем число 13.
Пример 2
И завершим разбор алгоритма решения 22 заданий примером с такой формулировкой:
«В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.»
Теперь уже никаких ограничений на время окончания процессов нет, можем их спокойно передвигать.
Сразу построим диаграмму Ганта и начнём анализ.
Выделим все блоки созависимых процессов. Временно, для наглядности, каждой группе созависимых процессов присвоим свой цвет. Сразу уточним термины: в одном блоке несколько групп процессов; группы влияют друг на друга, блоки между собой не связаны никак.
Итак, от 101 процесса зависит 103, за ним идёт 105, за которым 108 и 109.
Эти процессы можно, условно, выстроить в одну линию.
Далее идёт вторая группа. В неё входят 102 и 104 процессы. Причем от 104 ничто не зависит, его можно спокойной передвигать вправо. Влево его движение ограничивает 102. Сам же 102 может двигаться вправо вплоть до начала 103 процесса, который от него зависит.
То есть можно воспринимать 103 процесс как некий «шлагбаум»: дальше него не могут «проехать» ни 101, ни 102 процесс.
Есть еще одна группа процессов: 106 и 107. Их также можно выстроить в линию, а их «шлагбаумом» является 108 процесс. «Сзади» же их подпирает 103 – раньше него они начаться не могут.
Все рассмотренные выше группы процессов организуют первый блок.
Ну и второй блок – это оставшиеся процессы 110-113. В единую линию выстраиваются 110, 112 и 113 процессы, а 111 может спокойно двигаться вправо, а его движение влево ограничивает 110 процесс.
Что же, с тем, как допускается передвигать процессы, разобрались. Теперь определим, сколько максимально процессов может работать одновременно внутри каждого блока. В верхнем блоке одновременно уже работают по 2 процесса: с 1 по 14 мс и с 16 по 27 мс.
Но давайте уделим особое внимание второй группе.
Мы же помним, что 104 процесс у нас может беспрепятственно двигаться вправо? Так давайте поместим его начало на 16 миллисекунду.
Для этого сдвинем его на 12 единиц.
Таким образом, с 16 по 26 мс у нас будут одновременно работать сразу 3 процесса.
К сожалению, увеличить длительность их работы пока не представляется возможным. Так что, давайте перейдём ко второму блоку.
Здесь у нас параллельно выполняются 2 процесса. Следовательно, грамотно совместив оба блока, можем получить 5 параллельных процессов.
Давайте внимательно посмотрим на начало процессов на 16 и 8 миллисекундах. Нижний блок так можно передвинуть вправо так, чтобы конец 110 процесса совпадал с началом 104-106 процессов.
Тем самым мы сможем получить группу из 5 процессов, работающих одновременно. Для этого давайте сдвинем группу, зависящую от 110 процесса на 7 миллисекунд.
В итоге получаем, что с 16 по 25 миллисекунду у нас одновременно работает максимальное количество процессов.
Значит, мы готовы дать ответ: максимальное время, в течение которого работают 5 процессов – 10 миллисекунд.
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре
<<< Предыдущая статья Первая статья >>>