Исследование результатов работы реализованной среды исполнения

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

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

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

Если бы все ошибки являлись одиночными, тогда из ситуации, когда несколько мультиверсий произвели вычисления с ошибкой, следовало бы, что их результаты не равны между собой. Однако на практике возникают ситуации, когда несколько модулей возвращают одинаковый неверный результат и, следовательно, содержат одинаковую ошибку в программной архитектуре. Такие ошибки будем называть межверсионными. Следует отметить, что существуют методики и рекомендации по проектированию программных систем, которые позволяют снизить вероятность появления ошибок данного вида, но, как показывает практика, полностью их исключить не удается [ 22 ].

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

Очевидно, что гарантировать максимально надежное функционирование системы можно только при выполнении следующих условий:

1. Для каждой ошибки существует, как минимум, один модуль, ее не содержащий.

Рисунок 3.3. Множество выходов мультиверсионной системы с тремя программными модулями

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

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

Рисунок 3.4. Множество выходов мультиверсионной системы с тремя модулями, имеющими общие ошибки

2. Количество областей межверсионных ошибок должно быть меньше половины общего количества модулей, либо общее количество модулей должно быть достаточно велико.

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

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

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

Рисунок 3.5. Общая функциональная модель имитационной среды

Схема функционирования данной системы будет следующей:

· Модуль ввода передает СМВИ в качестве входных данных требуемые надежностные характеристики программных модулей (вероятности одиночных и межверсионных ошибок, максимальное количество модулей, содержащих одинаковую ошибку).

· СМВИ передает эти данные программным модулям.

· По команде выполнения вычислений (от СМВИ) программные модули генерируют одиночные и межверсионные ошибки с требуемой частотой.

· Блок принятия решений определяет корректный результат всей системы.

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

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

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

Введем обозначения:

i – номер программного модуля;

Pi – вероятность ошибки программного модуля i;

Qi – вероятность безотказной работы программного модуля i
(Qi = 1-Pi);

Ni – количество сгенерированных i-м программным модулем
ошибок;

Pм – вероятность межверсионной ошибки в нескольких модулях;

Nм – количество сгенерированных межверсионных ошибок;

S – номер текущего этапа вычислений (так как процесс
обработки информации, в общем случае, происходит в
несколько этапов [4]);

e, h – некоторые случайные величины из интервала от 0 до 1;

q – случайная величина, принимающая значение -1 или +1;

Xi – значение возвращаемое i-м программным модулем;

Y – абсолютно истинное значение (фиксированное или заранее
известное всем модулям);

∆x – максимально допустимое отклонение Xi от Y, при котором
Xi все еще можно считать корректным.

Будем считать, что i-й программный модуль завершил выполнение с ошибкой, если возвращаемая им величина Xi отклоняется от образца Y более чем на некоторый порог ∆x (рисунок 3.6). Причем ∆x должен быть отличным от нуля, т.к. некоторые алгоритмы принятия решений используют в процессе выполнения степень равенства результатов [3,29].

Рисунок 3.6. Зависимость выхода мультиверсии от параметра r

Формально это можно записать следующим образом:

X_i = Y + r ∙ ∆x.

Таким образом, придав параметру r значение из диапазона от -1 до +1, мы обеспечим на выходе «корректный» результат, а присвоив r любое другое значение – «ошибочный», причем r регулирует степень «ошибки». Остановимся на том, по какому правилу следует присваивать то или иное значение данному параметру. Очевидно, что r должен зависеть от вероятности ошибки i-го программного модуля Pi и некоторой случайной величины e для того, чтобы модули, обладающие одинаковой вероятностью ошибки, не генерировали их одновременно. В качестве основы такой зависимости выберем периодическую функцию с периодом M=1 / Pi. Например, линейную функцию:

f(S) = {S / M},

где {} – операция получения дробной части числа.

Учитывая, что M=1 / Pi, получаем:

f(P_i, S) = {S ∙ P_i}.

Добавим элемент случайности:

g(P_i, S) = f(P_i, S) + t ∙ e = {S ∙ P_i} + t ∙ e,

где t – некоторый коэффициент, определяющий уровень влияния случайности на выход программного модуля.

Так как множество значений функции f(x) лежит на отрезке [0;1], то и коэффициент t тоже должен принадлежать этому отрезку и не превышать 1.

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

(g > E_g) → ошибка.

