Задание № 22 ЕГЭ по информатике связано с анализом процессов, которые могут выполняться параллельно или последовательно. В таких задачах важно учитывать зависимости между процессами и правильно определять время их начала и окончания.

В этой статье разберём, как решаются подобные задания: как работать с зависимыми и независимыми процессами, как рассчитывать время выполнения и как находить максимальную продолжительность параллельной работы процессов.

Термины, которые мы будем использовать: зависимый/независимый процесс. [i]

Что такое процессы в системе и как они связаны между собой

Процесс — это единица работы с заданным временем выполнения (в мс).
Зависимость B от A означает, что для выполнения процесса B необходим результат работы процесса A. [i]

A и B могут выполняться только последовательно.

Независимые процессы не имеют зависимостей друг от друга (или от них не зависит никто из ещё не запущенных). [i]

Они могут выполняться параллельно (одновременно) на разных ядрах или процессорах.

Продолжительность отрезка времени — это интервал (в мс), в течение которого выполняется определённый набор процессов (например, максимальное количество одновременно работающих).
Минимальное время окончания всех процессов достигается, когда любой процесс запускается сразу, как только все его зависимости завершены. [i]

Как определить время выполнения процессов

Раннее время начала процесса рассчитывается так:

для независимого процесса (без предков): начало = 0;
для зависимого: начало = max (время окончания всех его предков) + 1.

Время окончания = начало + длительность.

Подготовка к экзаменам в 100балльном репетиторе

Как работать с таблицей процессов

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

Задача 1

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

Типовой пример организации данных в файле

ID процесса B	Время выполнения процесса B (мс)	ID процесса(-ов) A
1	4	0
2	3	0
3	1	1;2
4	7	3

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а время окончания работы всех процессов минимально. [i]

Как определить время выполнения процессов

Для начала подготовим таблицу, чтобы можно было автоматизированно сдвигать отрезки.

Столбец с зависимостями текущего процесса разделим на отдельные ячейки, чтобы у каждого номера была своя клетка.
Создадим два столбца, где будет указано время, от которого зависит начало выполнения процесса. В этих ячейках будет записано время, после которого процесс может начаться. Подтянуть значения можно с помощью функции ВПР: =ВПР(C2;$A:$I;8;0). Также добавим значение 0 в последнюю строку столбца A, чтобы формула работала корректно.
Сделаем клетки старта и финиша, отталкиваясь от начала и продолжительности процесса, а также сдвига, который мы решим установить: $=МАКС(E2:F2)+I2+1$ и $=G2+B2−1$ .

Создадим столбец «сдвиг», в который мы можем поставить любое число в любую ячейку.

Запишем формулу в схему, где должны находиться наши отрезки, которая подтянет нужное расположение каждого отрезка: = ЕСЛИ(И(K$1 >= $G2; K$1 <= $H2); 1; ””) и протянем её.

По условию задачи общее время выполнения должно быть минимальным, то есть не больше 37 мс. Подбирая значения в столбце «сдвиг», можно автоматически передвигать процессы (и все зависящие от них), так что методом подбора сможем обнаружить максимальную продолжительность — 5 мс.

Задание 22 ЕГЭ по информатике многопроцессорные системы (примеры решений)

Ответ: 5.

Задача 2

Условие перед вопросом сохраняется таким же, как в предыдущей задаче.

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение пяти процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. [i]

Аналогично оформляем вспомогательную таблицу и начинаем искать лучшие сдвиги.

Многопроцессорные системы (разбор и решения)

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

Максимальная продолжительность оказалась равна 7 мс.

Ответ: 7.

Задача 3

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение трёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. [i]

Аналогично оформляем вспомогательную таблицу и начинаем искать лучшие сдвиги.

Многопроцессорные системы, информатика ЕГЭ

Максимальная продолжительность оказалась равна 18 мс.

Ответ: 18.

Задача 4

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно и на выполнение всей совокупности процессов затрачено минимальное время. [i]

Решим это задание аналогично предыдущим.

Вспомогательную таблицу можно не строить заново — достаточно скопировать уже готовый шаблон: формулы автоматически расставят процессы в исходные позиции.

Также отметим красной полосой время, в которое закончатся все процессы при отсутствии каких-либо сдвигов — это и будет минимально затраченное время. Опираясь на него, начнём передвигать процессы, не переходя эту границу.