ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Параллельные вычисления.
| КЭС: | 1.1 Основные тенденции развития компьютерных технологий. Параллельные вычисления. Многопроцессорные системы. Распределённые вычислительные системы и обработка больших данных |
| Тип ответа: | Краткий ответ |
Ответ: 21
Решение.
В приложенной таблице 25 процессов. Первый столбец содержит их идентификаторы, второй — длительности в миллисекундах, третий — идентификаторы всех необходимых предшественников. Ноль в третьем столбце означает отсутствие предшественников. Типовой пример из условия не заменяет данные файла.
Начальный момент обозначим 0. Пусть d(B) — длительность процесса B, S(B) — время его начала, F(B) — время окончания. Процесс занимает промежуток от S(B) включительно до F(B) не включительно. Его результат доступен уже в момент F(B); следующий процесс может начаться в этот же момент.
Для самого раннего допустимого запуска используем правила:
S(B) = 0, если предшественников нет;
S(B) = max(F(A)), где максимум берётся по всем предшественникам A;
F(B) = S(B) + d(B).
Длительности разных предшественников не складываем: они могут работать параллельно. Но ждать требуется завершения каждого, поэтому выбираем самое позднее окончание. Строки вычисляем после их предшественников, даже если в файле они расположены в другом порядке.
Эти времена достижимы одновременным запуском всех готовых процессов. Раньше запустить очередной процесс нельзя: хотя бы один необходимый результат ещё отсутствует. Последовательно применяя это рассуждение по зависимостям, получаем минимальные времена окончания каждого процесса.
Проверка зависимостей и длительностей. Полный расчёт самого раннего расписания, все времена в мс:
| ID | d | Предшественники | S | F = S + d |
|---|---|---|---|---|
| 101 | 1 | нет | 0 | 0 + 1 = 1 |
| 102 | 5 | 101 | max(1) = 1 | 1 + 5 = 6 |
| 103 | 1 | 106; 108 | max(10; 1) = 10 | 10 + 1 = 11 |
| 104 | 5 | 115; 106 | max(25; 10) = 25 | 25 + 5 = 30 |
| 105 | 5 | 122; 113 | max(12; 8) = 12 | 12 + 5 = 17 |
| 106 | 4 | 102 | max(6) = 6 | 6 + 4 = 10 |
| 107 | 3 | 112 | max(1) = 1 | 1 + 3 = 4 |
| 108 | 1 | нет | 0 | 0 + 1 = 1 |
| 109 | 1 | 113; 106 | max(8; 10) = 10 | 10 + 1 = 11 |
| 110 | 1 | 107 | max(4) = 4 | 4 + 1 = 5 |
| 111 | 3 | 108; 103 | max(1; 11) = 11 | 11 + 3 = 14 |
| 112 | 1 | нет | 0 | 0 + 1 = 1 |
| 113 | 5 | 120 | max(3) = 3 | 3 + 5 = 8 |
| 114 | 6 | 111; 124 | max(14; 13) = 14 | 14 + 6 = 20 |
| 115 | 4 | 119 | max(21) = 21 | 21 + 4 = 25 |
| 116 | 4 | 101; 109 | max(1; 11) = 11 | 11 + 4 = 15 |
| 117 | 6 | 106; 107 | max(10; 4) = 10 | 10 + 6 = 16 |
| 118 | 3 | 101 | max(1) = 1 | 1 + 3 = 4 |
| 119 | 5 | 120; 117 | max(3; 16) = 16 | 16 + 5 = 21 |
| 120 | 2 | 112; 108 | max(1; 1) = 1 | 1 + 2 = 3 |
| 121 | 1 | 104 | max(30) = 30 | 30 + 1 = 31 |
| 122 | 6 | 102; 120 | max(6; 3) = 6 | 6 + 6 = 12 |
| 123 | 1 | 117 | max(16) = 16 | 16 + 1 = 17 |
| 124 | 2 | 103 | max(11) = 11 | 11 + 2 = 13 |
| 125 | 5 | 108 | max(1) = 1 | 1 + 5 = 6 |
Нужно найти первый момент, к которому завершилось не менее 22 процессов. Упорядочим все значения F по возрастанию, сохраняя одинаковые окончания разных процессов:
1; 1; 1; 3; 4; 4; 5; 6; 6; 8; 10; 11; 11; 12; 13; 14; 15; 16; 17; 17; 20; 21; 25; 30; 31.
На позиции 22 стоит 21. Строго раньше этого момента завершается 21 процессов, а к этому моменту включительно — 22. Поэтому раньше нужного количества ещё нет, а в момент 21 мс оно уже достигнуто. Одновременные окончания считаем по отдельности.
Ответ: 21.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF159297.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.