Параллельное программирование



              

Формальное описание алгоритма диспетчера - часть 3


? При отрицательном результате проверки выполнение алгоритма продолжаем с шага 2.

Пример. Продолжим рассмотрение G и S* (S), представленных на рис. 10.11.

  1. R = {1}, T1 = T2 = 0, A = {0, 0}, B = {1, 2}, ? =

    , ? =
    . Задачу 1 назначаем на первый процессор и исключаем из R. После этого A = {1, 0}, B = {2}, T1 = 2. Т.к. теперь R =
    , B
    , записываем во вторую строку ? "простой в 2 единицы". Таблица ? примет вид

     \begin{array}{c|ccc|c} 1 & 1 & & & T_1=2\\ \hline & \ubox{2} & 2 && T_2=2 \end{array}

  2. A = {1, 0} , T? = T1 = T2 = 2 , B = {1, 2} , ? = {1}. После исключения из S* первой строки и первого столбца (рис. 10.12) сформируем множество входов R = {2, 3, 4} которое переупорядочим по невозрастанию времен решения задач, R = {3, 4, 2}.

    Матрица следования после первого шага распределения

    Рис. 10.12.  Матрица следования после первого шага распределения

    В результате последовательного назначения задач из R таблица ? примет вид

     \begin{array}{c|ccc|c} 1 & 1, 3 & & & T_1=5\\ \hline & \ubox{2}, 4 & && T_2=4 \end{array}

  3. A = {3, 4}, T? = min {5, 4} = 4, B = {2}, ? = {4}. После исключения из S* (рис. 10.13) информации о задаче 4 сформируем множество неотмеченных в A входов R = {2, 6}.

    Матрица следования после второго шага распределения

    Рис. 10.13.  Матрица следования после второго шага распределения

    Таблица ? примет вид

     \begin{array}{c|ccc|c} 1 & 1, 3 & & & T_1=5\\ \hline & \ubox{2}, 4, 2 & && T_2=5 \end{array}

  4. A = {3, 2} , T? = 5 , B = {1, 2}, ? = {3, 2}. После исключения (рис. 10.14) информации о задачах 3 и 2 из S* найдем R = {5, 6}. В результате последовательного назначения получаем окончательный вид таблицы ?.

    Матрица следования после третьего шага распределения и окончательный план выполнения работ

    Рис. 10.14.  Матрица следования после третьего шага распределения и окончательный план выполнения работ

Tреш = max{T1, T2} = 7 и совпадает с точным минимальным.




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