В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или нескольких других процессов – поставщиков данных. Если зависимый процесс получает данные от других процессов (поставщиков данных), то выполнение зависимого процесса не может начаться раньше завершения всех процессов поставщиков. Длительность процесса не зависит от других параллельно выполняемых процессов, приостановка выполнения процесса не допускается.
В таблице представлены идентификатор (ID) каждого процесса, его длительность в мс и ID поставщиков данных для зависимых процессов. Для независимых процессов в качестве ID поставщика данных указан 0.
В момент, когда процесс готов к запуску, он ставится в очередь. Если несколько процессов оказываются готовы к запуску одновременно, первым ставится в очередь тот процесс, у которого меньше ID.
Одновременно может выполняться не более 3 процессов. Если в какой-то момент в системе работает менее 3 процессов, то при наличии готовых к запуску процессов выбирается и запускается первый процесс из очереди.
За какое время будут выполнены все процессы?
В ответе напишите число — требуемое время в мс.
Нарисуем время выполняемых процессов:
Начнем двигать вправо процессы так, чтобы всегда было только 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) < len(processes_data):
# Обновляем время до следующего завершения процесса
if running:
current_time = min(running.values())
# Обработка завершенных процессов
finished = [pid for pid, t in running.items() if t <= current_time]
for pid in finished:
del running[pid]
completed.add(pid)
# Обновляем зависимости других процессов после завершения
for p, deps in dependencies.items():
if p not in completed and p not in running and p not in ready:
if pid in deps:
deps.remove(pid)
if not deps:
ready.append(p)
ready = collections.deque(sorted(ready))
# Запускаем новые процессы, если есть свободные слоты
while len(running) < 3 and ready:
pid = ready.popleft()
end_time = current_time + processes_data[pid]["duration"]
running[pid] = end_time
# Если ничего не происходит, и процессы застряли
if not running and not ready and len(completed) < len(processes_data):
break # Задача застряла, невозможно завершить
return current_time
print(solve())
Ответ: 42.