В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор
процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
|---|---|---|
| 101 | 4 | 0 |
| 102 | 3 | 0 |
| 103 | 1 | 101; 102 |
| 104 | 7 | 103 |
Определите максимальную продолжительность отрезка времени
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Выполните задания, используя данные из файла ниже:
Добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
Далее рассчитаем время выполнения оставшихся процессов:
f(103) = 1 + max(f(101), f(102)) = 5;
f(104) = 5 + f(103) = 10;
f(105) = 7 + f(103) = 12;
f(106) = 3 + f(104) = 13;
f(107) = 1 + max(f(105), f(106)) = 14;
f(108) = 2 + f(107) = 16;
f(111) = 16 + f(109) = 24;
f(112) = 5 + f(110) = 11;
f(113) = 14 + max(f(111), f(114)) = 38;
f(114) = 14 + f(109) = 22.
Построим диаграмму выполнения каждого процесса.
Поскольку независимые процессы можно начинать с любого времени, попробуем добиться максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение пяти процессов:
Максимальный результат — 7.
Если рассмотреть другие процессы, то больше времени сделать не получится.
Ответ: 7.