В файле содержится информация о совокупности 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 готовы к выполнению, но запустятся только процессы 5 (пусть на ядре I) и 1 (на ядре II) как имеющие большее время выполнения. При этом процесс 1 завершится через 4 мс после старта, и на освободившемся ядре II начнётся выполнение процесса 2. Оно продлится 3 мс и завершится через 4 + 3 = 7 мс после старта. Процесс 5 завершится через 5 мс после старта, но процесс 3 может быть запущен только после завершения процессов 1 и 2, поэтому ядро I останется свободным. Заметим, что процессы 3 и 4 выполняются последовательно и могут быть выполнены на одном и том же ядре. К моменту завершения процесса на ядре I был выполнен 1 процесс (ID 5), а на ядре II — 2 процесса (ID 1 и 2). Тогда максимальное число процессов, выполненных на одном ядре, будет достигнуто, если процессы 3 и 4 запустить на ядре II, и составит 4. Процесс 3 продлится 1 мс и закончит выполнение через 7 + 1 = 8 мс после старта. Процесс 4 продлится 7 мс и завершится через 8 + 7 = 15 мс после старта. Таким образом, вычисления завершились через 15 мс. Ответ будем сумма 15 и 4 (наибольшее число процессов на одном ядре), т.е. 19.
ФАЙЛ К ЗАДАНИЮ