Для каждого процессора проводим анализ,

Для каждого процессора проводим анализ, сколько работ назначено на него на данном шаге распределения. Если назначения не произошло, переходим к анализу назначения на следующий процессор или заканчиваем анализ процессоров, если все они просмотрены. Если оказалась назначенной на процессор одна, 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 (т.е.

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