22. Вычислительные процессы: В файле содержится информация о совокупности N вычислительных…
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример организации данных в файле:
| 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$ |
Для приведённой таблицы процесс $3$ начинается на $8$-й мс, заканчивается на $9$-й мс.
Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$ и $12$ завершатся на $3$, $4$ и $6$ мс соответственно.
Процесс $3$ зависит от $2$ и завершится на $4+1=5$ мс, процесс $19$ тоже зависит от $2$ и завершится на $6$ мс. Процесс $5$ зависит от $12$ и завершится на $6+1=7$ мс. Процесс $6$ зависит от $3$ и $12$: позже заканчивается $12$ (на $6$ мс), значит $6$ завершится на $6+6=12$ мс.
От процесса $6$ дальше зависит целая ветка. Процессы $11$, $17$ и $24$ завершаются на $14$ мс, процесс $20$ — на $15$ мс. Процесс $18$ зависит от $11$ и $2$, стартует после $14$ мс и завершается на $14+6=20$ мс. Процесс $9$ зависит от $3$, $17$ и $12$ и завершается на $14+6=20$ мс.
Процесс $8$ зависит от $20$, $6$ и $18$: позже заканчивается $18$ (на $20$ мс), значит $8$ завершится на $20+3=23$ мс. От него зависит $23$, который завершится на $23+2=25$ мс. Процесс $4$ зависит от $5$ и $18$ и завершится на $20+6=26$ мс.
Процесс $13$ зависит от $4$ и $23$: позже заканчивается $4$ (на $26$ мс), поэтому $13$ завершится на $26+3=29$ мс. И наконец, процесс $21$ зависит от $6$, $1$ и $13$, стартует после $29$ мс и завершается на $29+5=34$ мс. Для сравнения, вторая длинная ветка идёт через процесс $7$ ($28$ мс) и $16$ ($32$ мс) — она короче.
Таким образом, вся совокупность процессов завершится на $34$ мс.
| Время, мс | ID процесса |
|---|---|
| $3$ | $1$ |
| $4$ | $2$ |
| $5$ | $3$ |
| $6$ | $12$, $19$ |
| $7$ | $5$ |
| $8$ | $25$ |
| $12$ | $6$ |
| $14$ | $11$, $17$, $24$ |
| $15$ | $20$ |
| $19$ | $15$ |
| $20$ | $9$, $18$ |
| $23$ | $8$ |
| $25$ | $10$, $22$, $23$ |
| $26$ | $4$ |
| $28$ | $7$, $14$ |
| $29$ | $13$ |
| $32$ | $16$ |
| $34$ | $21$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-16.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)
print(max(finish(p) for p in t)) # 34
Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Ответ — максимум по всем процессам, потому что вся совокупность закончится тогда, когда закончится самый поздний из них.