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