Параллельные процессы: неизвестная длительность
Условие
В таблице приведены сведения о процессах, которые могут выполняться параллельно (данные даны прямо в условии, в мини-версии вместо файла). Для каждого процесса B указаны его идентификатор (ID), время выполнения в миллисекундах и идентификаторы процессов A, от которых он зависит. Процесс B может начаться только после завершения всех процессов A, от которых он зависит; если процесс ни от чего не зависит, в последнем столбце записан 0. Независимые процессы могут выполняться одновременно, количество одновременно выполняемых процессов не ограничено. Временем на переключение между процессами можно пренебречь.
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 3 | 0 |
| 2 | 5 | 0 |
| 3 | 4 | 1 |
| 4 | 6 | 2 |
| 5 | 2 | 3; 4 |
| 6 | x | 1 |
| 7 | 5 | 5 |
| 8 | 3 | 5; 6 |
| 9 | 4 | 7; 8 |
Время выполнения процесса 6 неизвестно и обозначено в таблице буквой x (x — целое положительное число). Определите наибольшее значение x, при котором все процессы могут завершиться не позднее чем через 25 мс от начала выполнения.