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