Планирование работы ОУВС

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

Однократное выполнение алгоритма называют периодом цикла решения и обознается Tцр.

Алгоритм может быть представлен в виде графа ИС.

D = ( W, P, Г )

Тактом решения — называется интервал времени в течении которого произведена 1 элементарная проверка.

Предположим что такты контроля = тактам решения и постоянные:

В качестве результата планирования работы ВС выступает диаграмма загрузки (ДЗ). В ней по вертикальной оси откладывается ЭМ, а по горизонтальной время:

(ДЗ1)

Для планирования работы ОУВС в общем случае требуется 3 этапа:

1. Построение ДЗ P1 не учитывающей диагностических операций. Цель построения — минимизация времени решения при заданном количестве ЭМ и заданном графе ИС. Существует ряд эвристических алгоритмов позволяющих построить такую диаграмму.

2. Точный алгоритм — это полный перебор всех возможных вариантов.

3. Построение P2 — трансформация ДЗ P1. Цель — освободить max возможное количество ЭМ задействованных в решении прикладной задачи, при этом время решения не должно превышать max. Tцр <= Tцр_max

4. P3 — дополнение ДЗ P2. Дублирующимися фрагментами прикладных задач согласно заданному ДГ.

(ДЗ2)

Для построения ДЗ P1 используется следующий алгоритм:

(ДЗ3)

1й алгоритм: из множества фрагментов случайным образом выбираются фрагменты которые будут решаться на данном такте.

[+]:высокая скорость

[-]:граф не анализируется => эффективность зависит от случайной величины.

2й алгоритм: выбираются вершины с наибольшим количеством исходящих связей, то есть в 1ю очередь планируется решить те фрагменты, результаты решения которых наиболее востребованы в качестве исходных данных.

3й алгоритм: приоритет при выборе имеют вершины min отстоящие от начальных

4й алгоритм: выбирается вершина, длина пути которой от конечной max

5й алгоритм: комбинация из выше перечисленных.