Определение количества одновременно выполняемых процессов: В файле; 6, 0, 9, 1 · ЕГЭ №22

Условие, ответ и разбор задачи

Многопроцессорные системы

Профиматика Инф.

В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$ , если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$ . В этом случае процессы $A$ и $B$ могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите максимальное количество процессов, которые параллельно выполняются на 9-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.

Типовой пример организации данных в файле

ID процесса $B$	Время выполнения процесса $B$ (мс)	ID процесса(-ов) $A$
1	3	0
2	4	1
3	2	2; 4
4	5	0
5	8	1; 4
6	3	1

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файлы к задаче

ODS · 14 КБ

Скачать

Ответ:

Решение

# Решение на языке Python.
# Файл к задаче даётся в формате .ods — пересохраните его в .txt
# с разделителем «табуляция», первую строку с заголовком удалите.

t = {}                                           # время выполнения процесса
dep = {}                                         # от кого зависит процесс
for line in open('22.txt'):
    i, s, d = line.split('\t')
    t[int(i)] = int(s)
    dep[int(i)] = [] if d.strip() == '0' else [int(x) for x in d.split(';')]

end = {}                                         # миллисекунда окончания
def E(i):
    if i not in end:
        end[i] = max((E(j) for j in dep[i]), default=0) + t[i]
    return end[i]

k = 0
for i in t:
    if E(i) - t[i] + 1 <= 9 <= E(i):             # процесс идёт на 9-й мс
        k += 1
print(k)

Решение через электронные таблицы.

Решение в электронных таблицах смотрите в приложенном файле.

Откроем файл в LibreOffice Calc. Независимые процессы (в третьем столбце 0) начинаются на 1-й мс. Для каждого зависимого процесса время начала равно наибольшему времени окончания процессов, от которых он зависит, плюс 1; время окончания — начало плюс время выполнения минус 1. Остаётся посчитать строки, у которых начало $\le$ 9 и конец $\ge$ 9: =СУММПРОИЗВ((J2:J26<=9)*(K2:K26>=9)).

На 9-й мс одновременно выполняются процессы 10, 13, 15, 16, 17 и 24 — всего 6.

$\textbf{Ответ: 6.}$

Файлы решения

22-54b1ac79

ODS · 25 КБ

Скачать