Однако, ввиду влияния случайной величины t∙e, необходимо следить, чтобы количество сгенерированных ошибок Ni не превышало количество ошибок, ожидаемых к текущему этапу обработки данных Pi ∙S:

N_i / (P_i ∙ S) ≤ 1.

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

, в противном случае.

, если [ g(Pi, S) > Eg ] и [ Ni / (Pi ∙ S) ≤ 1 ],

Вместо (4 + i∙h)∙ q можно использовать и любую другую функцию, удовлетворяющую следующим условиям:

· каждый программный модуль имеет уникальные одиночные ошибки;

· в окрестности ∆x от любого «ошибочного» значения одной мультиверсии нет «ошибок» других мультиверсий.

Экспериментально было установлено, что для Eg оптимальным значением является 0,85, а для t – 0,5. Характер Xi при этих значения представлен на рисунок 3.7. На данном рисунке по оси абсцисс откладываются итерации i -го модуля, а по оси ординат – отклонение выходного значение от «корректного». Отклонение от Y более чем на ∆x считается ошибкой.

 

Рисунок 3.7. Характер выходных значений генератора ошибок при E_g=0,85 и t=0,5.
(100 значений, вероятность ошибки 0,07)

Генерация межверсионных ошибок будет осуществляться аналогично генерации одиночных ошибок, но вместо Pi будем использовать Pм, а вместо Ni – Nm:

, в противном случае.

, если [ g(Pм, S) > Eg ] и [ Nм / (Pм ∙ S) ≤ 1 ],

Важным моментом в процессе генерации межверсионных ошибок является то, что решение о «наличии» межверсионной ошибки принимает лишь один из программных модулей, назначенный арбитром. Например, если в качестве арбитра выбран программный модуль с номером i=1, то он определяет, какое ошибочное значение Xм генерировать в качестве межверсионной ошибки, на каком этапе Sм она должна произойти, а также количество и номера модулей, «содержащих» эту ошибку. Указанные им модули возвращают нужное значение Xм в нужный момент Sм и увеличивают свои счетчики ошибок Ni, а арбитр увеличивает Nм. Сам арбитр может как участвовать в межверсионной ошибке, так и только управлять процессом ее генерации.

На основании изложенных принципов была реализована «Программная система «ИС-СМВИ v1.0» (имитационная среда для системы мультиверсионного исполнения программных модулей), прошедшая регистрацию в Отраслевом фонде алгоритмов и программ [8].

Ниже приведены полученные с помощью разработанной системы данные, характеризующие преимущества и недостатки наиболее перспективных алгоритмов принятия решения [6]. Исследовались следующие алгоритмы: голосование абсолютным большинством (ГАБ) и голосование согласованным большинством (ГСБ) [16], нечеткое голосование согласованным большинством (НГСБ) [29] и взвешенные варианты ГСБ и НГСБ, предложенные в [3]. Касаясь характеристик приведенных алгоритмов, отметим только, что алгоритм ГАБ выбирает тот результат из множества результатов программных модулей, который был возвращен абсолютным большинством из них, т.е. для N модулей правильный результат должны вернуть одновременно (N+1)/2 мультиверсий [ 30 ]. Второй алгоритм, ГСБ, при принятии решения опирается не на абсолютное большинство, а на максимально большую группу из представленных результатов. Например, если множество выходов есть {A,B,A,C,B,A,D,C}, то алгоритм ГСБ выберет “A”. Причем, алгоритмы ГАБ и ГСБ определяют группу равных выходов, исходя из факта их равенства друг другу [ 30 ]. Алгоритм НГСБ, в свою очередь, исходит из степеней схожести выходов друг с другом, и в этом заключается его основное отличие от предыдущих алгоритмов. Взвешенные варианты алгоритмов ВГСБ и НВГСБ используют в процессе своего функционирования еще и накапливаемую статистику «ошибок» мультиверсий [3].

 

Ситуация №1.

Исходные данные:

Количество мультиверсий: 3

Межверсионных ошибок нет.

Результат представлен на рисунок 3.8.

Методы ГАБ, ГСБ и НГСБ не смогли принять решение ни для одного значения вероятности ошибки Qмодуля существенно меньшего 1. Это связано с тем, что при даже при средней надежности одного модуля 0,99, вероятность того что все три модуля вернут различные результаты равна 0,0001. Следовательно, при достаточном количестве итераций, непременно возникнет ситуация неопределенности при принятии решения.

 

