Применение алгоритмов шифрования Политики безопасности Протокол аутентификации Безопасность IP (IPSec) Использование сертификатов для обеспечения безопасности

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

Вообще говоря, методы распределения наборов задач существенно зависят от мощности набора, момента его поступления, времени обработки отдельных задач на каждой машине, связности задач, степени однородности компонент системы, методов обмена информацией между отдельными компонентами и т. д. Однако многие из указанных параметров известны, как правило, с невысокой достоверностью. Кроме того, учет всех параметров при распределении задач необычайно сложен, в связи с чем обычно строятся распределения при различных упрощающих ограничениях. Широкое распространение при распределении процессоров в случае параллельных вычислений получили методы теории расписаний. Наибольший эффект при этом достигается, если набор задач на распределение поступает одновременно и известно время реализации каждой задачи.

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

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

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

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

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

Информатика, черчение, математика