Списочные расписания

ОБЩАЯ ХАРАКТЕРИСТИКА ПРИБЛИЖЕННЫХ МЕТОДОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ И ИХ ОЦЕНКИ

Списочные расписания

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

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

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

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

,

где - число идентичных процессоров обработки информации. В качестве примера можно определить, что при ошибке между алгоритмом по критическому пути и оптимальным распределением не превышает 16,7%. При изучении сегментации массивов во внешней памяти часто используется квадратический критерий:

,

где - время, за которое процессор обслуживает задания, распределенные с помощью списка и по другому принципу. Для данного критерия справедливо неравенство:

.

Если использовать другой квадратический критерий, а именно

,

то для такого случая доказано неравенство:

.

Если отношение частичного порядка на выполнения заданий является деревом, то доказано, что

.

Таким образом, метод критического пути является одним из наиболее применимых и дает приемлемые результаты не только для независимых РЗ, но и для зависимых.