Карточки
Тесты
Главная
Курсы
Подписка
22. Вычислительные процессы: #298253
В файле содержится информация о совокупности $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+1$ по $f$, где $f$ — момент завершения, $d$ — длительность.
Независимые процессы $101$, $102$ и $109$ занимают мс $1$–$15$, $1$–$14$ и $1$–$8$. Процессы $110$ и $111$ зависят от $109$ и стартуют после $8$ мс: $110$ занимает мс $9$–$22$, $111$ — мс $9$–$14$. Процесс $113$ зависит от $111$ и занимает мс $15$–$22$. Процесс $103$ зависит от $101$ и $102$, позже заканчивается $101$ (на $15$ мс), значит $103$ занимает мс $16$–$18$. От него зависят $104$ (мс $19$–$21$) и $105$ (мс $19$–$33$), а от $104$ — процесс $106$ (мс $22$–$32$). Процесс $112$ зависит от $110$ и $111$ и занимает мс $23$–$35$, процесс $107$ — мс $34$–$38$, процесс $108$ — мс $39$–$46$.
Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он дважды. С $9$ по $14$ мс работают $101$, $102$, $110$ и $111$ — отрезок длиной $6$ мс; на $15$-й мс закончились $102$ и $111$, а добавился только $113$, и осталось три. Второй раз четвёрка набирается с $19$ по $22$ мс: сначала это $104$, $105$, $110$ и $113$, а на $22$-й мс вместо $104$ подключается $106$. Это отрезок длиной $4$ мс, на $23$-й мс процессы $110$ и $113$ заканчиваются, а добавляется только $112$.
Самый длинный отрезок — с $9$ по $14$ мс, его продолжительность $6$ мс.
| Процесс | Занятые мс |
|---|---|
| $101$ | $1$–$15$ |
| $102$ | $1$–$14$ |
| $109$ | $1$–$8$ |
| $110$ | $9$–$22$ |
| $111$ | $9$–$14$ |
| $113$ | $15$–$22$ |
| $103$ | $16$–$18$ |
| $104$ | $19$–$21$ |
| $105$ | $19$–$33$ |
| $106$ | $22$–$32$ |
| $112$ | $23$–$35$ |
| $107$ | $34$–$38$ |
| $108$ | $39$–$46$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-22.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
Спрашивается не про конкретный набор процессов, а про количество: во втором отрезке состав четвёрки на $22$-й мс меняется, но параллельных всё равно четыре. Вся совокупность процессов завершается на $46$ мс.
20
