Задание 22
тема 1 из 1

Параллельные процессы

Процесс начинается, когда закончились все процессы, от которых он зависит, а независимые процессы идут параллельно. Время окончания каждого процесса равно наибольшему времени окончания его предшественников плюс его длительность, а вся совокупность завершается в момент самого позднего окончания. Чтобы найти, сколько процессов работают одновременно, отмечают каждый процесс на шкале времени по миллисекундам.

Главная тема в задании22На карте навыков

Как рассчитать время процессов

Процесс B зависит от процесса A, если B нужны результаты A. Тогда B начинается только после окончания A. Независимые процессы выполняются параллельно.

  • Начало процесса — наибольшее из времён окончания процессов, от которых он зависит. Независимый процесс начинается в момент 0.
  • Окончание — начало плюс длительность процесса.
  • Минимальное время всей совокупности — наибольшее из времён окончания.
  • Неизвестная длительность tt: переберите tt и найдите наибольшее, при котором общее время не больше заданного.
  • Одновременная работа: отметьте каждый процесс на шкале по миллисекундам и посчитайте, сколько процессов идёт в каждую миллисекунду.

Начало и окончание процесса

В файле задания для каждого процесса дан идентификатор (ID), длительность в миллисекундах и список ID процессов, от которых он зависит. Ноль в третьем столбце значит, что процесс независимый. Процесс нельзя приостановить: начавшись, он идёт без перерыва.

Процесс может начаться, только когда закончились все его предшественники. Поэтому его начало — наибольшее из их времён окончания, а окончание — начало плюс длительность. Считайте процессы в таком порядке, чтобы предшественники каждого уже были посчитаны.

Пример

Процессы (ID, длительность в мс, от каких зависит): 1 — 3 мс, независимый; 2 — 4 мс, от 1; 3 — 2 мс, от 2 и 4; 4 — 4 мс, независимый; 5 — 8 мс, от 1 и 4; 6 — 3 мс, от 1. Когда начинается и заканчивается каждый процесс?

  1. 1.Независимые 1 и 4 начинаются в 0: 1 идёт от 0 до 3 мс, 4 — от 0 до 4 мс.
  2. 2.2 и 6 ждут только 1: 2 идёт от 3 до 7 мс, 6 — от 3 до 6 мс.
  3. 3.5 ждёт 1 и 4: начало max⁡(3,4)=4\max(3, 4) = 4, окончание 4+8=124 + 8 = 12.
  4. 4.3 ждёт 2 и 4: начало max⁡(7,4)=7\max(7, 4) = 7, окончание 7+2=97 + 2 = 9.

Ответ: 1: 0–3, 2: 3–7, 3: 7–9, 4: 0–4, 5: 4–12, 6: 3–6

Программа: окончание процесса рекурсией

Таблицу из файла переписывают в список: для каждого процесса ID, длительность и список предшественников, пустой для независимого. Функция finish(i) повторяет правило: берёт наибольшее окончание предшественников, default=0 даёт ноль для независимого процесса, и прибавляет длительность. Словарь end запоминает посчитанные окончания. Основы функций и словарей — в теме Python для ЕГЭ.

Тот же расчёт делают в электронной таблице: в столбце окончания для каждого процесса пишут наибольшее из окончаний его предшественников плюс его длительность.

Пример

Процессы: 1 — 3 мс, независимый; 2 — 4 мс, от 1; 3 — 2 мс, от 2 и 4; 4 — 4 мс, независимый; 5 — 8 мс, от 1 и 4; 6 — 3 мс, от 1. Найдите минимальное время, за которое завершатся все процессы.

  1. 1.Список data повторяет условие: 1 — 3 мс, 2 — 4 мс от 1, 3 — 2 мс от 2 и 4, 4 — 4 мс, 5 — 8 мс от 1 и 4, 6 — 3 мс от 1.
  2. 2.finish(i) вызывает себя для предшественников, поэтому порядок строк в списке не важен.
  3. 3.Программа печатает наибольшее окончание: 12.

