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

22. Вычислительные процессы: Определите максимальное количество процессов, которые параллельно…

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

В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.

Типовой пример организации данных в файле:

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$

Определите максимальное количество процессов, которые параллельно выполняются на $16$-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с $1$.

Например, для приведённой таблицы на $6$-й мс параллельно выполняются три процесса. Это процессы $2$, $5$ и $6$.

Здесь мало знать время завершения — нужен весь отрезок работы каждого процесса. Процесс стартует в самое раннее допустимое время, то есть сразу после того, как закончится последний из тех, от которых он зависит. Если процесс заканчивается на мс $f$ и длится $d$ мс, то занят он миллисекундами с $f-d+1$ по $f$. Процесс выполняется на $16$-й мс, если $f-d+1 \le 16 \le f$.

Считаем по цепочкам. Независимые процессы $111$, $122$ и $114$ занимают мс $1$, $1$ и $1$–$4$. Процесс $109$ зависит от $111$ и идёт с $2$ по $5$ мс. Процесс $103$ зависит от $114$ и $111$, стартует после $4$ мс и работает с $5$ по $10$ мс. От него зависят сразу несколько процессов: $101$ и $102$ занимают мс $11$–$16$, а $115$ — мс $11$–$15$.

Дальше процессы, стартующие ровно на $16$-й мс. Процесс $116$ зависит от $109$ и $115$, позже заканчивается $115$ (на $15$ мс), поэтому $116$ идёт с $16$ по $17$ мс. Процесс $117$ зависит от $103$ и $115$ и по той же причине занимает мс $16$–$19$. Процесс $123$ зависит от $111$ и $115$, тоже стартует после $15$ мс и работает с $16$ по $21$ мс.

Ещё два процесса захватывают $16$-ю мс, начавшись раньше. Процесс $124$ зависит от $109$ и $103$ и занимает мс $11$–$13$, процесс $121$ зависит от $109$ и занимает мс $6$–$11$. Оба они предшествуют процессам $104$ и $108$: те стартуют после $13$ мс, поэтому $104$ идёт с $14$ по $17$ мс, а $108$ — с $14$ по $19$ мс.

Таким образом, на $16$-й мс параллельно выполняются процессы $101$, $102$, $104$, $108$, $116$, $117$ и $123$ — всего $7$ процессов.

ПроцессЗанятые мс
$111$, $122$$1$
$114$$1$–$4$
$109$$2$–$5$
$113$$2$–$6$
$103$$5$–$10$
$119$$6$–$8$
$121$$6$–$11$
$105$$7$–$9$
$101$, $102$$11$–$16$
$115$$11$–$15$
$124$$11$–$13$
$104$$14$–$17$
$108$$14$–$19$
$116$$16$–$17$
$117$$16$–$19$
$123$$16$–$21$
$120$$18$–$19$
$107$$20$–$21$
$110$$20$–$24$
$112$$22$–$26$
$118$$22$–$25$
$125$$22$
$106$$25$–$27$

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

import pandas as pd
from functools import lru_cache

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

# процесс занимает мс с finish-t+1 по finish
print(sum(1 for p in t if finish(p) - t[p] < 16 <= finish(p)))   # 7

Условие finish(p) - t[p] < 16 означает, что процесс успел стартовать до конца $16$-й миллисекунды, а 16 <= finish(p) — что он к этому моменту ещё не закончился. Вся совокупность процессов в этом файле завершается на $27$ мс.

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

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