Решение: Параллельное выполнение процессов
В прилагаемом файле приведена таблица вычислительных процессов: для каждого процесса указаны его идентификатор, время выполнения в миллисекундах и идентификаторы процессов, от которых он зависит. Процессы могут выполняться параллельно, но зависимый процесс начинается только после завершения всех процессов, от которых он зависит.
Определите максимальное количество процессов, которые параллельно выполняются на 16-й миллисекунде. Каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
Решение по шагам
4 шагаДля каждого процесса по таблице определяем все процессы, от которых он зависит. Независимые процессы могут начинаться с первой миллисекунды.
Для зависимого процесса вычисляем самое раннее начало: оно следует после окончания самого позднего из процессов-зависимостей. Если последний из них заканчивается на миллисекунде $k$, процесс начинается на миллисекунде $k+1$.
Для каждого процесса отмечаем интервал его выполнения и проверяем, содержит ли этот интервал 16-ю миллисекунду.
Подсчёт процессов, выполняющихся на 16-й миллисекунде, даёт 7.
Где здесь ошибаются
Считать зависимый процесс завершённым в ту же миллисекунду, в которую завершается его последний предшественник.
Учитывать только одну зависимость, если у процесса их несколько.
Считать процесс выполняющимся на миллисекунде после окончания его интервала.
Начинать нумерацию миллисекунд с нуля.