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



              

Диспетчер распределения частично упорядоченного множества работ в однородной ВС - часть 2


Имитация выполнения первой работы

Рис. 10.8.  Имитация выполнения первой работы

  • Вновь выделяются входы графовой структуры текущего вида. В данном примере это программы, составляющие множество {№ 2, № 3, № 4}.

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

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

    Частным случаем этого правила является способ назначения заданий при отсутствии частичной упорядоченности.

    В результате упорядочения программ по невозрастанию времен их выполнения формируется очередь на данном шаге распределения:{ № 3, № 2, № 4}. Диаграмма последовательной однократной загрузки свободных с момента t = 2 процессоров принимает вид, показанный на рис. 10.9.

    Второй шаг распределения

    Рис. 10.9.  Второй шаг распределения

  • Вновь включается счетчик времени, следя за состоянием системы. Очевидно, что какие-то изменения могут наступить только в результате выполнения заданий. В момент t = 4 заканчивается выполнение программы № 2. Хотя новых входов в граф-схеме не образуется, есть вход (программа № 4), оставшийся после предыдущего шага распределения. Программа № 4 назначается на освободившийся процессор 2.

  • Затем таким же образом производится назначение программ № 5 и № 6, и формируется окончательный вид (рис. 10.10) временной диаграммы выполнения пакета заданий.

    Окончательный план выполнения работ

    Рис. 10.10.  Окончательный план выполнения работ

  • Значит, весь пакет программ выполняется за восемь условных единиц времени. Полученный план выполнения заданий в примере совпадает с оптимальным, т.к. более "короткого" расписания найти невозможно. В общем случае это свидетельствует о том, что данный алгоритм диспетчера "хороший", но не обеспечивает точного решения задачи оптимального распараллеливания.Точное же решение такой задачи, ввиду ее высокой сложности, не может служить основой оперативного диспетчера ВС.




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