Задержки и ограниченные ресурсы

Это дополнительный урок: такие задачи есть в подборках, но не было на экзаменах. Что меняется, если результат доходит до получателя с задержкой?

Готовность поставщика сдвигается на задержку: начало — самое позднее «окончание + задержка». Пусть процессы 1 (3 мс) и 2 (5 мс) ни от кого не зависят, 3 (4 мс) ждёт оба, 4 (2 мс) ждёт 3, а каждый результат идёт 2 мс. Тогда 3 начнёт в max(3; 5) + 2 = 7 и закончит в 11, а 4 начнёт в 11 + 2 = 13 и закончит в 15.

Задержку прибавляют один раз к самому позднему окончанию, а не к каждому поставщику с последующим сложением. Независимым процессам она не нужна — им ничего не передают. В Excel это =МАКС(E2:F2)+2 для зависимых процессов.

Время работы одного процесса неизвестно, а общее время дано. Как его найти?

Выразить общее время через неизвестное x и решить уравнение. В учебном примере пусть процесс 6 работает x мс. Он начинает в 8 и заканчивает в 8 + x. Процесс 8 ждёт 6 и 7 (тот готов к 13): начинает в max(8 + x; 13), заканчивает на 1 мс позже. Общее время — max(9 + x; 14).

Если общее время 16, то 9 + x = 16 и x = 7. Если 14 — подходит любое x от 1 до 5: процесс 6 успевает раньше 7 и на итог не влияет. Если спрашивают наибольшее такое x, ответ 5. А общее время 13 невозможно при любом x: ветвь через 7 уже даёт 14.

Что, если одновременно может идти не больше двух процессов?

Тогда готовый процесс ждёт ещё и свободного места. Расписание строят по шагам: в момент, когда место освобождается, запускают готовый процесс по правилу из условия — например, с меньшим ID.

Процессы 1 (4 мс), 2 (4 мс) и 3 (3 мс) ни от кого не зависят, 4 (2 мс) ждёт 1, 5 (1 мс) ждёт 2 и 3. Мест два. В 0 готовы 1, 2 и 3 — запускаем 1 и 2. В 4 оба заканчиваются: готовы 3 и 4 — запускаем их. В 6 заканчивается 4, но 5 ещё ждёт процесс 3. В 7 заканчивается 3 — запускаем 5, всё готово к 8.

Правило выбора берут из условия дословно: «с меньшим ID», «тот, кто раньше стал готов». От правила зависит ответ.

Два процесса не могут идти одновременно. Как это учесть?

Второй из них ждёт не только своих поставщиков, но и окончания первого. В учебном примере пусть 4 и 5 не могут идти вместе, первым идёт меньший ID. Оба готовы в 6: 4 идёт с 6 до 8, 5 — с 8 до 13. Процесс 7 ждёт 5 и начинает в 13, процесс 8 — в 15. Общее время 16 вместо 14.

• Задержканачало = самое позднее окончание + задержка
• Неизвестное xобщее время через x, потом уравнение
• Ограничение местготов и есть место — по правилу условия
• Взаимное исключениевторой ждёт окончания первого