Метод списочных расписаний.

Планирование для единичного ББ заключается в построении как можно более короткого плана. Поскольку эта проблема имеет переборный характер, внимание было сосредоточено на эвристических алгоритмах планирования. Среди таких алгоритмов наиболее подходящими оказались списочные расписания. Алгоритмы планирования по списку при линейном росте времени планирования при увеличении числа планируемых объектов, дают результаты, отличающиеся от оптимальных всего на 10-15%.

В таких расписаниях оператором присваиваются приоритеты по тем или

иным эвристическим правилам, после чего операторы упорядочиваются по

убыванию или возрастанию приоритета в виде линейного списка. В процессе

планирования затем осуществляется назначение операторов процессорам в по-

рядке их извлечения из списка.

На рисунке (а) представлена исходная ЯПФ. Номера вершин даны внутри

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

ветствущим алгоритмам и примем значения этих характеристик в качестве ве-

личин приоритетов этих вершин.

В первом расписании величина приоритета вершины есть ее уровень. Это

расписание УР. Во втором расписании величина приоритета вершины есть ее

уровень без учета времени исполнения, то есть здесь веса всех вершин полага-

ются одинаковыми (единичными).

УР	УР без учета веса
П	В	П	В

б) Приоритеты и списки вершин

(П— приоритеты, В — номера вершин)

в) Уровни вершин

номера вершины

уровни

г) Реализация расписаний (Р1, Р2 — процессоры, X — простой процессора)

УР (по уровню вершин)

Р1

Р2

Х

Х

УР без учета веса вершин

Р1

Х

Х

Р2

Х

Х

Х

Х

Об оптимальности расписания можно судить по количеству простоев про-

цессоров. Первое расписание дает 2, второе — 5.

Дата добавления: 2015-07-08