22. Вычислительные процессы: В файле содержится информация о совокупности N вычислительных…
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.
Типовой пример организации данных в файле:
| ID процесса $B$ | Время выполнения процесса $B$ (мс) | ID процесса(-ов) $A$ |
|---|---|---|
| $101$ | $4$ | $0$ |
| $102$ | $3$ | $0$ |
| $103$ | $1$ | $101$; $102$ |
| $104$ | $7$ | $103$ |
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно и время окончания работы всех процессов минимально.
Условие «время окончания работы всех процессов минимально» означает, что каждый процесс стартует в самое раннее допустимое время — сразу после окончания последнего из тех, от которых он зависит. Расписываем отрезки: процесс, заканчивающийся на мс $f$ и длящийся $d$ мс, занят миллисекундами с $f-d+1$ по $f$.
Независимые процессы $101$, $107$ и $108$ занимают мс $1$–$7$, $1$–$10$ и $1$–$17$. Процессы $102$ и $103$ зависят от $101$ и стартуют после $7$ мс: $102$ занимает мс $8$–$23$, $103$ — мс $8$–$24$. Процессы $109$ и $111$ зависят от $108$ и стартуют после $17$ мс: $109$ занимает мс $18$–$27$, $111$ — мс $18$–$24$. Процесс $104$ зависит от $103$ и $107$, позже заканчивается $103$ (на $24$ мс), значит $104$ занимает мс $25$–$34$; от него зависят $105$ (мс $35$–$38$) и $106$ (мс $35$–$48$). Процесс $112$ зависит от $111$ и занимает мс $25$–$43$, а процесс $110$ зависит от $109$ и занимает мс $28$–$50$.
Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он трижды. С $8$ по $10$ мс работают $102$, $103$, $107$ и $108$ — отрезок в $3$ мс; на $11$-й мс процесс $107$ уже закончился. С $18$ по $23$ мс работают $102$, $103$, $109$ и $111$ — отрезок в $6$ мс; на $24$-й мс процесс $102$ закончился. С $35$ по $38$ мс работают $105$, $106$, $110$ и $112$ — отрезок в $4$ мс; на $39$-й мс заканчивается $105$.
Самый длинный из этих отрезков — с $18$ по $23$ мс, его продолжительность $6$ мс.
| Процесс | Занятые мс |
|---|---|
| $101$ | $1$–$7$ |
| $107$ | $1$–$10$ |
| $108$ | $1$–$17$ |
| $102$ | $8$–$23$ |
| $103$ | $8$–$24$ |
| $109$ | $18$–$27$ |
| $111$ | $18$–$24$ |
| $104$ | $25$–$34$ |
| $112$ | $25$–$43$ |
| $110$ | $28$–$50$ |
| $105$ | $35$–$38$ |
| $106$ | $35$–$48$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-12.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)
T = max(finish(p) for p in t)
cnt = [0] * (T + 2) # сколько процессов идёт на каждой мс
for p in t:
for ms in range(finish(p) - t[p] + 1, finish(p) + 1):
cnt[ms] += 1
M = max(cnt[1:T+1]) # максимум одновременных процессов
best = cur = 0 # самая длинная цепочка мс со значением M
for ms in range(1, T + 1):
cur = cur + 1 if cnt[ms] == M else 0
best = max(best, cur)
print(best) # 6
Спрашивается не про конкретный набор процессов, а про количество, поэтому важно только значение счётчика. Вся совокупность процессов в этом файле завершается на $50$ мс.