[стр.-0]
Обеспечение отказоустойчивости алгоритмов
Абу Знейт Рушди Салим Х. (rushdi zneit@hotmail.com)
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
Проблема отказоустойчивости схем, устройств и систем изучается уже давно. Она особенно актуальна в тех случаях, когда ремонт и восстановление технического состояния объекта затруднены или вообще невозможны. Самым распространенным методом обеспечения отказоустойчивости считается введение и использование структурной избыточности. Очень популярным является троирование объектов с мажоритарным органом для выбора «2 из 3» правильного результата. В статье рассматривается алгоритмический восстанавливающий орган, в котором используются операции сравнения и учитывается последовательный характер обработки данных. Последнее обстоятельство позволяет внести изменения в анализ отказоустойчивости алгоритмов, так как не все сравниваемые результаты вычислений равноправны.
При разработке методов обеспечения отказоустойчивости алгоритмов следует принимать во внимание их модульную структуру. Поэтому отказоустойчивость алгоритмов рассматривается на уровне их вычислительных модулей. Каждый модуль характеризуется входным набором данных Dex и выходным набором данных Debix. Последний может сравниваться с аналогичными наборами других модулей. Если указанные наборы относятся к модулю Mj, то в обозначениях появляется соответствующий индекс: Dlex, Dleых.
Отказы при реализации алгоритмов приводят к появлению ошибок в Dleых.
Ошибочный набор данных в отказоустойчивых алгоритмах не должен быть пропущен в следующую обработку. Поэтому разрабатываются избыточные структуры алгоритмов, в которых используется троирование вычислительных модулей [1,2,3]. Будем модули с тройным резервированием называть ТМР-модулями.
Ошибки в выходных наборах вычислительных модулей могут возникать при отказах:
а)хранения программ ;
б)вызова программ на исполнение;
в)выполнения программ.
D=D2 | |
С
конец
Рис. 1. Схема алгоритма восстанавливающего органа для t=1
Из него следует, что восстанавливающий орган для борьбы с однократными отказами
состоит из двух условий и двух присвоений. Целесообразно считать набор данных D1
ведущим, так как при отсутствии отказов именно он будет выходом ТМР-модуля. Набор
21
данных D будем считать резервным, так как при ошибках в ведущем наборе D именно
23
D продолжит обработку. А набор данных D будем считать только голосующим, так как
он никогда не используется для последующий обработки. Его функция состоит в
определении ошибок в ведущем или резервном модуле.
Для обнаружения ошибок и блокирования неправильного выходного набора данных используется структурная избыточность для организации ТМР-модулей. Если считать, что за время выполнения выбранного набора из к одинаковых модулей ТМР-системы возникает t отказов, приводящих к ошибкам в r выходных наборах, то они могут быть блокированы, если выполняется следующее неравенство:
к > 2t +1
Для этого должен быть построен восстанавливающий орган. Возможная схема алгоритма восстановления правильного результата при однократном отказе (t = 1) показана на рис.1.
/ | D | / | |
С
! [D = BO(D ,D2 D )
конец
Рис. 2. Схема алгоритма ТМР-модуля
Оценим характеристики ТМР-модуля. Вероятность ошибки определяется по формуле, учитывающей работу ТМР-модуля по исправлению ошибок:
Po = Peо +(1 - 2Peо ЬРм - Рм ),
где: Peo - вероятность ошибки восстанавливающего органа;
Схема алгоритма ТМР-модуля для борьбы с одиночными отказами за счет использования трех одинаковых модулей M\,M2 M3 показана на рис.2. Хранение, вызов и
выполнение вычислительного модуля троированы. В результате восстанавливающий орган заблокирует ошибочный выход данных при появлении одиночного отказа, т. е. появлении ошибки в одном из трех вычислительных модулях.
