Задание №22 — Многопоточность

Решение:

В файле 14 процессов с идентификаторами 101–114. Зависимости распадаются на две не связанные между собой группы:

• 101 и 102 → 103 → 104 и 105; 104 → 106; 105 и 106 → 107 → 108 (длительности 4, 3, 1, 5, 7, 3, 1, 2 мс);
• 109 → 111 и 114; 111 и 114 → 113; независимый 110 → 112 (длительности 8, 16, 14, 14, 6, 5 мс).

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

Сколько процессов вообще могут работать одновременно? Одновременно могут выполняться только попарно независимые процессы. В первой группе любые три процесса обязательно связаны цепочкой зависимостей, независимых пар всего три (104 и 105, 105 и 106, 101 и 102) — значит, оттуда одновременно работают не более двух процессов. Во второй группе 109 предшествует 111 и 114, а 113 следует за ними, из пары 110 и 112 второй зависит от первого; максимум независимых процессов здесь — три (например, 111, 114 и 110). Итого одновременно могут идти не более $2 + 3 = 5$ процессов, то есть пятёрка процессов — это ровно две «ленты» первой группы и три «ленты» второй.

Вторая группа три непрерывные ленты держит долго: сразу после 109 (8 мс) параллельно запускаются 111 (16 мс) и 114 (14 мс), а третью ленту даёт цепочка 110 → 112 ($6 + 5 = 11$ мс). Ограничения нет: $\min(16, 14, 11) = 11$ мс.

Первая группа — узкое место. После 103 параллельно могут идти только 104 и 105. Первая лента — цепочка 104 → 106 ($5 + 3 = 8$ мс), вторая лента — процесс 105 (7 мс). Продлить вторую ленту нечем: следующий за 105 процесс 107 требует ещё и завершения 106, а 106 заканчивается на 1 мс позже, чем 105, — на стыке лента простаивает. Поэтому две ленты первой группы заняты одновременно не дольше 7 мс.

Итог: $\min(11, 7) = 7$ мс. Такое расписание действительно существует (общее время выполнения всей совокупности при этом остаётся минимальным — 38 мс):

ID	Время, мс	Зависит от	Старт, мс	Финиш, мс
101	4	—	0	4
102	3	—	0	3
103	1	101; 102	4	5
109	8	—	0	8
104	5	103	8	13
105	7	103	8	15
110	6	—	8	14
111	16	109	8	24
114	14	109	8	22
106	3	104	13	16
112	5	110	14	19
107	1	105; 106	16	17
108	2	107	17	19
113	14	111; 114	24	38

На отрезке с 8-й по 15-ю миллисекунду одновременно работают ровно пять процессов: сначала 104, 105, 110, 111, 114; с 13-й мс вместо завершившегося 104 включается 106; с 14-й мс вместо 110 — процесс 112. В момент 15 мс заканчивается 105, и остаётся четыре процесса. Длина отрезка — $15 - 8 = 7$ мс. Проверка:

sched = {101: (0, 4),   102: (0, 3),   103: (4, 5),   109: (0, 8),
         104: (8, 13),  105: (8, 15),  110: (8, 14),
         111: (8, 24),  114: (8, 22),
         106: (13, 16), 112: (14, 19), 107: (16, 17),
         108: (17, 19), 113: (24, 38)}

best = cur = 0
for t in range(38):                       # t - миллисекунда [t, t+1)
    k = sum(1 for s, e in sched.values() if s <= t < e)
    cur = cur + 1 if k >= 5 else 0
    best = max(best, cur)
print(best)

Ответ: 7