Ах, эти загадочные параллельные процессы!
Если бы они были людьми, то точно устроили бы вечеринку с танцами и перекличками: «Ты кто? Я зависимый от тебя!» — «А я вообще свободный и самостоятельный!» Вот и нам приходится разбираться в этом клубе программных тусовщиков на экзамене по информатике.
Задание 22 из ЕГЭ по информатике — это как детективная история про то, кто с кем дружит, кто кого ждет и кто решил прийти пораньше.
Начнем с главного героя — диаграммы Ганта. Это такая хитрая штука, которая показывает временные промежутки работы процессов.
Представьте себе расписание на вечеринке: когда играет диджей, когда начинается караоке и кто из гостей опаздывает. Только вместо гостей у нас процессы, которые могут либо тусоваться вместе (работать параллельно), либо ждать друг друга у дверей (быть зависимыми).
Задание звучит просто: нужно найти самый длинный период времени, когда одновременно работают четыре процесса.
Ну а если подумать, это как попытка устроить так, чтобы на вечеринке одновременно танцевали четыре самых энергичных гостя. Но проблема в том, что некоторые гости не могут танцевать без разрешения других — вот тут начинаются зависимости.
Сначала мы определяем независимых ребят — процессы 1 и 2. Они такие свободные птицы, могут начать тусить в любое время. Остальные же висят на них как хвосты: процесс 3 не может начать свой танец без разрешения 1 или 2; затем процесс 4 и 5 тоже зависят от 3; а дальше цепочка растет как снежный ком — шестой зависит от пятого, седьмой — сразу от четвертого и шестого (наверное, самый социально активный), а восьмой — от седьмого.
Вот так все восемь процессов оказываются в одной большой группе друзей-зависимых.
Представьте себе такую сцену: процесс третий стоит у двери вечеринки и говорит процессам четвертому и пятому: «Ребята, не войдете без меня!» А те ему в ответ: «Ну ладно уж». И все идут вместе — никто не может прийти раньше другого.
Далее у нас есть еще две группы желтых и зеленых процессов.
Там ситуация проще: девятый процесс приглашает одиннадцатый на танец, а десятый ведет двенадцатого под руку. Но они тусуются отдельно — их можно передвинуть вправо на диаграмме Ганта так далеко, что первая группа останется одна на площадке.
Теперь самое интересное! Нам нужно понять максимум сколько процессов могут работать одновременно в первой группе? Максимум два!
То есть максимум два гостя могут танцевать вместе здесь одновременно. Причем этот танец длится с 9 до 17 миллисекунд – целых восемь милых миллисекунд! Не долго, но зато ярко.
Во второй и третьей группах всё скучнее – там только по одному процессу за раз может работать.
Это как если бы каждый гость пришел со своим персональным ди-джеем и устраивал сольное выступление.
Но ведь нам надо именно четыре процесса одновременно! Значит надо хитро переставить вторую и третью группу так, чтобы их участники успели присоединиться к общей вечеринке между 9-й и 17-й миллисекундами. Например, сдвинуть начало третьей группы на восемь миллисекунд вправо – словно пригласить зеленую команду чуть позже на вечеринку.
И вот результат – максимальное время одновременной работы четырех процессов составит пять миллисекунд – то есть коротенький эпизод настоящего драйва! Можно представить как момент в клубе под названием «Параллельность», где все четыре героя наконец встретились на танцполе.