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