ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Параллельные вычисления.
| КЭС: | 1.1 Основные тенденции развития компьютерных технологий. Параллельные вычисления. Многопроцессорные системы. Распределённые вычислительные системы и обработка больших данных 1.2 Принципы построения и аппаратные компоненты компьютерных сетей. Сетевые протоколы. Сеть Интернет. Адресация в сети Интернет. Протоколы стека TCP/IP. Система доменных имён. Разделение IP-сети на подсети с помощью масок подсетей 1.3 Файловая система. Поиск в файловой системе. Принципы размещения и именования файлов в долговременной памяти. Шаблоны для описания групп файлов |
| Тип ответа: | Краткий ответ |
Ответ: 189
Решение.
В приложенной таблице 17 процессов. Первый столбец содержит их идентификаторы, второй — длительности в миллисекундах, третий — идентификаторы всех необходимых предшественников. Ноль в третьем столбце означает отсутствие предшественников. Типовой пример из условия не заменяет данные файла.
В этом файле длительности во втором столбце заданы формулами: к идентификатору прибавляется 17. Поэтому процессы 1–17 длятся соответственно 18–34 мс. В расчёте используем полученные значения формул.
Начальный момент обозначим 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 |
|---|---|---|---|---|
| 1 | 18 | нет | 0 | 0 + 18 = 18 |
| 2 | 19 | нет | 0 | 0 + 19 = 19 |
| 3 | 20 | 1; 12 | max(18; 29) = 29 | 29 + 20 = 49 |
| 4 | 21 | нет | 0 | 0 + 21 = 21 |
| 5 | 22 | 2 | max(19) = 19 | 19 + 22 = 41 |
| 6 | 23 | 5; 7; 8; 15 | max(41; 65; 43; 107) = 107 | 107 + 23 = 130 |
| 7 | 24 | 5 | max(41) = 41 | 41 + 24 = 65 |
| 8 | 25 | 1 | max(18) = 18 | 18 + 25 = 43 |
| 9 | 26 | 3; 4 | max(49; 21) = 49 | 49 + 26 = 75 |
| 10 | 27 | 7 | max(65) = 65 | 65 + 27 = 92 |
| 11 | 28 | 9 | max(75) = 75 | 75 + 28 = 103 |
| 12 | 29 | нет | 0 | 0 + 29 = 29 |
| 13 | 30 | 10; 12 | max(92; 29) = 92 | 92 + 30 = 122 |
| 14 | 31 | 11; 15 | max(103; 107) = 107 | 107 + 31 = 138 |
| 15 | 32 | 9 | max(75) = 75 | 75 + 32 = 107 |
| 16 | 33 | 13 | max(122) = 122 | 122 + 33 = 155 |
| 17 | 34 | 14; 16 | max(138; 155) = 155 | 155 + 34 = 189 |
Вся система заканчивает работу, когда выполнен последний процесс. Следовательно, T = max(F(B)) = 189 мс.
Проверим нижнюю границу цепочкой обязательных зависимостей:
2 → 5 → 7 → 10 → 13 → 16 → 17.
Эти процессы должны выполняться последовательно, их суммарная длительность равна
19 + 22 + 24 + 27 + 30 + 33 + 34 = 189 мс.
Быстрее закончить все процессы невозможно. Полная таблица показывает расписание, достигающее этой границы.
Ответ: 189.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFE4C7B9.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.