22. Вычислительные процессы: В файле содержится информация о совокупности N вычислительных…
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.
Типовой пример организации данных в файле:
| ID процесса $B$ | Время выполнения процесса $B$ (мс) | ID процесса(-ов) $A$ |
|---|---|---|
| $1$ | $4$ | $0$ |
| $2$ | $3$ | $0$ |
| $3$ | $1$ | $1$; $2$ |
| $4$ | $7$ | $3$ |
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $2$, $4$, $1$ и $15$ завершатся на $20$, $22$, $24$ и $24$ мс соответственно.
Процесс $5$ зависит от $2$, значит завершится на $20+25=45$ мс. Процесс $11$ зависит от $15$ и завершится на $24+22=46$ мс. Процесс $7$ зависит от $5$ и завершится на $45+18=63$ мс, процесс $8$ зависит от $1$ и $5$ (позже заканчивается $5$) и завершится на $45+22=67$ мс.
Процесс $10$ зависит от $7$ и завершится на $63+19=82$ мс. Процесс $3$ зависит от $10$ и завершится на $82+19=101$ мс. Процесс $9$ зависит от $3$ и $4$: позже заканчивается $3$, значит $9$ завершится на $101+21=122$ мс. Процесс $12$ зависит от $9$ и завершится на $122+24=146$ мс.
Процесс $13$ зависит от $10$ и $12$: позже заканчивается $12$ (на $146$ мс), поэтому $13$ завершится на $146+25=171$ мс. Процесс $16$ зависит от $13$ и завершится на $171+25=196$ мс.
Наконец, процесс $17$ зависит от $14$ и $16$: процесс $14$ закончился давно, ещё на $66$ мс, а $16$ — на $196$ мс, значит $17$ завершится на $196+22=218$ мс. Для сравнения, процесс $6$ зависит от $4$, $5$, $7$ и $8$ и заканчивается на $67+23=90$ мс — намного раньше.
Таким образом, вся совокупность процессов завершится на $218$ мс.
| Время, мс | ID процесса |
|---|---|
| $20$ | $2$ |
| $22$ | $4$ |
| $24$ | $1$, $15$ |
| $45$ | $5$ |
| $46$ | $11$ |
| $63$ | $7$ |
| $66$ | $14$ |
| $67$ | $8$ |
| $82$ | $10$ |
| $90$ | $6$ |
| $101$ | $3$ |
| $122$ | $9$ |
| $146$ | $12$ |
| $171$ | $13$ |
| $196$ | $16$ |
| $218$ | $17$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-20.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)) # 218
Критический путь здесь длинный: $2 \to 5 \to 7 \to 10 \to 3 \to 9 \to 12 \to 13 \to 16 \to 17$. Именно эта цепочка из десяти последовательных процессов и определяет ответ, тогда как остальные ветки заканчиваются вдвое раньше.