Автор статьи: Андрей Рогов
Введение
В статье рассмотрены основные способы решения задания № 22 без необходимости сдвигать процессы. Там же представлена общая информация о формулировках. Давайте разберёмся с заданиями, где начало процесса может сдвигаться.
Как вообще понять, что процесс можно двигать? В заданиях, где это не так, есть следующее предложение: «Считать, что каждый процесс начинается в самое раннее допустимое время». В заданиях же, где начало процесса можно сдвинуть, такая фраза отсутствует. Однако может встретиться другая: «Время окончания работы всех процессов минимально». Это тоже необходимо учитывать в решении: сдвигать можно не все процессы, а только те, сдвиг которых не повлияет на общее время окончания работы.
Задача 1. Точное количество параллельных процессов
Для решения такого задания нам необходимо наглядно видеть связи между процессами. Важно, чтобы при перемещении процесса связь тоже сдвигалась. Удобно использовать для этого фигуры с панели рисования. В программе Libre Office Calc из офисного пакета Libre Office отсутствуют линии, связывающие две фигуры. Однако такой инструмент есть в Libre Office Draw, тоже части пакета. Программы позволяют скопировать линию из Draw и вставить её в Calc.
Отобразим панель рисования в Calc. Для этого в меню выберем пункт «Вид» → «Панели инструментов» → «Рисование».
Процессы будем изображать с помощью прямоугольников. Высота равна одной строке, а ширина — количеству столбцов сообразно времени выполнения процесса. Соединительную линию скопируем из программы Libre Office Draw. В дальнейшем будем делать копию соединительной линии непосредственно в Calc, т. е. достаточно один раз скопировать её из Draw.
Далее, соблюдая порядок процессов, изобразим все оставшиеся. Вот один из возможных путей построения диаграммы:
- Рисуем прямоугольник процесса, выдерживая его размер
- Делаем подпись на прямоугольнике — номер процесса
- Сдвигаем прямоугольник в нужное место
- С помощью соединительной линии скрепляем прямоугольники
Другой вариант: сначала расставить все прямоугольники, затем размещать соединительные линии. Полученная диаграмма представлена на рисунке ниже.
Мы видим три цепочки процессов, которые между собой могут выполняться параллельно. Цепочки 9–11 и 10–12 дают нам по два параллельных процесса. Чтобы их стало четыре, мы можем добавить идущие параллельно 1 и 2 либо 4 и 5 с 6. Чтобы получить максимальную продолжительность, необходимо взять процессы 4, 5 и 6. Мы получим следующую картину:
Её продолжительность равна продолжительности минимальной цепочки. В нашем случае это процесс с ID 4. Таким образом, ответ на задание равен 7.
Основная задача — наглядно увидеть, как связаны процессы. При этом у нас есть возможность сдвигать их, учитывая связи. В случае с этой задачей можно было в черновике нарисовать диаграмму Ганта от руки. Однако в более сложных случаях схема выглядела бы запутанной.
Задача 2. Максимальная продолжительность максимального количества процессов
В задании не даётся конкретное количество параллельных процессов, а требуется сначала найти максимально возможное значение. Изобразим данные графически.
Мы получили две независимые цепочки. В верхней возможно два параллельных процесса. В начале цепочки могут идти процессы 101-й и 102-й, а в середине — 104-й + 106-й и 105-й.
В нижней цепочке тоже идёт два процесса параллельно, 110-й и 111-й. Но 113-й можно запускать сразу после 111-го, и он тоже будет параллелен 110-му. После окончания 110-го процесса 113-й пойдёт параллельно со 112-м.
Одно из условий задания — минимальное время завершения всех процессов. Без этого условия можно было бы сдвинуть начало 101-го и 102-го так, чтобы получить 9 мс идущих параллельно четырёх процессов.
Однако мы так сделать не можем, поскольку процессы не завершатся за минимальное время. Верхнюю цепочку можно завершить за 101 + 103 + 105 + 107 + 108 = 12 + 2 + 18 + 1 + 3 = 36 мс, нижнюю цепочку — за 109 + 110 + 112 = 8 + 14 + 15 = 37 мс. Значит, верхнюю, если необходимо, получится сдвинуть вправо на 1 мс. Рассмотрим места, где может идти четыре процесса параллельно.
Рассмотрим жёлтый прямоугольник. Если мы сдвинем всю верхнюю цепочку на 1 мс вправо, то четыре процесса будут идти 102 − 109 = 9 − 8 = 1 мс + 1 мс сдвига = 2 мс. В зелёном прямоугольнике мы получим бóльшую продолжительность: 104 + 106 = 4 + 1 = 5 мс. Максимально возможная продолжительность выполнения четырёх процессов параллельно равна 5 мс.
Задача 3. Максимальное количество процессов за определённое время
Несмотря на то что задание очень похоже на предыдущее, здесь нет ограничения «все процессы должны завершаться за минимальное время».
Построим диаграмму процессов. Они имеют большую продолжительность, поэтому диаграмма получается вытянутой.
Определим, сколько процессов может идти параллельно. В нижней цепочке это довольно просто, там одно ветвление, поэтому параллельно можно запустить по два процесса: 109 + 110 и 111 + 112. Максимальная продолжительность будет равна сумме 111-го и 112-го процессов, поскольку они короче: 111 + 112 = 7 + 4 = 11 мс.
На первый взгляд в верхней цепочке тоже максимум два процесса, однако 107-й можно сдвинуть так, чтобы он шёл параллельно со 102-м и 103-м. Таким образом, в верхней цепочке можно запустить сразу три параллельных процесса.
Поскольку в этой задаче нет требования, что все процессы должны завершиться за минимальное время, всю верхнюю цепочку мы можем сдвинуть так, как показано на рисунке.
Пять параллельных процессов могут идти столько, сколько длится 107-й процесс, т. е. 7 мс.
Заключение
В статье были рассмотрены различные подходы к решению задания № 22 ЕГЭ по информатике с возможностью сдвига процессов с применением электронных таблиц. Преимущества подхода:
- наглядность представления данных
- удобство анализа временных интервалов
- гибкость при изменении условий задачи
Освоение рассмотренных методов позволит эффективно решать задание № 22 даже в случае появления новых вариаций условий. Полученные навыки могут быть успешно применены при решении других задач, связанных с анализом временных зависимостей.
Особое внимание стоит уделить ограничениям, которые есть в задании. Как мы увидели, всего одно предложение может полностью изменить способ получения ответа.
Рекомендуем решить подборку задач для практики.