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

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

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

В файле содержится информация о совокупности $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$, $107$ и $108$ занимают мс $1$–$7$, $1$–$7$ и $1$–$18$. Процессы $102$ и $103$ зависят от $101$ и стартуют после $7$ мс: $102$ занимает мс $8$–$22$, $103$ — мс $8$–$23$. Процессы $109$ и $111$ зависят от $108$ и стартуют после $18$ мс: $109$ занимает мс $19$–$28$, $111$ — мс $19$–$25$. Процесс $104$ зависит от $103$ и $107$, позже заканчивается $103$ (на $23$ мс), значит $104$ занимает мс $24$–$33$; от него зависят $105$ (мс $34$–$46$) и $106$ (мс $34$–$37$). Процесс $112$ зависит от $111$ и занимает мс $26$–$29$, а процесс $110$ зависит от $109$ и занимает мс $29$–$47$.

Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. На первых восемнадцати миллисекундах их всегда три. На $19$-й мс к процессам $102$ и $103$ добавляются $109$ и $111$, а $108$ как раз закончился — становится четыре. Столько же держится до $22$-й мс включительно, а на $23$-й мс процесс $102$ уже закончился, и остаётся три. Больше четырёх нигде не набирается: дальше по файлу счётчик опускается до трёх и двух.

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

ПроцессЗанятые мс
$101$, $107$$1$–$7$
$108$$1$–$18$
$102$$8$–$22$
$103$$8$–$23$
$109$$19$–$28$
$111$$19$–$25$
$104$$24$–$33$
$112$$26$–$29$
$110$$29$–$47$
$105$$34$–$46$
$106$$34$–$37$

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

import pandas as pd
from functools import lru_cache

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

Здесь максимум достигается лишь в одном месте, поэтому и отрезок единственный. Вся совокупность процессов завершается на $47$ мс.

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

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