Методы введения структурной избыточности в программы

 

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

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

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

При N-версионном программировании подготавливаются N -версий программ, и правильный результат определяется по мажоритарному признаку при помощи аппаратных или программных средств.

При дуальном или N -версионном программировании требуется в два или N раз больше времени для вычислений, если последние выполняются последовательно во времени. Кроме того, объем труда программистов возрастает во столько же раз.

Дуальное и N -версионное программирование целесообразно использовать в случае, если имеет место нагруженное резервирование вычислительной аппаратуры [1, 2, 51].

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

Обозначим погрешность первой программы через δ ₁ и допустимую погрешность второй программы через δ ₂. Пусть вероятность отказа (возникновение погрешности значительно больше допустимой) первой программы составляет q ₁ и второй программы – q ₂.

При независимости этих программ возможны следующие несовместимые события:

1) обе программы работают безотказно, вероятность возникновения этого события , погрешность результата – δ ₁;

2) откажет основная программа, вероятность возникновения этого события , погрешность результата – δ ₂;

3) откажет резервная программа, вероятность возникновения этого события , погрешность результата – весьма значительная, допустим δ ₃ (погрешность отказавшей резервной программы);

4) откажут и основная, и резервная программы, вероятность возникновения этого события , погрешность δ ₃.

Средняя погрешность неотказавшей системы из двух программ равна:

 

 

,

 

при вероятности отказа системы:

 

.

 

В случае, когда имеется только основная программа, погрешность результата равна δ ₁, а вероятность отказа – .

Пример расчета надежности и точности системы с применением модифицированного дуального программирования. Пусть δ ₁ = 0, 01; δ ₂ = 0, 1; q ₁ = 0, 05; q ₂ = 0, 001. Тогда и .

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

Решающим органом при этом является простейшая программа, которая сравнивает результаты работы грубой и точной программы и реализует алгоритм:

 

у ₁ – результат первой программы;

у ₂ – результат второй программы.

 

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

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