22. Вычислительные процессы: Определите минимальное время (в мс), за которое завершатся 17…
В файле содержится информация о совокупности $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$ |
Определите минимальное время (в мс), за которое завершатся $17$ процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Минимальное время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число – количество мс.
Например, для приведённой таблицы найдём время, за которое завершатся $3$ процесса. Минимальное время, которое для этого требуется, – $7$ мс. За это время завершатся процессы $1$, $2$ и $4$.
Составим таблицу, на какой мс завершится каждый из процессов, и будем накапливать их количество. Искомое время — момент завершения $17$-го по счёту процесса.
Независимые процессы $121$, $106$ и $112$ завершаются на $2$, $3$ и $4$ мс. Процесс $125$ зависит от $112$ и завершается на $4+1=5$ мс. На $6$ мс заканчиваются сразу три процесса: $103$ (зависит от $125$), а также $116$ и $122$ (оба зависят от $112$) — всего завершено $7$.
Дальше процессы $105$ и $115$ зависят от $121$ и завершаются на $2+6=8$ мс, их становится $9$. На $9$ мс заканчиваются $108$ (зависит от $106$ и $112$, стартует после $4$ мс), $111$ (зависит от $125$ и $121$, стартует после $5$ мс) и $102$ (зависит от $115$ и $106$, стартует после $8$ мс) — всего $12$.
На $11$ мс завершаются $109$ и $124$, завершённых становится $14$. И наконец на $12$ мс заканчиваются сразу три процесса: $107$ (зависит от $115$ и $109$), $117$ (зависит от $115$) и $120$ (зависит от $109$ и $115$). Все они стартуют после $11$ мс либо после $8$ мс, и вместе доводят счёт до $17$.
Значит минимальное время, за которое завершатся $17$ процессов, равно $12$ мс.
| Время, мс | ID процесса | Всего завершено |
|---|---|---|
| $2$ | $121$ | $1$ |
| $3$ | $106$ | $2$ |
| $4$ | $112$ | $3$ |
| $5$ | $125$ | $4$ |
| $6$ | $103$, $116$, $122$ | $7$ |
| $8$ | $105$, $115$ | $9$ |
| $9$ | $102$, $108$, $111$ | $12$ |
| $11$ | $109$, $124$ | $14$ |
| $12$ | $107$, $117$, $120$ | $17$ |
| $13$ | $110$ | $18$ |
| $15$ | $118$, $123$ | $20$ |
| $16$ | $113$, $114$ | $22$ |
| $17$ | $101$ | $23$ |
| $18$ | $104$ | $24$ |
| $21$ | $119$ | $25$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-06.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)
times = sorted(finish(p) for p in t)
print(times[16]) # 12 — время завершения 17-го по счёту процесса
Отсортировав времена завершения по возрастанию, достаточно взять элемент с индексом $16$ — это и есть момент, когда завершится семнадцатый процесс. Обратите внимание, что на $12$-й мс заканчиваются сразу три процесса, поэтому счёт перескакивает с $14$ сразу до $17$.