Шешімі: Параллельное выполнение процессов
В прилагаемом файле содержится информация о совокупности вычислительных процессов, которые могут выполняться параллельно или последовательно. Для каждого процесса указаны время выполнения и ID процессов, от которых он зависит. Каждый процесс начинается в самое раннее допустимое время. Определите максимальное количество процессов, которые параллельно выполняются на 23-й миллисекунде. Нумерация миллисекунд начинается с 1.
Процесс B может начаться только после завершения всех процессов, от которых он зависит. Приостановка выполнения процесса не допускается.
Шешім по шагам
4 қадамПо данным прилагаемого файла для каждого процесса последовательно определяем самое раннее время начала: независимые процессы начинают выполняться с первой миллисекунды, а зависимые — после завершения всех указанных предшественников.
$$s_B = \max_{A \in Pred(B)} f_A + 1$$Для каждого процесса вычисляем последнюю миллисекунду выполнения по формуле: время окончания равно времени начала плюс длительность минус единица.
$$f_B = s_B + t_B - 1$$Проверяем интервалы выполнения процессов на 23-й миллисекунде и подсчитываем количество процессов, для которых $s_B \leq 23 \leq f_B$.
Согласно данным файла, на 23-й миллисекунде выполняется один процесс.
Где здесь ошибаются
Считать процесс выполняющимся в момент, когда он уже завершился.
Начинать нумерацию миллисекунд с нуля.
Учитывать только одну зависимость, если у процесса их несколько.
Допускать прерывание процесса и возобновлять его позже.