Примеры заданий
Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Типовой пример организации данных в файле
Определите максимальное количество процессов, которые параллельно выполняются на 16-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1. Например, для приведённой таблицы на 6-й мс параллельно выполняются три процесса. Это процессы 2, 5 и 6.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла. | ||||||||||||||||||||||
| Файл к заданию (zip) |
Показать ответ
Решение.
- Процесс начинается, когда закончились все процессы, от которых он зависит: начало = max(окончаний предшественников), окончание = начало + длительность. Независимый процесс (0) начинается сразу.
- Процесс с началом s и окончанием e выполняется в миллисекунды s+1, …, e (нумерация с 1).
import pandas as pd df = pd.read_excel("22.xlsx") dur, dep = {}, {} for pid, t, d in df.values: dur[pid] = t dep[pid] = [int(x) for x in str(d).split(";") if int(x) != 0] end = {} def fin(p): # время окончания процесса p if p not in end: end[p] = max([fin(q) for q in dep[p]], default=0) + dur[p] return end[p] for p in dur: fin(p) start = {p: end[p] - dur[p] for p in dur} run = lambda t: sum(start[p] < t <= end[p] for p in dur) print(run(16))- На 16-й мс выполняются процессы: 101, 102, 104, 108, 116, 117, 123 — всего 7.
- Ответ: 7.