Теория к заданию 22 ЕГЭ по информатике Многопроцессорные системы и параллельные вычисления
Задание 22 проверяет расчёт параллельных процессов. В файле дана таблица: ID процесса, его длительность в миллисекундах и ID процессов, от которых он зависит. Процесс начинается, когда закончились все его предшественники: начало и окончание процесса. Вопросы линии: минимальное время всей совокупности, наибольшая неизвестная длительность при заданном общем времени, сколько процессов работают одновременно и как долго.
Ответ — одно целое число, за верный ответ дают 1 балл. Файл — электронная таблица, поэтому задание решают на компьютере. Окончания процессов считают в столбце таблицы или программой с рекурсивной функцией. Таблицу из десятка процессов быстро считают и вручную.
Пример задания
Открытый банк ФИПИ
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. В файле информация о процессах представлена в виде таблицы. В первой колонке таблицы указан идентификатор процесса (ID), во второй колонке таблицы — время его выполнения в миллисекундах, в третьей колонке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Время выполнения одного из процессов неизвестно и для данного процесса в соответствующей колонке обозначено как t.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) А |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | t | 1; 2 |
| 4 | 7 | 3 |
Определите максимальное возможное целочисленное t (время выполнения процесса), при котором выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, завершилось не более чем за 19 мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Что учить: от главного к редкому
Главное
Самые частые правила — учите первыми
Тренировка в формате ЕГЭ
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы Aи B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) А |
|---|---|---|
| 101 | 4 | 0 |
| 102 | 3 | 0 |
| 103 | 1 | 101; 102 |
| 104 | 7 | 103 |
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение пяти процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.