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

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

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

Главное в задании — правильно построить расписание; сам вопрос потом решается одной формулой. Разберём условие:

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

1. Процессы и расписание — ты сейчас здесь: когда процесс начинается и заканчивается.
2. Расписание в Excel — тот же расчёт формулами для таблицы из файла.
3. Сколько процессов — вопросы о миллисекундах; решим задачу темы: ответ 3.
4. Параллельность — сколько процессов идёт одновременно и как долго.
5. Сдвиги процессов — задачи, где процесс можно запустить позже.
6. Задержки и ограниченные ресурсы — дополнительный урок для редких задач.

Что значит, что один процесс зависит от другого?

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

Пусть процесс 1 работает 4 мс, а процесс 2 — 6 мс и ждёт результата процесса 1. Тогда они идут друг за другом: 2 начинает в 4 и заканчивает в 4 + 6 = 10.

Если же 2 ни от кого не зависит, оба начинают сразу и идут одновременно. Тогда всё готово к 6 — к окончанию самого долгого:

Время на рисунках разбито на миллисекунды, как в задании: 1-я мс — от момента 0 до момента 1, 2-я — от 1 до 2. Справа у каждой строки — моменты начала и окончания.

Процесс ждёт двух других. Когда он начнёт?

Когда закончится последний из них: начало — самое позднее окончание тех, кого ждёшь. Окончание — начало плюс время работы.

Пусть процесс C ждёт A и B. A заканчивается в момент 5, B — в момент 12. В момент 5 результат A уже есть, а B ещё работает. Оба результата готовы только в 12 — значит, C начинает в 12. Если C работает 3 мс, он закончится в 12 + 3 = 15 и займёт 13-ю, 14-ю и 15-ю мс.

Складывать 5 и 12 нельзя: это моменты на общих часах, а не длительности. Пока B работал до 12, A тоже работал — одновременно с ним.

Тех, кого процесс ждёт, будем называть его поставщиками: они поставляют ему результаты. У процесса без поставщиков (в таблице — 0) начало 0.

Как посчитать начала и окончания для всей таблицы?

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

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

Пройди расчёт по шагам. Пунктир на кадре — момент, когда готов последний поставщик: с него процесс и начинает.

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

Почему всё нельзя закончить быстрее 14 мс?

Есть цепочка, где каждый процесс ждёт предыдущего: 2 → 5 → 7 → 8. Она идёт строго по очереди, 6 + 5 + 2 + 1 = 14 мс. Её называют критической: сколько бы процессов ни шло одновременно, быстрее она не пройдёт.

Найти её легко с конца. Процесс 8 начался в 13 — по окончанию 7. Процесс 7 начался в 11 — по окончанию 5. Процесс 5 начался в 6 — по окончанию 2. Каждый раз берём того поставщика, который закончился последним.

• ЗависимостьB начинает только после окончания A
• Началосамое позднее окончание поставщиков; без них — 0
• Окончаниеначало + время работы
• Миллисекундыпроцесс с s до f занимает мс с (s + 1)-й по f-ю
• Порядок расчётасначала поставщики, потом те, кто их ждёт
• Общее времямаксимум всех окончаний
• Критическая цепочкакаждый ждёт предыдущего; её длина — общее время