Тип 22 № 48470 
Многопроцессорные системы. Задания для подготовки
i
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов — поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение не раньше чем через 5 мс после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
Задание 22
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите, за какое минимальное время можно выполнить все процессы. В ответе запишите целое число — минимальное время в мс.
Решение. Для начала проведем сортировку данных, чтобы отделить не зависимые процессы, зависимые от одного процесса и зависимые от двух процессов вычисления. Для этого выделим первые три столбца, а затем выберем меню «Данные — Сортировка» и отсортируем по возрастанию.
Далее нам надо разделить данные в столбце «ID поставщиков данных» для тех процессов, где есть зависимость от двух процессов. Для этого выделим столбец С, далее — меню «Данные — Текст» по столбцам. В меню мастера разделения текста по столбцам последовательно выберем «Формат данных с разделителями», далее «Символ разделитель: точка с запятой». Формат данных столбца «Общий».
В столбце E будем считать общее время на выполнение процесса. Для независимых процессов перенесем данные из столбца B. Введем в ячейку E67 формулу =B67 и скопируем её во все строки в диапазоне E67:E101.
Теперь посчитаем время у процессов зависящих от одного процесса. Для этого в ячейке E2 введем формулу =B2+5+ВПР(C2;A:E;5;0), где B2 — время самого процесса, 5 — время после завершения процесса A (по условию задачи), а функция ВПР ищет время процесса, от которого зависит процесс А. Далее скопируем формулу во все ячейки диапазона E2:E37.
Далее будем считать время процессов, зависящих от 2 процессов. Для этого введем в ячейку E38 формулу:
=B38+5+МАКС(ВПР(C38;A:E;5;0);ВПР(D38;A:E;5;0)).
Скопируем формулу во все ячейки диапазона E38:E66.
Найдем самый длительный процесс введя формулу =МАКС(E2:E101), это и будет минимальное время выполнения всех процессов.
Ответ: 597.
Приведём решение Михаила Глинского на языке Python.
res={'0':0}
f=open('22.txt')
for s in f:
n,t,*FF=s.split()
if len(FF)==0:
res[n]=int(t)
else:
res[n]=int(t)+max([res[i]for i in FF])+5
print(max(res.values()))
Примечание. Предварительно удаляем в файле 1 строку и делаем «Данные»>«Текс по столбцам»>разделители ";".
Cохраняем текст как текст MSDOS.
Ответ: 597
PDF-версии: