Задание 22. Информатика. ЕГЭ. Шастин. 6.11.2024
- Просмотры: 92
- Изменено: 24 ноября 2024
(Л. Шастин) В файле содержится информация о совокупности \(N\) вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс \(B\) зависит от процесса \(A\), если для выполнения процесса \(B\) необходимы результаты выполнения процесса \(A\). В этом случае процессы могут выполняться только последовательно. Все процессы запускаются при первой же возможности, никакие задержки не допускаются. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение \(0\).
Определите, какое количество процессов не может быть завершено за первые \(T=100\) мс с момента запуска первого процесса.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 2 | 0 |
| 2 | 4 | 0 |
| 3 | 1 | 1;2 |
| 4 | 7 | 3 |
Для приведённого выше примера при \(T=6\) мс процессы № 1, 2 и 3 успеют завершиться, если каждый из них будет запущен при первой же возможности. Процесс же №4 в лучшем случае успеет завершиться только по прошествии \(12\) мс. Ответ для примера: \(1.\)
Решение:
Построим временную диаграмму для процессов, которые начинаются раньше, чем \(100\) мс.
Видим, что процесс 10 завершится позже, чем через \(100\) мс. Отметим его в таблице красным цветом. Отметим также красным цветом и те процессы, которые зависят как от него, так и от его потомков. Всего таких процессов \(10.\)
Ответ: \(10\)