9. Алгоритм организации взаимных проверок эм

ВС решает множество фрагментов прикладных задач: W = {Wd}

Процесс решения каждого фрагмента в общем случае — это нахождение функции: fd(xd), где xd — исходные данные.

Если ЭМ исправна, то значение функции fd находится верно для любого x лежащего в области определения.

Будем считать, что если ЭМ исправна, то результат решения функции fd будет искажен на всей области определения. Тогда для проведения взаимной проверки достаточно найти решение функции f над одними и теми же исходными данными на 2х разных ЭМ:

(x) и (x).

При сделанных допущениях ошибка может быть выявлена путем сравнения полученных результатов: (x)=(x).

Если данное условие не выполняется, то это является признаком ошибки!

Если в ВС в каждый момент времени может отказать только 1 ЭМ, то для организации отказоустойчивых вычислений можно использовать следующий подход:

Если имеется множество ЭМ U={}, то все эти ЭМ делятся на пары. Каждый поступающий фрагмент прикладной задачи решается сразу на 2х ЭМ:и.

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

W1

Ui Uj

W2 W3

Ui Uk Uj Um

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

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

В случае не совпадения результатов в обеих образованных парах образуется 4е новые пары:

W1

Ui Uj

W2 W3

Ui Uk UjUm

W4 W5 W6 W7

Ui Ux UkUn Uj Uo UmUp

При совпадении результатов выявляется целая цепочка неправильных ответов. При не совпадении результатов образуется новая пара и т.д.

Следует отметить что процесс решения прикладных задач не останавливается даже при наличие отказов.

[+]:

• высока скорость получения данных о состоянии ЭМ

• нет необходимости проведения специальных процедур для выявления отказавших ресурсов.

[-]:

• требование большого количества ЭМ в системе половина ресурсов ВС тратиться на обеспечение отказоустойчивого решения

• при расхождении результатов фрагмента в паре на следующем шаге нельзя использовать фрагменты зависящие по данным от фрагмента на предыдущем шаге.

10. Методы дешифрации синдрома

Синдром — это совокупность результатов взаимных проверок ЭМ.

Дешифрация синдрома — это определение состояния каждой ЭМ входящей в состав ВС ( исправной / неисправной ) .

Результаты проведения взаимных проверок могут храниться в виде ДГ с маркированными дугами.

Матрица смежности такого графа — матрица синдрома. На практике чаще всего присутствует случай, когда одно и то же множество проверок производится многократно в каждом цикле диагностирования.

T — множество элементарных проверок.

T | =m, m — мощность элементарных проверок ( количество проверок )

Одни и те же проверки производятся до реконфигурации ВС.

В этом случае целесообразно отдельно хранить ДГ без результатов проверок и результаты.

Тогда результаты представляются в виде вектора Sk, который содержит m элементов:

Sk = (S1, S2, … , Sm)

Порядок элементов в векторе является произвольным.

Важно чтобы одни и те же позиции сохранялись за элементами во всех циклах диагностирования.

Методы дешифрации синдрома ВС делятся на 3 группы:

1.Табличные методы

2.Аналитические методы

3.Графовые методы.