Центр подготовки к ЕГЭ > Материалы для подготовки к ЕГЭ и ОГЭ > Программа ЕГЭ по информатике — Разбор задач и материалы > Задание №22 на ЕГЭ по информатике. Параллельные вычислительные процессы.

Задание №22 на ЕГЭ по информатике. Параллельные вычислительные процессы.

В 2023 году в ЕГЭ по информатике появилось новое задание, которое «призвано привлечь внимание к параллельному программированию, технологиям организации многозадачных / многопоточных вычислений». Для выполнения задания необходимо использовать файл – электронную таблицу. Это задание проверяет навык построения математических моделей для решения практических задач.

На самом деле все современные вычисления многопоточные и все современные компьютеры многопроцессорные. Если раньше многопроцессорные вычислительные системы (МВС) применялись в основном в научной сфере для решения вычислительных задач, требующих мощных вычислительных ресурсов, то сейчас МВС применяются повсеместно.

Пример 1
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы  — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Выполните задания, используя данные из файла 22_1.xlsx

Решение:
Чтобы понять, как решать задачу, проиллюстрируем взаимосвязь процессов на примере диаграммы Ганта. Это не способ решения, а только иллюстрация того, как выполняются процессы.
Откроем файл 22_1.xlsx.

Мы видим, что процессы 1, 2, 9 и 10 из столбца В ни от чего не зависят и могут выполняться одновременно. Отобразим это на диаграмме:

Синим цветом выделена ось Х, цифрами обозначена длительность процесса в мс. Зеленым выделены номера процессов.
1-ый процесс ни от чего не зависит, можем запустить и длится он 4 мс.
2-ой процесс тоже ни от чего не зависит, может идти параллельно с 1-м и длится 3 мс.
3-ий процесс зависит только от 1-го и 2-го, длится 1 мс.
4-ый процесс зависит от 3-го и длится 7 мс.
5-ый процесс зависит от 3-го, может идти параллельно 4-му и длится 6 мс.
6-ый процесс зависит от 5-го и длится 3 мс.
7-ый процесс зависит от 4-го и 6-го и длится 1 мс.
8-ый процесс зависит от 7-го и длится 2 мс.
9-ый процесс независимый и длится 7 мс. Запускается сразу.
10-ый процесс независимый и длится 8 мс. Запускается сразу.
11-ый процесс зависит от 9-го и длится 6 мс.
12-ый процесс зависит от 10-го и длится 6 мс.
Нам нужно отобразить время, когда закончились все процессы.
Видим, что 17 мс прошло и все процессы закончились.
Диаграмма зависимости времени процессов друг от друга называется диаграммой Ганта. На ней удобно отслеживать время и очередность процессов.
Однако в данной задаче это не лучший способ решения.
Как решить такую задачу по-другому?
Нарисуем схему запуска всех процессов. Цифра – номер процесса, а индекс общее количество затраченного времени от момента запуска всей системы. Считаем устно, все расчеты зарисовываем и записываем внимательно:

Ответ: 17

Пример 2.
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы  — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:

Решение:
В данной задаче есть процесс, который зависит от трёх источников.
Сделаем иллюстрацию с помощью диаграммы Ганта.

Самая поздняя секунда, когда закончатся все процессы – 24.
Нарисуем схему:

Ответ: 24

Пример 3
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение не раньше чем через 3 мс после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_3.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов. Определите, за какое минимальное время можно выполнить все процессы.
В ответе запишите целое число – минимальное время в мс.

Решение:
Задача аналогичная, но есть нюанс. Здесь любой следующий процесс запускается не мгновенно, а с зазором в 3 мс.
Чтобы не запутаться и не рисовать руками, можно все тоже самое сделать в Excel.
Скопируем данные в Excel. Столбец D будет отображать общее время окончание процесса.

Время процессов, которые ни от чего не зависят – можно сразу посчитать:

Общее время 4-го процесса – это максимум времени 1-го и 2-го процессов, плюс 3 мс и плюс время самого процесса:

Точно так же считаем общее время для каждого процесса. Все записываем вручную по каждому процессу. Ответ задачи – максимальное время:

Конечно, это ручной метод, и он удобен до тех пор, пока в операциях не возникнут большие числа.

Нарисуем схему как альтернативу:

Ответ: 26

Пример 4
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_4.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщика данных для зависимых процессов. Определите, за какое минимальное время можно выполнить все процессы.
В ответе запишите целое число – минимальное время в мс.
Решение:
В этой задаче уже 20 строк. Схемой решать становится неудобно, поэтому решим при помощи Excel.
Там, где процесс ни от чего не зависит, мы просто дублируем данные в столбец D, там, где есть поставщики данных, пишем условия подсчета.

Максимальное число – 29.
Ответ: 29
Это не автоматизированное решение, но вполне удобное.

