Задание 22 ЕГЭ по информатике · 777B78
Параллельные процессы: сколько и как долгоВысокаяКЭС 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.
Показать ответ
4
Подсказки (3)
- Представьте процессы в виде ориентированного графа зависимостей и определите интервалы их выполнения.
- Процесс может начаться только после завершения всех процессов, от которых он зависит. Для каждого момента времени посчитайте число одновременно выполняющихся процессов.
- После построения расписания найдите непрерывный интервал, на котором число выполняющихся процессов максимально. Его продолжительность для данных из файла равна 7 мс.
Решение
1. По данным файла для каждого процесса определяем наиболее раннее время начала: оно равно нулю для независимых процессов, а для зависимого процесса — максимальному времени окончания его предшественников.
tнач(B)=maxA→Btок(A)
2. Для каждого процесса отмечаем интервал его выполнения от времени начала до времени окончания. Процессы, не связанные зависимостями в данный момент, выполняются параллельно.
3. Подсчитываем количество одновременно выполняющихся процессов на каждом промежутке между моментами начала и окончания процессов, выбираем максимальное количество и определяем все интервалы, на которых оно достигается.
4. Для данных из прилагаемого файла суммарная продолжительность такого интервала составляет 7 миллисекунд.
tнач(B)=maxA→Btок(A)
2. Для каждого процесса отмечаем интервал его выполнения от времени начала до времени окончания. Процессы, не связанные зависимостями в данный момент, выполняются параллельно.
3. Подсчитываем количество одновременно выполняющихся процессов на каждом промежутке между моментами начала и окончания процессов, выбираем максимальное количество и определяем все интервалы, на которых оно достигается.
4. Для данных из прилагаемого файла суммарная продолжительность такого интервала составляет 7 миллисекунд.
Частые ошибки
- Складывают времена выполнения всех процессов вместо анализа их параллельного выполнения.
- Начинают процесс одновременно с его предшественниками, не дожидаясь получения результатов.
- Учитывают только один из нескольких процессов-предшественников.
Похожие задания
22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · DC04F122В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · E923FA22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · A3580C22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 330C0022В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 10A67122В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · E3251922В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · DAB82122В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 4A47D4
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.