Многопроцессные системы

Что проверяет номер

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

Таблица процессов: ID, время выполнения, от каких процессов зависит (через «;»). Процесс стартует сразу после окончания самого позднего из тех, от кого зависит. Спрашивают: сколько процессов идёт параллельно в какую-то миллисекунду, сколько завершится за N мс, или за какое минимальное время закончится всё.

Простыми словами

Представь стройку дома. Фундамент занимает 3 дня и не зависит ни от чего. Стены занимают 5 дней и ждут фундамент. Крыша занимает 2 дня и ждёт стены. Окна занимают 1 день и тоже ждут стены.

Фундамент идёт с момента 0 до 3. Стены начинаются в 3 и заканчиваются в 8. Крыша идёт от 8 до 10, окна от 8 до 9. На 9-й день одновременно делают и крышу, и окна. Весь дом готов к моменту 10.

Если работа ждёт несколько других, она начинается, когда закончится самая поздняя из них. В №22 всё то же самое, только вместо дней миллисекунды, а вместо работ процессы.

Шаги

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

1. Раздели третий столбец по ; на отдельные столбцы (Данные → Текст по столбцам, разделитель ;). Получится до 4 столбцов зависимостей, пустые заменяем нулём.
2. Добавь строку с ID 0 и нулями: так ВПР на зависимость «0» (нет зависимости) вернёт 0, а не ошибку.
3. Начало процесса: =МАКС(ВПР(зав1; таблица; столбец_конца; 0); ВПР(зав2; …); …). Берём конец самой поздней зависимости.
4. Конец процесса: = начало + время.
5. Нумерация миллисекунд с 1: процесс со временем 3, начавшийся в момент 0, занимает мс 1, 2, 3; значит выполняется на мс t, если начало < t <= конец.
6. Конец всего = МАКС по столбцу концов. Это минимальное время всей совокупности.

Вся таблица с адресами ячеек

Пусть в строке 1 заголовки. После шагов 1 и 2 столбцы такие: A это ID, B время, D, E, F зависимости, G начало, H конец. Строка 2 это добавленный процесс с ID 0 и нулями везде, а настоящие процессы идут со строки 3.

В ячейке H3 считаем конец: =G3+B3. В ячейке G3 считаем начало:

=МАКС(ВПР(D3;$A$2:$H$8;8;0);ВПР(E3;$A$2:$H$8;8;0);ВПР(F3;$A$2:$H$8;8;0))

Что это значит:

• ВПР(D3; таблица; 8; 0) ищет в первом столбце таблицы процесс из ячейки D3 и берёт значение из 8-го столбца, то есть H, его конец.
• 0 в конце означает точное совпадение.
• $ закрепляет таблицу, чтобы при протягивании она не сдвигалась. Для своего файла поставь последнюю строку таблицы вместо 8.
• МАКС выбирает самую позднюю из зависимостей. Если зависимости нет, в ячейке 0, и ВПР находит строку с ID 0, где конец равен 0.

Протяни G3 и H3 вниз, и таблица посчитается сама, даже если процесс зависит от того, что записан ниже.

Таблица после расчёта

Так выглядят столбцы начала и конца для таблицы из задания.

Процесс 4 ждёт процессы 1 и 2. Они заканчиваются в 4 и 3, берём большее, поэтому начало 4. Процесс 5 ждёт 3 и 4, они заканчиваются в 6 и 9, поэтому начало 9.

Вопросы и формулы подсчёта

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

• «Параллельно на t-й мс»: =СЧЁТЕСЛИМН(начало; "<"&t; конец; ">="&t).
• «Завершатся за первые T мс»: =СЧЁТЕСЛИ(конец; "<="&T).
• «Начнутся не ранее a-й мс и завершатся не позднее b-й»: =СЧЁТЕСЛИМН(начало; ">="&(a-1); конец; "<="&b). Начало у нас считается от 0, поэтому «стартует не ранее a-й мс» значит начало >= a-1.

Почему условия именно такие

Миллисекунды нумеруются с единицы: процесс с началом 4 и концом 9 занимает миллисекунды с 5-й по 9-ю. Отсюда правило: процесс идёт на миллисекунде t, если начало < t и конец >= t. При t = 4 он ещё не идёт, потому что начало 4 не меньше 4, а при t = 9 уже идёт, потому что конец 9 не меньше 9.

Для таблицы выше формула выглядит так: =СЧЁТЕСЛИМН(G3:G8;"<5";H3:H8;">=5"). Здесь t = 5, для другого вопроса поменяй только число.

Ловушки