Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

22. Вычислительные процессы: В файле содержится информация о совокупности N вычислительных…

Задание #298226
Решено верно
Решено неверно
Сообщить о проблеме

В файле содержится информация о совокупности $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$ и $110$ занимают мс $1$–$14$, $1$–$3$ и $1$–$8$. Процесс $104$ зависит от $102$ и работает с $4$ по $14$ мс. Процессы $111$ и $112$ зависят от $110$ и стартуют после $8$ мс: $111$ занимает мс $9$–$24$, $112$ — мс $9$–$16$. Процесс $103$ зависит от $101$ и $102$, позже заканчивается $101$ (на $14$ мс), поэтому $103$ занимает единственную $15$-ю мс. От него зависят $105$ (мс $16$–$28$) и $106$ (мс $16$–$20$), а от $106$ — процесс $107$ (мс $21$–$23$). Процесс $113$ зависит от $112$ и занимает мс $17$–$30$. Наконец, $108$ работает на $29$-й мс, а $109$ — на мс $30$–$31$.

Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он дважды. Первый раз — на мс с $9$ по $14$, когда параллельно идут $101$, $104$, $111$ и $112$: это отрезок длиной $6$ мс. Затем на $15$-й мс остаются только $103$, $111$ и $112$, то есть три процесса, и цепочка обрывается. Второй раз четвёрка набирается с $16$-й мс — работают $105$, $106$, $111$ и $112$ — и держится до $23$-й мс включительно, хотя состав по ходу меняется: с $17$-й мс вместо $112$ подключается $113$, а с $21$-й мс вместо $106$ идёт $107$. Это отрезок с $16$ по $23$ мс длиной $8$ мс. На $24$-й мс процесс $107$ уже закончился, и параллельных остаётся три.

Таким образом, максимальное количество одновременно выполняемых процессов равно $4$, а самый длинный отрезок, на котором это количество держится, длится $8$ мс.

ПроцессЗанятые мс
$101$$1$–$14$
$102$$1$–$3$
$110$$1$–$8$
$104$$4$–$14$
$111$$9$–$24$
$112$$9$–$16$
$103$$15$
$105$$16$–$28$
$106$$16$–$20$
$113$$17$–$30$
$107$$21$–$23$
$108$$29$
$109$$30$–$31$

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-09.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)

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)   # 8

Обратите внимание: спрашивается не про конкретный набор процессов, а про количество. Состав четвёрки внутри отрезка с $16$ по $23$ мс меняется трижды, но одновременно работающих всё время ровно четыре, поэтому весь отрезок считается целиком.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение