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