ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Параллельные вычисления.
| КЭС: | 1.1 Основные тенденции развития компьютерных технологий. Параллельные вычисления. Многопроцессорные системы. Распределённые вычислительные системы и обработка больших данных |
| Тип ответа: | Краткий ответ |
Ответ: 6
Решение.
Открываем исходный файл ODS. Полная таблица содержит 25 процессов; иллюстративная таблица в тексте задания показывает только формат данных. Для ответа используем именно файл. Все времена ниже указаны в миллисекундах.
Обозначим длительность процесса i через d(i), самое раннее время начала — S(i), завершения — F(i). Время отсчитываем от нуля: независимые процессы начинаются в момент 0 и работают уже на первой миллисекунде.
Процесс может начаться, когда завершатся все его непосредственные предшественники. Поэтому S(i) равно максимуму их времён F. Для независимого процесса S(i) = 0. После начала процесс выполняется непрерывно, так что F(i) = S(i) + d(i).
Сначала рассчитываем независимые процессы, затем те, у которых известны времена завершения всех предшественников. Номер процесса не задаёт порядок вычисления. Параллельные ветви не складываем между собой: в формуле начала нужен максимум.
В таблице ниже процессы расположены в порядке расчёта. Знак «—» означает отсутствие зависимостей. В столбцах S и F показаны численные подстановки.
| ID | Длительность | Предшественники | Начало S | Завершение F |
|---|---|---|---|---|
| 25 | 2 | — | 0 | 0 + 2 = 2 |
| 6 | 1 | — | 0 | 0 + 1 = 1 |
| 2 | 2 | 6, 25 | max(1; 2) = 2 | 2 + 2 = 4 |
| 17 | 4 | — | 0 | 0 + 4 = 4 |
| 23 | 5 | 17 | 4 = 4 | 4 + 5 = 9 |
| 21 | 4 | 2, 23 | max(4; 9) = 9 | 9 + 4 = 13 |
| 1 | 2 | 25, 6, 21 | max(2; 1; 13) = 13 | 13 + 2 = 15 |
| 4 | 2 | 25 | 2 = 2 | 2 + 2 = 4 |
| 18 | 3 | 2, 17, 4 | max(4; 4; 4) = 4 | 4 + 3 = 7 |
| 16 | 4 | 18 | 7 = 7 | 7 + 4 = 11 |
| 3 | 5 | 16 | 11 = 11 | 11 + 5 = 16 |
| 14 | 5 | 4 | 4 = 4 | 4 + 5 = 9 |
| 5 | 4 | 25, 14 | max(2; 9) = 9 | 9 + 4 = 13 |
| 7 | 5 | 25 | 2 = 2 | 2 + 5 = 7 |
| 8 | 6 | 17, 25 | max(4; 2) = 4 | 4 + 6 = 10 |
| 15 | 3 | 7, 21, 23 | max(7; 13; 9) = 13 | 13 + 3 = 16 |
| 9 | 6 | 8, 2, 15 | max(10; 4; 16) = 16 | 16 + 6 = 22 |
| 10 | 4 | 6, 18 | max(1; 7) = 7 | 7 + 4 = 11 |
| 11 | 4 | 18, 16, 9 | max(7; 11; 22) = 22 | 22 + 4 = 26 |
| 12 | 6 | 15 | 16 = 16 | 16 + 6 = 22 |
| 19 | 3 | 21, 6, 5 | max(13; 1; 13) = 13 | 13 + 3 = 16 |
| 13 | 4 | 19, 8 | max(16; 10) = 16 | 16 + 4 = 20 |
| 20 | 3 | 17 | 4 = 4 | 4 + 3 = 7 |
| 22 | 1 | 18, 25, 2 | max(7; 2; 4) = 7 | 7 + 1 = 8 |
| 24 | 2 | 25, 15 | max(2; 16) = 16 | 16 + 2 = 18 |
Проверка расписания: каждая длительность равна F(i) − S(i), а начало не меньше завершения любого предшественника. Все готовые процессы можно запускать одновременно: ограничения на число исполнителей в условии нет.
Докажем, что получены самые ранние времена. Независимый процесс нельзя начать раньше нуля. Если самые ранние завершения его предшественников уже найдены, зависимый процесс не может начаться раньше их максимума. Запуск в этот момент допустим. Продолжая рассуждение по порядку зависимостей, получаем самые ранние начала и завершения всех процессов.
Нужна 6-я миллисекунда: это промежуток от 5 до 6. Процесс работает в течение этой миллисекунды, если S(i) меньше 6, а F(i) не меньше 6. Завершение ровно в момент 6 включается, начало ровно в момент 6 не включается.
Проверяем оба ограничения для всех строк расчётной таблицы. Подходят следующие процессы:
| ID | S | F |
|---|---|---|
| 7 | 2 | 7 |
| 8 | 4 | 10 |
| 14 | 4 | 9 |
| 18 | 4 | 7 |
| 20 | 4 | 7 |
| 23 | 4 | 9 |
Их номера: 7, 8, 14, 18, 20, 23. Количество равно 6.
Проверка исключённых: 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 15, 16, 17, 19, 21, 22, 24, 25. Для каждого из них либо начало не раньше 6, либо завершение раньше 6.
Самое раннее начало каждого процесса прямо задано условием. Поэтому сдвигать процессы для увеличения числа одновременных запусков нельзя: считаем их в уже определённом расписании.
Ответ: 6.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFDC04F1.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.