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