Задание № 22 ЕГЭ по информатике связано с анализом процессов, которые могут выполняться параллельно или последовательно. В таких задачах важно учитывать зависимости между процессами и правильно определять время их начала и окончания.
В этой статье разберём, как решаются подобные задания: как работать с зависимыми и независимыми процессами, как рассчитывать время выполнения и как находить максимальную продолжительность параллельной работы процессов.
Термины, которые мы будем использовать: зависимый/независимый процесс.
Что такое процессы в системе и как они связаны между собой
Процесс — это единица работы с заданным временем выполнения (в мс).
Зависимость B от A означает, что для выполнения процесса B необходим результат работы процесса A.
A и B могут выполняться только последовательно.
Независимые процессы не имеют зависимостей друг от друга (или от них не зависит никто из ещё не запущенных).
Они могут выполняться параллельно (одновременно) на разных ядрах или процессорах.
Продолжительность отрезка времени — это интервал (в мс), в течение которого выполняется определённый набор процессов (например, максимальное количество одновременно работающих).
Минимальное время окончания всех процессов достигается, когда любой процесс запускается сразу, как только все его зависимости завершены.
Как определить время выполнения процессов
Раннее время начала процесса рассчитывается так:
- для независимого процесса (без предков): начало = 0;
- для зависимого: начало = max (время окончания всех его предков) + 1.
Время окончания = начало + длительность.
Как работать с таблицей процессов
Разберёмся, как строить таблицу процессов, на примере типовой задачи.
Задача 1
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Типовой пример организации данных в файле
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1;2 |
| 4 | 7 | 3 |
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а время окончания работы всех процессов минимально.
Для начала подготовим таблицу, чтобы можно было автоматизированно сдвигать отрезки.
- Столбец с зависимостями текущего процесса разделим на отдельные ячейки, чтобы у каждого номера была своя клетка.
- Создадим два столбца, где будет указано время, от которого зависит начало выполнения процесса. В этих ячейках будет записано время, после которого процесс может начаться. Подтянуть значения можно с помощью функции ВПР: $\text{=ВПР(C2;\$A:\$I;8;0)}$. Также добавим значение 0 в последнюю строку столбца A, чтобы формула работала корректно.
- Сделаем клетки старта и финиша, отталкиваясь от начала и продолжительности процесса, а также сдвига, который мы решим установить: $\text{=МАКС(E2:F2)+I2+1}$ и $\text{=G2+B2−1}$.
- Создадим столбец «сдвиг», в который мы можем поставить любое число в любую ячейку.
- Запишем формулу в схему, где должны находиться наши отрезки, которая подтянет нужное расположение каждого отрезка: $= \text{ЕСЛИ}(\text{И}(\text{K}\$1 >= \text{\$G}2; \text{K}\$1 <= \text{\$H}2); 1; \text{””})$ и протянем её.
По условию задачи общее время выполнения должно быть минимальным, то есть не больше 37 мс. Подбирая значения в столбце «сдвиг», можно автоматически передвигать процессы (и все зависящие от них), так что методом подбора сможем обнаружить максимальную продолжительность — 5 мс.
Ответ: 5.
Задача 2
Условие перед вопросом сохраняется таким же, как в предыдущей задаче.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение пяти процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Аналогично оформляем вспомогательную таблицу и начинаем искать лучшие сдвиги.
Чтобы найти лучший сдвиг, нужно стараться подстроить все процессы максимально друг под друга и следить, чтобы они начинались после процессов, от которых зависят, и завершались до процессов, которые зависят от них.
Максимальная продолжительность оказалась равна 7 мс.
Ответ: 7.
Задача 3
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение трёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Аналогично оформляем вспомогательную таблицу и начинаем искать лучшие сдвиги.
Максимальная продолжительность оказалась равна 18 мс.
Ответ: 18.
Задача 4
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно и на выполнение всей совокупности процессов затрачено минимальное время.
Решим это задание аналогично предыдущим.
Вспомогательную таблицу можно не строить заново — достаточно скопировать уже готовый шаблон: формулы автоматически расставят процессы в исходные позиции.
Также отметим красной полосой время, в которое закончатся все процессы при отсутствии каких-либо сдвигов — это и будет минимально затраченное время. Опираясь на него, начнём передвигать процессы, не переходя эту границу.
Максимальная продолжительность искомого отрезка составила 8 мс.
Ответ: 8.
Заключение
После изучения этой темы можно уверенно решать задания № 22 на многопроцессорные системы.
Теперь ты умеешь:
- определять зависимости между процессами;
- находить время начала и окончания процессов;
- работать с параллельным выполнением;
- находить максимальную продолжительность отрезка времени.
Чтобы закрепить материал, реши несколько заданий из открытого банка ЕГЭ и проверь себя.
Автор статьи
