Реферат: Списочные расписания
ОБЩАЯ ХАРАКТЕРИСТИКА ПРИБЛИЖЕННЫХ МЕТОДОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ И ИХ ОЦЕНКИ
Списочные расписания
Списочные расписания отличатся простой в построении и реализации и характеризуются достаточно высокой эффективностью с точки зрения времени выполнения ПП. Практически во всех случаях цель рассматриваемых расписаний является минимизация времени выполнения ПП, за которое при учете только детерминированных факторов принимается время от момента начала и до момента завершения выполнения ПП, а при учете также и вероятных факторов – среднее значение этого времени. Затраты машинного времени на расписания в динамике выполнения программ обычно не включаются в величину времени выполнения ПП, а рассматриваются отдельно, принимая меры к их уменьшению. Необходимо отметить, что те расписания, которые обеспечивают меньшее в среднем значения времени выполнения ПП, являются более эффективными и дают более точное решения задачи планирования ПВП.
Физический смысл списочных расписаний можно помнить таким образом. По мере того как в динамике вычислительного процесса РЗ ПП становятся готовыми к исполнению, а процессоры освобождаются от выполнения ранее назначенных на них РЗ, осуществляется выбор новых РЗ и их распределения по процессорам таким образом, чтобы по возможности уменьшить задержки в ПВП.
Реализация списочных расписаний основана на применении линейных списков РЗ, упорядоченных по убыванию (невозрастанию) приоритетов в соответствии с принятым алгоритмом выбора РЗ. При этом списки могут быть как статическими, так и динамическими обновляемыми по мере выполнения и имеют наиболее высокие приоритеты.
В данной работе рассматриваются в основном РЗ независимые друг от друга, которые могут выполняться на любом из идентичных процессоров. Одним из наиболее популярных списочных расписаний является алгоритм упорядочения по критическому пути (МСР). В этом случае список составляется в порядке убывания величин РЗ. Если обозначить время завершения РЗ при работе МСР как, а оптимальное расписание как, то выполняется очень важное неравенство :
,
где — число идентичных процессоров обработки информации. В качестве примера можно определить, что при ошибке между алгоритмом по критическому пути и оптимальным распределением не превышает 16,7%. При изучении сегментации массивов во внешней памяти часто используется квадратический критерий:
,
где — время, за которое процессор обслуживает задания, распределенные с помощью списка и по другому принципу. Для данного критерия справедливо неравенство:
.
Если использовать другой квадратический критерий, а именно
,
то для такого случая доказано неравенство:
.
Если отношение частичного порядка на выполнения заданий является деревом, то доказано, что
.
Таким образом, метод критического пути является одним из наиболее применимых и дает приемлемые результаты не только для независимых РЗ, но и для зависимых.