Диспетчер последовательного назначения для неоднородной ВС
В основе диспетчера лежит следующее решающее правило:
При известных текущих значениях занятости процессоров, готовые к выполнению работы назначаются так, чтобы в первую очередь выполнялись более трудоемкие, и чтобы каждая работа была назначена на тот процессор, который раньше других закончит ее выполнение.
Введем сквозную нумерацию процессоров от 1 до
В процессе распределения работ будем формировать расписание в виде таблицы ?, состоящей из N строк, каждая из которых соответствует одному процессору. В строке будем записывать последовательность заданий одному процессору. Задания имеют два вида: выполнить работу
В процессе распределения и имитации выполнения работ будем использовать множество A номеров работ, уже назначенных на процессоры, но не выполненных в анализируемый момент времени. A представляет собой таблицу, содержащую пары "назначенная для выполнения задача — время окончания ее выполнения ", т.е. A = {
Множество R — множество работ, соответствующих не назначенным входам (нулевым строкам) текущего значения изменяемой матрицы следования S.
Алгоритм диспетчера
- Полагаем первоначально Tl = 0, l = 1, ... N, A = B = R = , ? = 1, S? = S, (? — номер шага распределения). Переходим к выполнению 5.
- Находим в множестве A значение tmu = minj
{ti} и множество B
A номеров работ, назначенных на процессоры и закончивших выполнение к моменту t?. Полагаем равными нулю все позиции A, составляющие B.
Этим имитируется окончание выполнения работ на процессорах к моменту времени t?. - Для всех процессоров, для которых текущее время занятости меньше значения t? (Ti < t?), записываем простой в течение времени t? - Ti (символом простоя ). Для этих процессоров полагаем Ti = t?.
- Исключаем из S? строки и столбцы, соответствующие всем работам из B, после чего матрицу S? (S*?) уплотним. Полагаем ? := ? + 1. Таким образом сформируется матрица S? (а также S*?) на новом шаге распределения.
- Находим множество R — входов матрицы следования S?, соответствующих не назначенным ранее работам. Если R
, переходим к выполнению 6, в противном случае выполняем пункт 2. - Пусть для определенности R = {1 ...r}, работеp соответствует вес {tp1 ... tpN}, p = 1 ... r. Формируем суммы Tl + tpl , l = 1 ... N, p = 1 ... r. Для каждого значения p (т.е. для каждой работы из R) находим минимальную (по l) из таких сумм, т.е. для каждой работы находим один или несколько процессоров, на которых время окончания выполнения этой работы минимально при текущих значениях занятости процессоров. Найденные суммы сведем в невозрастающую последовательность R*, состоящую из r чисел. При этом сохраним информацию о соответствии процессорам.
- Ставим в соответствие каждой p-й работе, представленной в последовательности R*, значение ?p, равное числу процессоров, при выполнении на которых достигается найденное минимальное время окончания выполнения этой работы.
- Производим последовательное назначение работ на процессоры следующим образом. Назначаем не более N работ слева направо в соответствии с вхождением времени окончания их выполнения в последовательность R*. Каждую p-ю работу назначаем на все те процессоры, (их число равно ?p), на которых достигается входящее в R* время окончания выполнения. В результате те работы, для которых ? > 1, окажутся назначенными более чем на один процессор, а на один процессор на данном шаге могут оказаться назначенными более одной работы. Чтобы определить окончательно, на какой процессор должна быть назначена p-я работа, воспользуемся следующей процедурой.
Для каждого процессора проводим анализ, сколько работ назначено на него на данном шаге распределения. Если назначения не произошло, переходим к анализу назначения на следующий процессор или заканчиваем анализ процессоров, если все они просмотрены. Если оказалась назначенной на процессор одна, p-я, работа, считаем ее окончательно закрепленной за данным процессором, и, если ?p > 1, исключаем ее из рассмотрения при анализе последующих процессоров — т.е., снимаем ее с назначения на другие процессоры. Если на процессор назначено более одной работы, закрепляем за процессором лишь ту работуp, которая имеет минимальное значение ?p. Если несколько работ имеют равное минимальное значение ?p, назначаем любую (первую) из них. Для множества работ {?}, отклоненных от назначения на данный процессор, полагаем ?? := ??
- 1. Значение ?? = 0 означает, что работе ? отказано в назначении на данном шаге распределения. Назначенную работу исключаем из рассмотрения при анализе следующих процессоров. Номера назначенных работ оказываются записанными в строки таблицы ?, соответствующие процессорам. Эти номера исключаем из R. Номер каждой назначенной работы и время окончания ее выполнения (оно же — время занятости процессора) заносим в A. - Проверяем, все ли работы распределены. При отрицательном результате проверки переходим к выполнению 2.
Конец алгоритма.
Пример.
При k = 2, n1 = 1, n2 = 2, (N = 3) распределим работы, отображенные расширенной матрицей следования на рис. 10.16 (соответствующей графу на рис. 10.15), для минимизации времени выполнения.
Рис. 10.16. Преобразование расширенной матрицы следования
- T1 = T2 = T3 = 0, A = B = , S1 = S, R = {1}. Выполнение работы 1 ранее всех закончит процессор 1. После ее назначения T1 = 1, T2 = T3 = 0, A = {1 - 1}.
- Найдем в A работу 1 с минимальным временем окончания выполнения, равным 1. Записываем простои в одну единицу времени процессорам 2 и 3. Таблица ? принимает вид
После исключения первой строки и первого столбца из S1 (т.е.
по матрице S2) найдем R = {2, 3, 4, 6}. Составим таблицу 10. 1 времени окончания выполнения каждой работы из R каждым процессором l = 1, 2, 3. Минимальное время окончания выполнения каждой работы выделено.
Таблица 10.1.
Формируем последовательность R* = {6 (4; 1, 2, 3, ?4 = 3), 3 (2; 2,3, ?2 = 2), 3( 3; 1, ?3 = 1), 2 (6; 2,3, ?6 = 2)}, где в круглых скобках указаны номер работы, список процессоров, на которых достигается минимальное время окончания ее выполнения, и число ?pl Tl+t2l Tl+t3l Tl+t4l Tl+t6l 1 4 3 6 4 2 3 6 6 2 3 3 6 6 2
этих процессоров.
Назначим первоначально (таблица 10.2) работу 4 на процессоры 1, 2, 3, работу 2 — на процессоры 2 и 3 , работу 3 — на процессор 1.
Таблица 10.2.
После анализа значений ?p оставим на процессоре 1 работу 3 (после чего ?4 = 2), на процессоре 2 — работу 4 (после чего ?2 = 1), на процессоре 3 — работу 2, A = \{3 - 3, 4 - 6, 2 - 3\}. Таблица распределения ? примет вид1 4 (?4 = 3), 3(?3 = 1) 2 4 (?4 = 3), 2(?2 = 2) 3 4 (?4 = 3), 2(?2 = 2) 
B = {2, 3}. После исключения строк и столбцов, соответствующих работам 2 и 3, из матрицы S2, т.е. по сформированной матрице S3, найдем R = {5, 6}. Составим таблица 10.3 значений времени окончания выполнения каждой работы из R каждым процессором.
Таблица 10.3.
Из таблицы найдем R* = {5 (5; 1, ?5 = 1), 4 (6; 3, ?6 = 1)},l Tl+t5l Tl+t6l 1 5 6 2 10 7 3 7 4
Назначим работу 5 на процессор 1, работу 6 — на процессор 3, A = {5 - 5,4 - 6, 6 - 4}. Таблица распределения ? примет вид
B = {6}. После исключения строки и столбца, соответствующих работе 6, из матрицы следования S3, т.е. по сформированной матрице S4, найдем R =. Назначим процессору 3 простой в течение одной условной единицы времени. Таблица ? примет вид
B = {5}. После преобразования матрицы S4, т.е. по матрице S5, найдем R = {7, 8}. Из таблицы 10.4, аналогичной таблице 3, найдем R* = {9 (8;1, ?8 = 1), 7 (7; 3, ?7 = 1)} .
Таблица 10.4.
Назначаем работу 8 на процессор 1, работу 7 — на процессор 3. Таблица ? примет видl Tl+t7l Tl+t8l 1 9 9 2 8 11 3 7 10 
B = {4}. После исключения строки и столбца, соответствующих работе 4, из матрицы следования S5, т.е. по сформированной при этом матрице S6, найдем R = {9}. Время окончания выполнения работы 9 на процессорах равно соответственно 10, 8, 9. Назначаем работу 9 на процессор 2. Таблица ? примет окончательный вид
Дополнение.
Данный диспетчер для неоднородной ВС построен на основе обобщения рассмотренного диспетчера последовательного назначения для однородных ВС, который можно рассматривать как частный случай при k = 1.
Он применим и в другом частном случае: когда отсутствует частичная упорядоченность работ, то есть когда надо разделить "поровну" взаимно независимые работы между n исполнителями. Наглядный пример такого распределения составляет задача о рюкзаках, рассмотренная в разделе 10.1.1.