Ответ: 1212 мс

Минимальное время всей совокупности

Все процессы закончатся в момент самого позднего окончания. Раньше закончить нельзя: этот процесс стоит в конце цепочки зависимых процессов, а они идут только друг за другом. Поэтому ответ — длительность самой долгой цепочки зависимостей.

Пример задания

Открытый банк ФИПИ

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

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

ID процесса B Время выполнения процесса B (мс) ID процесса(ов) А
1 4 0
2 3 0
3 1 1; 2
4 7 3


Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

59131_22.xlsx

Неизвестная длительность процесса

Иногда длительность одного процесса не дана, а задано, что все процессы должны закончиться не позже момента TT. С ростом tt общее время не уменьшается. Пока процесс с длительностью tt не лежит на самой долгой цепочке, общее время не меняется, потом растёт вместе с tt. Ищут наибольшее целое tt, при котором общее время не больше TT.

Вручную: пройдите все цепочки через неизвестный процесс и найдите, сколько времени у него в запасе. Программой: оберните расчёт в функцию от tt и переберите tt в цикле.

Пример

Процессы: 1 — 3 мс, независимый; 2 — tt мс, независимый; 3 — 4 мс, от 1 и 2; 4 — 2 мс, от 3. Все процессы должны завершиться не более чем за 12 мс. Найдите наибольшее целое tt.

  1. 1.3 начинается в max⁡(3,t)\max(3, t), 4 заканчивается в max⁡(3,t)+4+2\max(3, t) + 4 + 2.
  2. 2.Условие: max⁡(3,t)+6≤12\max(3, t) + 6 \le 12, то есть t≤6t \le 6.
  3. 3.Программа считает общее время для каждого tt и запоминает последнее подходящее tt. Она печатает 6.

Ответ: 66

Сколько процессов работают одновременно

Нарисуйте шкалу времени по миллисекундам: строка на каждый процесс, клетка на каждую миллисекунду. Закрасьте клетки от начала до окончания процесса. Процесс от 3 до 7 мс занимает четыре клетки: 4-ю, 5-ю, 6-ю и 7-ю миллисекунды. Число закрашенных клеток в столбце — число процессов, которые работают в эту миллисекунду.

Отрезок одновременной работы kk процессов — подряд идущие миллисекунды, в каждую из которых работают kk процессов. Его продолжительность — число таких миллисекунд.

Пример

Процессы: 1 — 3 мс, независимый; 2 — 4 мс, от 1; 3 — 2 мс, от 2 и 4; 4 — 4 мс, независимый; 5 — 8 мс, от 1 и 4; 6 — 3 мс, от 1. Найдите наибольшую продолжительность отрезка, когда одновременно работают три процесса.

  1. 1.Отрезки процессов: 1 — 0–3, 4 — 0–4, 2 — 3–7, 6 — 3–6, 5 — 4–12, 3 — 7–9.
  2. 2.От 0 до 3 мс работают 1 и 4: два процесса. От 3 до 4 мс — 4, 2 и 6: три. От 4 до 6 мс — 2, 6 и 5: три.
  3. 3.От 6 до 9 мс работают по два процесса, дальше один.
  4. 4.Три процесса идут от 3 до 6 мс без перерыва: 3 мс. Программа считает то же число по миллисекундам.

Ответ: 33 мс

Сдвиг процесса позже

В вопросе «в течение которого возможно одновременное выполнение» процессы не обязаны начинаться как можно раньше. Процесс можно начать позже, но нельзя прервать. Цепочка зависимых процессов, которые идут вплотную друг за другом, занимает одну строку шкалы без перерыва, и её можно сдвигать целиком.

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

Пример задания

Открытый банк ФИПИ

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

ID процесса B Время выполнения процесса B (мс) ID процесса(-ов) A
1 4 0
2 3 0
3 1 1; 2
4 7 3


Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

29916_22.ods

29916_22.xls

29916_22.xlsx

Потренируйте навык

Все задания на этот навык

Решать