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

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

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

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

При 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 раз.

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

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

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

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

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