Пример 5
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения другого процесса – поставщика данных. Независимые процессы (не имеющие поставщика данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_5.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщика данных для зависимых процессов. Определите, за какое минимальное время можно выполнить все процессы.
В ответе запишите целое число – минимальное время в мс.
Решение:
На первый взгляд, задача стала проще. У процесса B либо нет поставщика, либо он один. Однако появились другие сложности:
- таблица из ста строк
- на глаз сложно идентифицировать процесс, а значит, уйдет много времени на поиск нужного процесса
– величина времени двухзначная, а значит,устно считать становится сложнее.
Однако выход есть!
Запишем формулу: если поставщик данных пустой, то берем время выполнения процесса, иначе используем функцию ВПР:

Растягиваем формулу по столбику D и затем находим максимум.

Ответ:312

От задачи к задаче файл увеличивается, и предполагается, что мы не будем это обрабатывать вручную. Иногда предлагают программный способ решения, но мы видим, что с этой задачей прекрасно работает Excel. Мы используем отличную функцию ВПР, которая работает и в 9, 18, 26, а теперь и в 22 задаче.

Разберем функцию ВПР подробнее.
ВПР работает по следующему принципу: Функция просматривает выбранный диапазон таблицы вертикально сверху вниз до искомого значения идентификатора. Когда видит его, забирает значение напротив него из нужного столбца и копирует в ячейку.
Аргументы функции: искомое значение, таблица, номер столбца, интервальный просмотр.
Искомое значение — название ячейки, из которой функция будет искать данные для переноса. В нашем случае – это номер процесса-поставщика.
Таблица — это диапазон ячеек, из которого функция будет брать данные для искомого значения. В этот диапазон должны войти столбцы с искомым значением и со значением, которое нужно перенести в ячейку. В нашем случае нужно перенести время окончания процесса-поставщика, поэтому указываем верхнюю часть исходной таблицы.
Номер столбца — порядковый номер столбца в таблице, в котором находится переносимое значение. Считается по принципу: номер 1 — самый левый столбец, 2 — столбец правее и так далее. В нашем случае значение для переноса — время — находится в четвертом столбце слева. Если столбцы не пронумерованы, посчитайте их вручную.
Интервальный просмотр — условное значение, которое настроит, насколько точно сработает функция:
• Если нужно точное совпадение при поиске ВПР, вводим ЛОЖЬ.
• Если нужно приближённое соответствие при поиске ВПР, вводим ИСТИНА.
В нашем случае нужно, чтобы функция подтянула точные значения.

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

Пример 6
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения другого процесса – поставщика данных. Независимые процессы (не имеющие поставщика данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение не раньше, чем через 4 мс после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_6.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщика данных для зависимых процессов. Определите, за какое минимальное время можно выполнить все процессы.
В ответе запишите целое число – минимальное время в мс.
Решение:
Опять в файле 100 строк, сложно искать глазами нужный процесс, а также начало следующего процесса начинается не моментально, а с зазором в 4 мс.
Запоминаем! Если процесс ни от чего не зависит, то будет выполняться с нуля, а если зависит, то между поставщиком данных и самим процессом еще 4 мс.

Растягиваем формулу по всему столбцу D и берем максимальное значение:

Ответ: 227

Пример 7

В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение не раньше, чем через 3 мс после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_7.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов. Определите, за какое минимальное время можно выполнить все процессы.
В ответе запишите целое число – минимальное время в мс
Решение:
Эта задача еще сложнее: данных много, время выполнения двузначное, процессы не по порядку выстроены, а поставщиков данных может быть несколько.
Для начала давайте разделим поставщиков данных. Их максимум два, поэтому напишем формулу, которая откусит в столбце C пять первых символов, а если в столбце нет поставщика данных, то выводится «0». Так получится столбик D.

Столбик Е получим практически так же, лишь слегка изменив формулу:

Что в итоге получилось? Мы разделили столбик С на два: там, где не было поставщика проставили «0», где был один поставщик, он ушел в столбик D, где было два поставщика, разделили их на два столбика D и Е.
Есть один нюанс, чтобы в формулу ввести «0», надо ввести его в таблицу. Посмотрите, мы специально вводим первую строку с ID процесса «0» и итоговым временем «0». Это надо указать, чтобы сократить итоговую формулу.
Напишем формулу для столбика F:

Заметьте, что в формуле указан выбор максимального значения для двух столбиков.
Последний штрих – ищем максимальное значение из столбика F.
Ответ: 581

Пример 8

В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_8.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите, какое наибольшее количество процессов может быть завершено за первые 200 мс.

Решение:
В этой задаче немного другая постановка вопроса: «какое наибольшее количество процессов может быть завершено за первые 200 мс?»
Тут можно запутаться и совершить ошибку. В момент времени 200 мс надо посчитать процессы, которые УЖЕ закончились. В точке x=200, двухсотая секунда уже закончится, т.е. считаем количество процессов, время окончания которых будет ≤200.
Оформляем файл задачи, как в седьмой задаче. Нюанс только в том, что в данной задаче нет временного зазора между поставщиками.
Также разбиваем столбец С на D и E:

После этого создаем столбец F (время завершения процесса), обязательно создав несуществующий процесс с ID=0

И последний штрих – ищем все процессы, которые к моменту времени 200 мс были завершены:

Заметьте, что в последней формуле мы считаем реальные процессы с третьей строчки и ниже. Вторую строчку с несуществующим процессом мы не считаем.
Ответ: 82

Пример 9

В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_9.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите, сколько процессов выполнялось одновременно в течение 100-й мс
Решение:
Что значит, что процессы выполнялись? Это значит, что у этих процессов начало ≤99 мс, а окончание ≥100 мс.
Чтобы узнать время начала, нам надо из времени окончания процесса отнять время самого процесса. А время окончания мы с вами считать уже умеем.
Наши действия такие же, как в предыдущих задачах: разделяем столбец С на D и Е. Считаем время окончания процесса, а также добавляем новый столбик – G – время начала процесса:

Теперь нам нужно посчитать сколько процессов выполнялось одновременно в 100 мс:

Ответ: 14

Пример 10

В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного, двух или трех входящих процессов. Независимые процессы (у которых нет входящих процессов) можно запускать в любой момент времени. Если процесс B получает данные от процесса A (входящего процесса), то процесс B может начать выполнение не раньше, чем через 3 мс после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_10.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID входящих процессов. Определите, за какое минимальное время можно выполнить все процессы.
В ответе запишите целое число – минимальное время в мс.
Решение:
В этой задаче очень много строчек и бывает даже три поставщика, поэтому мы делим столбец С на три столбика: D, E, F.
Формула для столбца D: