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

Лекция 14

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

План

1. Понятие о дуальном и N-версионном программировании.

2. Модифицированное дуальное программирование.

3. Виртуальные машины в надежности.

4. Избыточность операционной системы ИС.

Ключевые слова

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

Рекомендуемые материалы

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

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

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

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

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

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

         

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

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

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

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

Избыточность операционной системы

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

Повышение надежности программ обеспечит применение принципа виртуальной машины в случае мультипрограммной обработки.

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

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

При этом важна высокая степень изоляции каждой виртуальной машины. Тогда ошибка в программе одной виртуальной машины не влияет на другие.

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

На рис. 1 изображена структура мультипрограммной обработки на одном компьютере без применения принципа виртуальной машины. Пользователи П₁, П₂, … , П_n имеют общую операционную систему ОС. Ошибка в ОС выводит из строя всех пользователей. На рис. 2 изображена структура системы с виртуальными машинами высокой степени изоляции. Только ошибка в сравнительно небольшой программе – мониторе М влечет за собой нарушение работы пользователей П₁, П₂, … , П_n. Отказы индивидуальных операционных систем ОС₁, ОС₂, … , ОС_n вызывают нарушения в работе только «своего» пользователя.

        

Метод контрольных функций.

Методы введения избыточности в программы основаны на повторении программ в различных версиях (дуальное, N-версионное программирование). Такие методы повышения надежности не экономичны как в смысле расхода ручного труда программиста, так и в смысле использования объема памяти для записи программ, так и экономии машинного времени.

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

Простейшим примером применения метода контрольных соотношений является вычисление функций и по отдельным программам. Контрольным соотношениям в данном случае будет соотношение .

Пусть имеются две независимые программы, вычисляющие числовые функции ƒ₁ и ƒ₂ (аргументы функции для простоты записи опущены). Необходимо исправлять любую одиночную ошибку в программах. Опишем подход, требующий три дополнительные программы, вычисляющие значения вспомогательных контрольных функций ƒ₃, ƒ₄, ƒ₅ [1]. Эти функции могут, например, удовлетворять уравнениям

                            (1)

,

где a_ij ≠ 0 – произвольные постоянные.

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

 (1) была построена на основе контрольной матрицы (код Хэмминга) [ ]. Система

.

Для построения контрольных функций   при i = 1,…, r, где a_ij – постоянные, необходимо выбрать двоичную  матрицу [h_ij] с отличающимися друг от друга столбцами, не равными нулю, а затем применить соотношение

,                                                         (2)

где  произвольные постоянные.

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

Пример исправления одиночной ошибки с помощью контрольных функций. Пусть вычисляются четыре функции ƒ₁, ƒ₂, ƒ₃, ƒ₄. Необходимо построить систему, позволяющую исправлять ошибку в одной из функции. Для построения системы уравнений используется матрица Н Хэмминга вида

.

Выбирая коэффициенты d_ij равными единице, непосредственно по матрице Н с учетом (2) записывается система уравнений:

,

,

,

где дополнительные контрольные функции ƒ₅, ƒ₆ и ƒ₇ определяются по следующим очевидным соотношениям: ; ; . Если, например, возникает ошибка е₂ при вычислении функции ƒ₂, то , . По виду синдрома () определяется, что ошибка соответствует второму столбцу матрицы Н, т.е. ошибка е₂ относится к функции ƒ₂ и последняя может быть скорректирована вычитанием этой ошибки.

Аналогично исправляются ошибки и в функциях ƒ₁, ƒ₃, ƒ₄.

Контрольные вопросы и задания.

1. Какие существуют методы повышения надежности ПО?

2. Определите разницу между дуальными и N-версионным программированием.

Вместе с этой лекцией читают "7. Особенности организации и управления".

3. Что такое мультимпрограммный режим работы компьютера?

4. Дайте определение понятию монитор.

5. В каких случаях используется модифицированное дуальное программирование?

6. Почему при мультипрограммной обработке информации используют принцип виртуальных машин?

7. Оцените общее число ошибок в тексте программы, если программа проверена тремя специалистами и если первый из них нашел в программе 3 ошибки, второй – 5 ошибок, а третий – 6 ошибок, причем две ошибки из найденных были общими у всех специалистов.

Литературы: 2,3,6, 8,11