Формальное описание алгоритма диспетчера
Пусть задана (рис. 10.11) расширенная матрица следования S*, отражающая информационные связи внутри множества m работ j = 1...m. Веса tj — времена выполнения каждой j-й работы на каждом из n процессоров однородной ВС с общей ОП.

Рис. 10.11. Граф алгоритма и расширенная матрица следования
Необходимо составить расписание параллельного выполнения работ, при котором время выполнения всей совокупности работ минимально.
Вспомогательные построения
Пусть в результате распределения составляется таблица-расписание?, содержащая n строк — расписаний одному процессору. В строке — последовательность заданий двух видов: выполнить работу (задачу, оператор и т.д.)


Пусть в процессе распределения формируется таблица (множество) A номеров задач, назначенных к данному шагу распределения последними для выполнения на каждом процессоре. Эти номера заносятся в позиции, закрепленные за каждым процессором. Если последним был записан простой, в соответствующей позиции значится 0.
В множество B будем объединять процессоры (один или более), имеющие на данном шаге распределения минимальное время занятости.
В множество ? выделим те работы из A, которые выполняются на процессорах из B.
Множество R — множество работ, соответствующих входам (нулевым строкам) текущего значения изменяемой в процессе распределения матрицы следования S.
Алгоритм.
- Полагаем первоначально Ti = 0, i = 1 ... n, A = {0, ...,0}, B = {1 ... n}, = , R =, ? = 1, S?* = S*; переходим к выполнению шага 6.
- Находим Tmu = min{Ti} и множество B номеров процессоров с найденным временем занятости.
- Находим множество ? A номеров задач, назначенных последними на процессоры из B. После построения ? все позиции в A, соответствующие процессорам из B, полагаем равными нулю. Этим моделируется окончание выполнения задач на данных процессорах к моменту T?.
- Если ? = , переходим к выполнению шага 7 при Rи шага 10 при R =; при ?выполняем следующий шаг.
- Исключаем из S?* строки и столбцы, соответствующие задачам, составляющим множество ?.
Содержание Назад Вперед