Обеспечение отказоустойчивости алгоритмов

Абу Знейт Рушди Салим Х. (rushdi zneit@hotmail.com)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

Проблема отказоустойчивости схем, устройств и систем изучается уже давно. Она особенно актуальна в тех случаях, когда ремонт и восстановление технического состояния объекта затруднены или вообще невозможны. Самым распространенным методом обеспечения отказоустойчивости считается введение и использование структурной избыточности. Очень популярным является троирование объектов с мажоритарным органом для выбора 2 из 3 правильного результата. В статье рассматривается алгоритмический восстанавливающий орган, в котором используются операции сравнения и учитывается последовательный характер обработки данных. Последнее обстоятельство позволяет внести изменения в анализ отказоустойчивости алгоритмов, так как не все сравниваемые результаты вычислений равноправны.

При разработке методов обеспечения отказоустойчивости алгоритмов следует принимать во внимание их модульную структуру. Поэтому отказоустойчивость алгоритмов рассматривается на уровне их вычислительных модулей. Каждый модуль характеризуется входным набором данных Dex и выходным набором данных Debix. Последний может сравниваться с аналогичными наборами других модулей. Если указанные наборы относятся к модулю Mj, то в обозначениях появляется соответствующий индекс: Dlex, Dleых.

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

Ошибочный набор данных в отказоустойчивых алгоритмах не должен быть пропущен в следующую обработку. Поэтому разрабатываются избыточные структуры алгоритмов, в которых используется троирование вычислительных модулей [1,2,3]. Будем модули с тройным резервированием называть ТМР-модулями.

Ошибки в выходных наборах вычислительных модулей могут возникать при отказах:

а) хранения программ ;

б) вызова программ на исполнение;

в) выполнения программ.

С

конец

Рис. 1. Схема алгоритма восстанавливающего органа для t=1

Из него следует, что восстанавливающий орган для борьбы с однократными отказами

состоит из двух условий и двух присвоений. Целесообразно считать набор данных D1

ведущим, так как при отсутствии отказов именно он будет выходом ТМР-модуля. Набор

данных D будем считать резервным, так как при ошибках в ведущем наборе D именно

D продолжит обработку. А набор данных D будем считать только голосующим, так как

он никогда не используется для последующий обработки. Его функция состоит в

определении ошибок в ведущем или резервном модуле.

Для обнаружения ошибок и блокирования неправильного выходного набора данных используется структурная избыточность для организации ТМР-модулей. Если считать, что за время выполнения выбранного набора из к одинаковых модулей ТМР-системы возникает t отказов, приводящих к ошибкам в r выходных наборах, то они могут быть блокированы, если выполняется следующее неравенство:

к > 2t +1

Для этого должен быть построен восстанавливающий орган. Возможная схема алгоритма восстановления правильного результата при однократном отказе (t = 1) показана на рис.1.

С

! [D = BO(D ,D2 D )

конец

Рис. 2. Схема алгоритма ТМР-модуля

Оценим характеристики ТМР-модуля. Вероятность ошибки определяется по формуле, учитывающей работу ТМР-модуля по исправлению ошибок:

Po = Peо +(1 - 2Peо ЬРм - Р'м ),

где: Peo - вероятность ошибки восстанавливающего органа;

Схема алгоритма ТМР-модуля для борьбы с одиночными отказами за счет использования трех одинаковых модулей M\,M2 M3 показана на рис.2. Хранение, вызов и

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

Рм - вероятность ошибки одного модуля.

Предполагается, что все три модуля имеют одинаковую надежность. Тогда выигрыш в надежности ТМР-модуля по сравнению с одним модулем будет определяться следующим отношением:

r = м = ± м

Po Рво + (1 2Рво )(2 Рм )РМ

Выигрыш отсутствует, если r = 1. При r > 1 выигрыш составляетr раз . При r < 1

получается проигрыш раз.

В табл.1 и на рис.3 показана зависимость выигрыша от вероятностей ошибок в модуле Рм и в восстанавливающем органе Рво .

Из расчетных данных можно сделать следующие выводы.

1 . Выигрыш гарантируется при вероятности ошибки модуля большей 0.5.

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

3. Для каждого значения вероятности ошибок восстанавливающего органа существует предельное значение вероятности ошибки модуля, при котором проигрыш превращается в выигрыш.

4. Проигрыш сохраняется тем дольше, чем больше вероятностей ошибки восстанавливающего органа.

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

расчеты для вероятности ошибки восстановления Рво вплоть до значения 0.45. А это в свою

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

Рис. 3. Зависимость выигрыша от применения ТМР-модуля от вероятностей ошибок в модуле и восстанавливающем органе

органа, может не дать выигрыша и даже привести к проигрышу. Например, при Рм = 0.3 и

Рво = 0.3 получаем проигрыш в 1.2 раза.

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

Таблица 1 .

Литература

1. Данько Ю.П. Методы и средства обеспечения эффективности механизмов отказоустойчивости вычислительных систем. М.: ИТМиВТ. 1990, -52 с.

2. Gilles Muller, Michel Banatre, Nadine Peyrouze, Bruno Rochat. Lessons from FTM: An Experiment in the Design & Implementation of Low-Cost Fault-Tolerant System IEEE Transaction on Reliability, Vol. 45, No. 2, 1996 JUN. -pp. 332-340.

3. Hagbae Kim, Kang G. Shin Sequencing Tasks to Minimize the Effects of Near-Coincident Faults in TMR Controller Computers IEEE Transaction on Computers. Vol. 45, No. 11, Nov. 1996, -pp.1331-1337.