Диспетчер последовательного назначения для неоднородной ВС

В основе диспетчера лежит следующее решающее правило:

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

Введем сквозную нумерацию процессоров от 1 до

. Зададим вес {tj1 ... tjN} j-й вершины (j = 1 ... m; m — размер матрицы S или объем буфера диспетчера) так, что при новой нумерации процессоров tjl — время выполнения j-й работы l-м процессором. Например, при k = 2, n1 = 1, n2 = 2 расширенная матрица следования на рис. 10.15б примет вид, представленный на рис. 10.16.

В процессе распределения работ будем формировать расписание в виде таблицы ?, состоящей из N строк, каждая из которых соответствует одному процессору. В строке будем записывать последовательность заданий одному процессору. Задания имеют два вида: выполнить работу

, простоять t единиц времени (изображается

). Момент Ti , i = 1 ... N, окончания (отсчет ведется от нуля) выполнения последней работы или простоя, назначенных к данному моменту распределения i-му процессору, назовем текущим временем занятости процессора.

В процессе распределения и имитации выполнения работ будем использовать множество A номеров работ, уже назначенных на процессоры, но не выполненных в анализируемый момент времени. A представляет собой таблицу, содержащую пары "назначенная для выполнения задача — время окончания ее выполнения ", т.е. A = {

j - tj}.

Множество R — множество работ, соответствующих не назначенным входам (нулевым строкам) текущего значения изменяемой матрицы следования S.

Алгоритм диспетчера

Полагаем первоначально Tl = 0, l = 1, ... N, A = B = R =
, ? = 1, S? = S, (? — номер шага распределения). Переходим к выполнению 5.
Находим в множестве A значение tmu = minj

{ti} и множество B
A номеров работ, назначенных на процессоры и закончивших выполнение к моменту t?. Полагаем равными нулю все позиции A, составляющие B.

Содержание Назад Вперед