Задание 22 ЕГЭ по информатике — Многопроцессорные системы: расписание процессов

Решение.
Нарисуем время выполняемых процессов:
Начнем двигать вправо процессы так, чтобы всегда было только 3 выполняемых процесса и не больше, при этом соблюдая условие задачи.
Все процессы будут выполнены за 42 мс.
Приведем решение на языке Python.
import collections
def solve():
# Загрузка данных из файла
with open("22dz.txt", "r") as f:
processes_data = {}
for line in f:
parts = line.strip().split('\t')
pid = int(parts[0])
duration = int(parts[1])
providers = [] if parts[2] == '0' else [int(p) for p in parts[2].split(',')]
processes_data[pid] = {"duration": duration, "providers": providers}
current_time = 0
running = {} # {pid: end_time}
ready = collections.deque()
completed = set()
# Создаем зависимости для каждого процесса
dependencies = {pid: set(data["providers"]) for pid, data in processes_data.items()}
# Изначально запускаем процессы без зависимостей
for pid, deps in dependencies.items():
if not deps:
ready.append(pid)
ready = collections.deque(sorted(ready))
while len(completed)

42

Решение.
Процесс 1016 зависит от процесса 1003, а процесс 1003 зависит от процессов 1009 и 1013. 1009 является независимым процессом. Процесс 1013 зависит от 1006, а процесс 1006 зависит от процесса 1021, который является независимым процессом. Минимальное время (в мс), за которое завершится процесс 1013 равно сумме времен процессов 63.

63