Задание 22 ЕГЭ по информатике · 64212F
Параллельные процессы: сколько и как долгоВысокаяКЭС 1.1
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Типовой пример организации данных в файле
Определите максимальное количество процессов, которые параллельно выполняются на 23-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
Например, для приведённой таблицы на 6-й мс параллельно выполняются три процесса. Это процессы 2, 5 и 6.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Типовой пример организации данных в файле
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 3 | 0 |
| 2 | 4 | 1 |
| 3 | 2 | 2; 4 |
| 4 | 5 | 0 |
| 5 | 8 | 1; 4 |
| 6 | 3 | 1 |
Определите максимальное количество процессов, которые параллельно выполняются на 23-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
Например, для приведённой таблицы на 6-й мс параллельно выполняются три процесса. Это процессы 2, 5 и 6.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
К заданию прилагается файл с данными — скачайте его в задании внутри Precettore.
Показать ответ
1
Подсказки (3)
- Для каждого процесса определите самое раннее время начала по временам окончания всех его предшественников.
- Если процесс зависит от нескольких процессов, его начало равно максимуму времён их окончания.
- Постройте интервалы выполнения процессов и проверьте, какие из них содержат 23-ю миллисекунду. Максимальное количество таких процессов равно 1.
Решение
1. По данным прилагаемого файла для каждого процесса последовательно определяем самое раннее время начала: независимые процессы начинают выполняться с первой миллисекунды, а зависимые — после завершения всех указанных предшественников.
sB=maxA∈Pred(B)fA+1
2. Для каждого процесса вычисляем последнюю миллисекунду выполнения по формуле: время окончания равно времени начала плюс длительность минус единица.
fB=sB+tB−1
3. Проверяем интервалы выполнения процессов на 23-й миллисекунде и подсчитываем количество процессов, для которых sB≤23≤fB.
4. Согласно данным файла, на 23-й миллисекунде выполняется один процесс.
sB=maxA∈Pred(B)fA+1
2. Для каждого процесса вычисляем последнюю миллисекунду выполнения по формуле: время окончания равно времени начала плюс длительность минус единица.
fB=sB+tB−1
3. Проверяем интервалы выполнения процессов на 23-й миллисекунде и подсчитываем количество процессов, для которых sB≤23≤fB.
4. Согласно данным файла, на 23-й миллисекунде выполняется один процесс.
Частые ошибки
- Считать процесс выполняющимся в момент, когда он уже завершился.
- Начинать нумерацию миллисекунд с нуля.
- Учитывать только одну зависимость, если у процесса их несколько.
- Допускать прерывание процесса и возобновлять его позже.
Похожие задания
22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 09605522В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · DC04F122В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · E923FA22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · A3580C22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 330C0022В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 777B7822В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · 10A67122В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Параллельные процессы: сколько и как долго · E32519
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.