Тип 22 № 55609 
Многопроцессорные системы. Задания для подготовки
i
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов — поставщиков данных. Все независимые процессы (не имеющие поставщиков данных) запускаются в начальный момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то выполнение процесса B начинается сразу же после завершения процесса A. Количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
Задание 22
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите количество активных процессов через 150 мс после запуска первого процесса.
Решение. Надо разделить данные в столбце «ID поставщиков данных» для тех процессов, где есть зависимость от двух процессов. Для этого выделим столбец С, далее — меню «Данные — Текст» по столбцам. В меню мастера разделения текста по столбцам последовательно выберем «Формат данных с разделителями», далее «Символ разделитель: точка с запятой». Формат данных столбца «Общий».
В ячейку A102 впишем 0. Теперь посчитаем время выполнения процессов, для этого в ячейку E2 впишем формулу:
=B2+МАКС(ВПР(C2;A:E;5;0);ВПР(D2;A:E;5;0)),
где B2 — время самого процесса, а функция ВПР ищет время процесса, от которого зависит процесс А. Скопируем эту формулу во все ячейки диапазона E2:E101.
Теперь найдем количество активных процессов через 150 мс после запуска первого процесса, для этого нам необходимо, чтобы время окончания процесса было больше или равно 150, а также, чтобы разница времени окончания и времени выполнения была меньше или равна 150, так как сам процесс мог начаться позже 150 мс, а нам необходимы лишь процессы, которые были активны в момент 150 мс. Для этого впишем в ячейку F2 формулу:
=ЕСЛИ(И(E2>=150;E2-B2<=150);1;0)
и протянем её до конца таблицы. В ячейку G2 запишем =СУММ(F2:F101) и получим ответ — 12.
Ответ: 12.
Приведём решение Владимира Артамонова на языке Python.
with open("22.txt") as file:
processes = {"0": range(0, 1)}
for line in file.readlines():
num, time, sub = line.split()
start_time = max([max(processes[i]) for i in sub.split(";")])
processes[num] = range(start_time, start_time + int(time) + 1)
counter = 0
for time in processes.values():
if 150 in time:
counter += 1
print(counter)
Примечание.
Для считывания информации из файла необходимо конвертировать его из xlsx в txt.
Ответ: 12
