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$, $102$ и $110$ занимают мс $1$–$14$, $1$–$3$ и $1$–$8$. Процесс $104$ зависит от $102$ и работает с $4$ по $14$ мс. Процессы $111$ и $112$ зависят от $110$ и стартуют после $8$ мс: $111$ занимает мс $9$–$24$, $112$ — мс $9$–$16$. Процесс $103$ зависит от $101$ и $102$, позже заканчивается $101$ (на $14$ мс), поэтому $103$ занимает единственную $15$-ю мс. От него зависят $105$ (мс $16$–$28$) и $106$ (мс $16$–$20$), а от $106$ — процесс $107$ (мс $21$–$23$). Процесс $113$ зависит от $112$ и занимает мс $17$–$30$. Наконец, $108$ работает на $29$-й мс, а $109$ — на мс $30$–$31$.
Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он дважды. Первый раз — на мс с $9$ по $14$, когда параллельно идут $101$, $104$, $111$ и $112$: это отрезок длиной $6$ мс. Затем на $15$-й мс остаются только $103$, $111$ и $112$, то есть три процесса, и цепочка обрывается. Второй раз четвёрка набирается с $16$-й мс — работают $105$, $106$, $111$ и $112$ — и держится до $23$-й мс включительно, хотя состав по ходу меняется: с $17$-й мс вместо $112$ подключается $113$, а с $21$-й мс вместо $106$ идёт $107$. Это отрезок с $16$ по $23$ мс длиной $8$ мс. На $24$-й мс процесс $107$ уже закончился, и параллельных остаётся три.
Таким образом, максимальное количество одновременно выполняемых процессов равно $4$, а самый длинный отрезок, на котором это количество держится, длится $8$ мс.
| Процесс | Занятые мс |
|---|---|
| $101$ | $1$–$14$ |
| $102$ | $1$–$3$ |
| $110$ | $1$–$8$ |
| $104$ | $4$–$14$ |
| $111$ | $9$–$24$ |
| $112$ | $9$–$16$ |
| $103$ | $15$ |
| $105$ | $16$–$28$ |
| $106$ | $16$–$20$ |
| $113$ | $17$–$30$ |
| $107$ | $21$–$23$ |
| $108$ | $29$ |
| $109$ | $30$–$31$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-09.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]).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) # 8
Обратите внимание: спрашивается не про конкретный набор процессов, а про количество. Состав четвёрки внутри отрезка с $16$ по $23$ мс меняется трижды, но одновременно работающих всё время ровно четыре, поэтому весь отрезок считается целиком.