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

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

Nmax = fn /п-4 - /п-1 4~ /п-З"

Таким образом, наибольшее сокращение количества ДНС как для нижней границы, так и для верхней достигается при наличии нулевых результатов контроля.

Сравнивая кольцевые структуры с минимальными и максимальными цепочными, можно сделать вывод об улучшении характеристик диагностируемости в первом случае. При этом верхняя граница количества ДНС снижается по меньшей мере на величину /„ , а минимальная граница может быть снижена до двух.

Применение кольцевых, минимальных структур обеспечивает возможность однозначной идентификации неисправных элементов. Множество таких элементов называют ядром неисправностей данной структуры взаимоконтроля. Ядро неисправностей Vc можно определить таким образом:

Vc = Vo{J {i I i eV.UVo-. [vi, V,) = 0), (3.10)

где Vo = {Vj IЗо/, Vi+i.....Vj+i: Vj, v,+i, ... , £ V

такие, что (о,-, 0;+,) = О, [Vj+i, Vf+2 = О, ... , {Vj+m-i,

f/+m)==0, {Vi+m, Vj= 1) либо {Vj, Vj+m) = Ц.

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

Оценивая эффективность использования кольцевых структур для анализа технического состояния отказоустойчивой системы, можно отметить значительное уменьшение количества дне. Так, Для рассмотренного ранее примера п = 13

3 5-541 65

сокращение числа ДНС по сравнению с полным перебором состояний работоспособности элементов достигается в 8192/ /(/12+ /ю) = 15,7 раза.

Таким образом, применение СВК обеспечивает существенное сокращение множества ДНС и тем самым повышает эф-фективностъ контроля и диагностирования в отказоустойчивых микропроцессорных системах.

3. ДИАГНОСТИРОВАНИЕ ХАРАКТЕРНЫХ НЕИСПРАВНОСТЕЙ

Поиск неисправных элементов в СВК путем полного перечисления неисправностей приводит к большим затратам машинного времени. Поэтому вводятся некоторые предположения, упрощающие поиск. Распространенным является предположение о том, что наиболее вероятен отказ наименьшего числа элементов системы.

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

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

Рассмотрим один из наиболее распространенных алгоритмов системы диагностирования без восстановления [461. При поиске неисправностей предполагается, что количество / одновременно неисправных элементов не превышает числа т (G), удовлетворяющего следующим условиям:

т(С)< [(«-l)/2j; т (G) < d„,„ (G), d„in = min Г (о,-).

В процессе диагностирования по данному алгоритму различают множество элементов, технические состояния которых задаются произвольным образом (эксплицитные назначения), и элементы, состояния которых являются следствием эксплицитных присваиваний (имплицитные назначения). Возможны два случая имплицитных назначений: при эксплицитном назначении элементу значения «исправен» {vf. = 0)

и «неисправен» (w-: = 1). В первом случае эксплицитное назначение порождает подмножества

f(0 = lo/O/: = 0=*O/: = l. Во втором случае

N{i)= 0;

В результате выполнения алгоритма получается подмножество Vp исправных элементов структуры G = G (V, Е) и подмножество V„ неисправных элементов. В процессе выполнения используется граф G{V, Е), получаемый при исключении вершин, входящих в подмножества Vp, Vh, и соответствующих им связей графа G {V, Е).

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

Алгоритм 1.

1. Присвоить 1р:= 0, Vh-:= 0; 0(У, Е)- = 0(У, Е).

2. Выбрать {Vi, Vj)£E, (о,-, о,-) = 1. Если такой дуги нет, то Vu - множество неисправных элементов и вычисление окончено.

3. Вычислить Л(/), F{j), при эксплицитном назначении Vj: = 0.

4. Если N{]) Г\ Е{})Ф 0, то принять : = 1 и вновь вычислить N{j), F(j).

5. а) если Fh U f (/) I < т (G) и и,- = О, то получить Ур:Ур\] N{j), V„: = Vh и F{}), поместить (о,-, N (j) U F{j)) в стек и перейти к шагу 2;

б) если I и f (/) I < т(G) и Vj= I, то получить Va. = Vi, и F(/). Если -значение v,- = 1 было присвоено на шаге 4, то перейти к шагу 2. В противном случае поместить множество f (/) в стек и перейти к шагу 2;

в) если I Vh и (/)! > т (G), то исключить (читать) записи из стека вплоть до первой пары {Vj, N(j) (J F{j)). В случае отсутствия такой пары в стеке, решения не существует и вычисление окончено. В противном случае все вершины, исключенные из стека, исключить из подмножества V„ и Vp. В качестве элемента v, принять элемент о,- связи (о,-, о,). Произвести назначение У/ = 1, вычислить N{j), F(j). Повторить шаг 5.