Задание 22 ЕГЭ по информатике · 10A671
Параллельные процессы: сколько и как долгоВысокаяКЭС 1.1
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Типовой пример организации данных в файле
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Типовой пример организации данных в файле
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 101 | 4 | 0 |
| 102 | 3 | 0 |
| 103 | 1 | 101; 102 |
| 104 | 7 | 103 |
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
К заданию прилагается файл с данными — скачайте его в задании внутри Precettore.
Показать ответ
2
Подсказки (3)
- Постройте граф зависимостей процессов и определите интервалы времени, на которых каждый процесс выполняется.
- Для каждого процесса сначала найдите момент его запуска: он начинается после завершения всех процессов, от которых зависит.
- Отметьте границы всех интервалов выполнения, посчитайте число одновременно работающих процессов на каждом промежутке и выберите самый длинный промежуток с максимальным числом процессов. Его продолжительность равна 16 мс.
Решение
1. По данным файла для каждого процесса определяем время начала. Если процесс зависит от нескольких процессов, его запуск возможен после завершения самого позднего из них.
tstart(B)=maxA∈Dependencies(B)(tstart(A)+t(A))
2. Для каждого процесса записываем интервал его выполнения [tstart,tstart+t] и объединяем все моменты начала и окончания процессов.
3. На каждом получившемся промежутке подсчитываем количество одновременно выполняющихся процессов.
4. Находим максимальное количество одновременно выполняющихся процессов и среди промежутков с этим количеством выбираем самый длинный.
tstart(B)=maxA∈Dependencies(B)(tstart(A)+t(A))
2. Для каждого процесса записываем интервал его выполнения [tstart,tstart+t] и объединяем все моменты начала и окончания процессов.
3. На каждом получившемся промежутке подсчитываем количество одновременно выполняющихся процессов.
4. Находим максимальное количество одновременно выполняющихся процессов и среди промежутков с этим количеством выбираем самый длинный.
Частые ошибки
- Считать зависимые процессы выполняющимися одновременно.
- Начинать процесс сразу после завершения только одной из его зависимостей.
- Искать общую продолжительность выполнения всех процессов вместо длины промежутка с максимальным параллелизмом.
- Не учитывать моменты окончания процессов как границы интервалов.
Похожие задания
22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · E923FA22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · A3580C22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 330C0022В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 777B7822В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · E3251922В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · DAB82122В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 4A47D422В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 42A2E4
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.