22. Вычислительные процессы: В файле содержится информация о совокупности N вычислительных…
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.
Типовой пример организации данных в файле:
| ID процесса $B$ | Время выполнения процесса $B$ (мс) | ID процесса(-ов) $A$ |
|---|---|---|
| $101$ | $4$ | $0$ |
| $102$ | $3$ | $0$ |
| $103$ | $1$ | $101$; $102$ |
| $104$ | $7$ | $103$ |
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Расписываем отрезок работы каждого процесса: он стартует сразу после окончания последнего из тех, от которых зависит, и занимает миллисекунды с $f-d+1$ по $f$, где $f$ — момент завершения, $d$ — длительность.
Независимые процессы $101$, $107$ и $108$ занимают мс $1$–$7$, $1$–$7$ и $1$–$18$. Процессы $102$ и $103$ зависят от $101$ и стартуют после $7$ мс: $102$ занимает мс $8$–$22$, $103$ — мс $8$–$23$. Процессы $109$ и $111$ зависят от $108$ и стартуют после $18$ мс: $109$ занимает мс $19$–$28$, $111$ — мс $19$–$25$. Процесс $104$ зависит от $103$ и $107$, позже заканчивается $103$ (на $23$ мс), значит $104$ занимает мс $24$–$33$; от него зависят $105$ (мс $34$–$46$) и $106$ (мс $34$–$37$). Процесс $112$ зависит от $111$ и занимает мс $26$–$29$, а процесс $110$ зависит от $109$ и занимает мс $29$–$47$.
Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. На первых восемнадцати миллисекундах их всегда три. На $19$-й мс к процессам $102$ и $103$ добавляются $109$ и $111$, а $108$ как раз закончился — становится четыре. Столько же держится до $22$-й мс включительно, а на $23$-й мс процесс $102$ уже закончился, и остаётся три. Больше четырёх нигде не набирается: дальше по файлу счётчик опускается до трёх и двух.
Таким образом, максимальное количество одновременно выполняемых процессов равно $4$, и держится оно ровно на отрезке с $19$ по $22$ мс, то есть $4$ мс.
| Процесс | Занятые мс |
|---|---|
| $101$, $107$ | $1$–$7$ |
| $108$ | $1$–$18$ |
| $102$ | $8$–$22$ |
| $103$ | $8$–$23$ |
| $109$ | $19$–$28$ |
| $111$ | $19$–$25$ |
| $104$ | $24$–$33$ |
| $112$ | $26$–$29$ |
| $110$ | $29$–$47$ |
| $105$ | $34$–$46$ |
| $106$ | $34$–$37$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-14.ods', engine='odf', header=None, skiprows=1)
t, dep = {}, {}
for _, row in df.iterrows():
pid = int(row[0])
t[pid] = int(row[1])
s = str(row[2]).replace(' ', '').strip()
dep[pid] = [] if s == '0' else [int(x) for x in s.split(';')]
@lru_cache(None)
def finish(p): # момент завершения процесса p
return t[p] + max([finish(d) for d in dep[p]], default=0)
T = max(finish(p) for p in t)
cnt = [0] * (T + 2) # сколько процессов идёт на каждой мс
for p in t:
for ms in range(finish(p) - t[p] + 1, finish(p) + 1):
cnt[ms] += 1
M = max(cnt[1:T+1]) # максимум одновременных процессов
best = cur = 0 # самая длинная цепочка мс со значением M
for ms in range(1, T + 1):
cur = cur + 1 if cnt[ms] == M else 0
best = max(best, cur)
print(best) # 4
Здесь максимум достигается лишь в одном месте, поэтому и отрезок единственный. Вся совокупность процессов завершается на $47$ мс.