Ситуация №2.

Исходные данные:

Количество мультиверсий: 5

Межверсионных ошибок нет.

Результат представлен на рисунок 3.9.

Алгоритм ГАБ не смог принять решение для Qмодуля меньших 0,91. Алгоритм ГСБ не смог принять решение для Qмодуля меньших 0,80. У алгоритма ВГСБ наблюдается небольшое отклонение характеристики по сравнению с алгоритмом НВГСБ-0,5.

 

Ситуация №3.

Исходные данные:

Количество мультиверсий: 15

Межверсионных ошибок нет.

Результат представлен на рисунок 3.10.

Метод ГАБ не смог принять решение для значений Qмодуля, меньших 0,82. У алгоритма, реализующего метод ВГСБ, наблюдается аномалия в области значений вероятности безотказной работы мультиверсий до 0,67, причем, в отличие от остальных методов, его характеристика начинается не с 0, а, приблизительно, со значения, соответствующего 0,18, после чего, вплоть до 0,67, отказоустойчивость системы падает практически до нуля. При повторе теста с большим числом вложенных этапов, эта аномалия повторяется. Возможно, это связано с тем, что вероятность ошибки в данной области гораздо выше, чем вероятность корректного результата. После значения вероятности отказа выше 0,67, алгоритм ВГСБ оказывается несколько более эффективным, чем ГСБ. Линия, соответствующая алгоритму НГСБ-0,5, также демонстрирует большую эффективность, чем характеристика алгоритма ГСБ для всех значений вероятности отказа Qмодуля.

В области Qмодуля > 0,67 все значения, соответствующие вероятности отказа системы Qсистемы, выше 0,98.

Анализ показывает, что, начиная со значений вероятностей отказа 0,82, самым эффективным алгоритмом является ГАБ. Для него Qсистемы = 1.

Остальные методы распределились следующим образом (от более эффективного к менее эффективному): ВГСБ, НГСБ-0,5, ГСБ, НВГСБ-0,5. Так же, следует отметить, что увеличение порога среза снижает эффективность нечетких алгоритмов принятия решений. Скорее всего, это связано с характером распределения ошибок модулей в данном конкретном случае.

 

Ситуация №4.

Исходные данные:

Количество мультиверсий: 15

Вероятность межверсионной ошибки 0,000002 в 8 модулях.

Результат представлен на рисунок 3.11.

Алгоритм ГАБ не смог принять решение для значений Qмодуля, меньших 0,86. Аномальное поведение алгоритма ВГСБ повторилось. В целом, поведение алгоритмов принятия решения идентично предыдущему случаю, за тем только отличием, что все характеристики, кроме НВГСБ, идут несколько ниже, а разница между значениями ГСБ и НГСБ сократилась.

Выводы

Проведя анализ полученных зависимостей, можно сделать вывод о том, что наиболее универсальным алгоритмом принятия решений является взвешенное голосование согласованным большинством - ВГСБ. Алгоритм ВГСБ показал лучшие результаты во всех ситуациях, где средняя вероятность ошибки программного модуля не превышала 0,30. Следует также отметить, что алгоритм, реализующий голосование абсолютным большинством, позволяет добиваться очень высокой отказоустойчивости для систем, в которых все программные модули являются высоконадежными (средняя вероятность ошибки не превышает 0,15), и их количество достаточно велико. Это важно, так как алгоритм ГАБ является очень простым [3], и его использование позволит снизить (относительно других методом голосования) ресурсоемкость решения задачи для системы в целом. Все рассмотренные алгоритмы голосования обладают своими преимуществами и недостатками, поэтому для достижения максимальной эффективности функционирования каждой конкретной мультиверсионной системы управления следует проводить исследование всех характеристик этой системы. Затем, используя значения этих характеристик в среде ИС‑СМВИ, можно осуществить обоснованный выбор наиболее подходящего для конкретной системы управления алгоритма принятия решений.

Рисунок 3.8. Зависимость отказоустойчивости системы от отказоустойчивости отдельных модулей

 

Рисунок 3.9. Зависимость отказоустойчивости системы от отказоустойчивости отдельных модулей

 

Рисунок 3.10. Зависимость отказоустойчивости системы от отказоустойчивости отдельных модулей

Рисунок 3.11. Зависимость отказоустойчивости системы от отказоустойчивости отдельных модулей