Графовые модели ОУВС

Алгоритм поиска единичных отказов

1.Принцип расширяющихся областей:

Самодиагностика осуществляется группой ЭМ. В процессе взаимных проверок машинами данной группы гарантируется исправность данных машин. Далее машины из этой группы проверяют соседние ЭМ, определяя их исправность (неисправность). В дальнейшем процессе диагностирования участвуют все ЭМ исправность, которых подтверждена.

[-]: нет гарантированного времени окончания проверки

2.Принцип распределенного ядра:

ЭМ производят взаимные диагностические проверки. Делается предположение о состоянии участников по результатам проведенной проверки.

[-]: большая нагрузка на ЛС

Тот или иной принцип выбирают в зависимости от параметров конкретной ВС и задач планируемых к решению.

Один из принципов отказоустойчивых вычислений — это голосование. Особенно часто используется в системах реального времени!

[--]:требуется большая структурная избыточность.

[+]:при заданной мере диагностируемости определение отказавшего узла происходит в реальном времени.

Мера диагностируемости — это количество ЭМ одновременный выход из строя которых будет обнаружен за цикл диагностирования.

6. Методы диагностирования:

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

[-]:

· фактически нет оценки вычислительной способности

· синхронизация времени

· сам таймер является устройством, которое может выйти из строя, соответственно в результате проверки будет зафиксирован отказ машины при отказе таймера.

2.Решение двумя ЭМ одного и того же фрагмента задачи в одно и то же время с последующим сравнением результатов.

Для сокращения объема передаваемых данных в качестве результата может выступать контрольная сумма

полученного результата. В этом случае в состав ЭМ не требуется вводить дополнительное устройство в виде таймера.

Большинство процессов происходящих в ВС можно описать с помощью графов.

1.Графы информационных связей (графы ИС):

D = ( W, P, Г ), где W - множество фрагментов решаемого набора прикладных задач,

P — множество весов фрагментов прикладных задач определяющих трудоемкость

Г — множество ИС между фрагментами.

Это означает что результат

выполнения фрагмента w1

является исходным данными

для фрагмента w2.

В общем случае величина Pi определяет сложность задачи — являющейся много приоритетной. Однако для однородных систем Pi определяется только свойствами задач.

Для упрощения задач планирования во многих случаях определяют фрагмент с большей трудоемкостью, разбивают на цепочки фрагментов с трудоемкостью = min.

Такое разбиение позволяет

не учитывать трудоемкость

при решении задач планирования.

Графы ИС позволяют описать задачу. Однако никак не учитываются особенности самой ВС и операций необходимых для обеспечения отказоустойчивости.

Для описания диагностических операций и структуры системы используется диагностический граф (ДГ): G = ( U, T ), где U — множество ЭМ входящих в состав ВС, T — множество диагностических связей между ЭМ.

Связи в ДГ могут быть как направленные так и не направленные.

Если на связях не задано направление, то проверки называются симметричными, то есть в ходе проверки каждая ЭМ является как проверяемой, так и проверяющей. Если указано направление, то проверки — не симметричные. Соответственно выделяются контролирующая и контролируемая машина.

ДГ определяется мерой диагностируемости ВС.

ДГ не может содержать петель, так как проверка ЭМ самой себя — отсутствует ( нет смысла для выполнения этой операции).

Помимо меры диагностируемости, существует величина t0 — мера отказоустойчивости.

Данная величина определяется спецификой прикладной задачи и показывает количество ЭМ при которых из вычислительного процесса результат решения прикладной задачи еще будет востребован.

Мера диагностируемости — t.

В общем случае если t > t0, то не имеет смысла проводить проверку.