Введение в архитектуру компьютеров


Распределение задач по процессорам - часть 2


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

Известны два подхода к проблеме диспетчирования. При первом каждая задача из входного набора предварительно назначается для обслуживания на некоторую машину. Задачи начинают выполняться только после окончания диспетчирования всего входного набора. Метод, основанный на таком подходе, называют статическим диспетчированием. Задача статического диспетчирования допускает оптимальное решение, которое в принципе можно получить полным перебором возможных вариантов. Однако с ростом числа вариантов эффект от использования оптимального распределения (по сравнению с некоторым случайным распределением) может быть сведен на нет трудоемкостью получения оптимального результата.

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

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

Чаще всего в качестве критерия работы диспетчера выбирается время выполнения всего набора задач, хотя используются и другие критерии: минимальное время простоя (максимальная загрузка) различных устройств МВС; минимальное среднее время ожидания решения для всего набора задач; минимальное число используемых процессоров при заранее заданном времени окончания решения задач и т. д. Иногда используются обобщенные критерии в виде функции, устанавливающей зависимость между отдельными частными критериями. Качество диспетчера тогда – отклонение от экстремального значения обобщенного критерия. Большую сложность здесь представляет процедура обоснованного формирования функции, задающей обобщенный

критерий.




Начало  Назад  Вперед



Книжный магазин