В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или нескольких других процессов — поставщиков данных. Если зависимый процесс получает данные от других процессов (поставщиков данных), то выполнение зависимого процесса не может начаться раньше завершения всех процессов-поставщиков. Длительность процесса не зависит от других параллельно
выполняемых процессов, приостановка выполнения процесса не допускается.
В таблице представлены идентификатор (ID) каждого процесса, его длительность в мс и ID поставщиков данных для зависимых процессов. Для независимых процессов в качестве ID поставщика данных указан 0.
Одновременно может выполняться не более 3 процессов. Если в какой-то момент в системе работает менее 3 процессов, то при наличии готовых к запуску процессов выбирается и запускается тот из них, который имеет минимальный ID.
За какое время будут выполнены все процессы?
В ответе напишите число — требуемое время в мс.
Выполните задания, используя данные из файла ниже:
Добавим в таблицу столбец «Время окончания процесса» и запишем туда длительности независимых процессов. Затем рассчитаем время окончания зависимых процессов. В результате получим таблицу.
Нарисуем время выполняемых процессов:
Расставим процессы так, чтобы зависимые стояли сразу за независимыми процессами.
Начнем двигать вправо процессы так, чтобы всегда было только 3 выполняемых процесса. Первыми будут выполняться процессы 1,2 и 6. Как только завершиться самый короткий процесс (в этой задаче процесс 6), запускаем следующий процесс. Помним, что запущенный процесс должен иметь минимальный ID. Процессы 3, 4 и 5 запустить нельзя, так как они зависят от процесса 2. Запускаем следующий по ID процесс 7. Расставляем далее процессы, следя за тем, чтобы одновременно выполнялось не более 3 процессов, запускались независимые процессы от текущих и с минимальным ID. Получаем следующую таблицу.
Все процессы будут выполнены за 53 мс.
Ответ: 53.