Задание 22: Многопроцессорные системы

Типовая формулировка звучит так: дана совокупность из $N$ процессов, каждый из которых характеризуется идентификатором, временем выполнения в миллисекундах и списком идентификаторов процессов, от которых он зависит. Если список пуст (стоит значение 0), процесс независим и может стартовать в любой момент. Процесс B зависит от процесса A означает, что B не может начаться, пока не завершится A. Все независимые друг от друга процессы могут выполняться параллельно (предполагается неограниченное число процессоров). Требуется найти минимальное время, через которое завершится выполнение всей совокупно …

• Процесс — задача с фиксированным временем выполнения $t$, которая может зависеть от других процессов.
• Зависимость: если B зависит от A, то A должен полностью завершиться до старта B. Такие процессы выполняются строго последовательно.
• Независимые процессы (без общих зависимостей друг от друга) выполняются параллельно — их времена не складываются, а идут «одновременно».
• Время начала процесса определяется формулой: $$T_{start}(B) = \max_{A \in \text{Dep}(B)} T_{finish}(A)$$ где $\text{Dep}(B)$ — множество процессов, от которых зависит B. Если B независим, $T_{start}(B) = 0$.
• Время завершения процесса: $$T_{finish}(B) = T_{start}(B) + t(B)$$
• Итоговый ответ задачи — максимальное время завершения среди всех процессов: $$T_{answer} = \max_{B} T_{finish}(B)$$
• Граф зависимостей процессов — это ориентированный ациклический граф (DAG): вершины — процессы, рёбра идут от A к B, если B зависит от A. Обрабатывать вершины нужно в порядке топологической сортировки: сначала процессы без зависимостей, затем те, чьи «родители» уже обработаны.
• Критический путь — самая длинная по суммарному времени цепочка последовательных зависимых процессов. Именно длина критического пути и есть минимальное время выполнения всей системы.

1. Выписать из таблицы/файла для каждого процесса: ID, время выполнения $t$, список зависимостей (или 0, если процесс независим).
2. Найти все процессы без зависимостей — для них $T_{start} = 0$, $T_{finish} = t$.
3. Определить порядок обработки оставшихся процессов так, чтобы к моменту расчёта процесса B все процессы из его списка зависимостей уже были обработаны (топологическая сортировка).
4. Для каждого следующего процесса B вычислить: $$T_{start}(B) = \max_{A \in \text{Dep}(B)} T_{finish}(A), \qquad T_{finish}(B) = T_{start}(B) + t(B)$$
5. Повторять шаг 4, пока не будут обработаны все процессы.
6. Найти максимум среди всех $T_{finish}$ — это и есть минимальное время выполнения всей совокупности процессов.
7. Записать ответ как целое число миллисекунд.