Централизованное диспетчирование

В более сложном виде задача диспетчирования возникает в централизованных ВС. В чем она заключается?

Пусть некоторый супервизор, например, в системе реального времени, определил множество информационно взаимосвязанных задач (частично — упорядоченное множество задач), которые должны решаться циклически, а возможно, и единственный раз процессорами ВС. Известны временные оценки решения задач.

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

Рис. 8.3. Информационный граф и расширенная матрица следования

Показана соответствующая ему матрица следования S и расширенная матрица следования S*, содержащая и столбец весов.

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

Формально: пусть задано множество работ A = {

1 , ...,

m} и известно множество временных оценок этих работ T = {t1 , ..., tm}, а также известна частичная упорядоченность, задаваемая матрицей следования S. Пусть ВС — однородная (т.е. все процессоры обладают одинаковой производительностью) и содержит n процессоров. Пусть в результате распределения множества работ A между n процессорами каждый (i-й) процессор оказался занятым решением задач в течение времени Ti. Тогда время решения всей совокупности задач

Задачей диспетчера является распределение работ

1,...,

m между процессорами, обеспечивающее

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

Содержание раздела