В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Известно, что независимые процессы начали выполняться сразу, остальные — как только их выполнение стало возможно.
Вычислительное устройство имеет 4 вычислительных ядра. Каждый из параллельных процессов выполняется на отдельном ядре. Будем говорить, что ядро простаивает, если ядро не выполняет никакой процесс и при этом не вся совокупность процессов выполнена. Из готовых к выполнению процессов в первую очередь запускаются процессы с наименьшим временем выполнения (если таких больше, чем свободных ядер, приоритет имеют процессы с меньшими ID).
Известно, что выполнение всей совокупности процессов заняло минимальное возможное время. Определите суммарное время простоя всех ядер.
Типовой пример организации данных в файле:
| ID процесса B |
Время выполнения процесса B (мс) |
ID процесса(ов) A |
| 1 |
4 |
0 |
| 2 |
3 |
0 |
| 3 |
1 |
1; 2 |
| 4 |
7 |
3 |
| 5 |
5 |
0 |
Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению, но запустятся только процессы 1 (пусть на ядре I) и 2 (на ядре II) как имеющие меньшее время выполнения. При этом процесс 2 завершится через 3 мс. Поскольку процесс 3 может начаться только после завершения обоих процессов 1 и 2, на освободившемся ядре II запускается процесс 5, который завершится через 3 + 5 = 8 мс после старта. Процесс 1 завершится через 4 мс после старта и позволит начать выполнение процесса 3 на освободившемся ядре I. Процесс 3 завершится через 4 + 1 = 5 мс после старта. На освободившемся ядре I начнётся выполнение процесса 4, которое продлится 7 мс и закончится через 5 + 7 = 12 мс после начала вычислений. Таким образом, ядро I не простаивало, а ядро II начало простаивать через 8 мс после старта и простаивало до конца вычислений через 12 мс после старта. Тогда суммарное время простоя всех ядер равно времени простоя ядра II и составляет 12 - 8 = 4 мс. Ответ: 4.
ФАЙЛ К ЗАДАНИЮ