На правах рукописи

24,1,2,23,22,3,4,21,20,5,6,19,18,7,8,17,16,9,10,15,14,11,12,13

Котенок Андрей Владимирович

МУЛЬТИВЕРСИОННАЯ СРЕДА ИСПОЛНЕНИЯ

ДЛЯ ОТКАЗОУСТОЙЧИВЫХ ПРОГРАММНЫХ КОМПЛЕКСОВ

СИСТЕМ УПРАВЛЕНИЯ

05.13.01 – Системный анализ, управление и обработка информации

(космические и информационные технологии)

05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Красноярск – 2009

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева», г. Красноярск

Научный руководитель:

доктор технических наук,

профессор Ковалев Игорь Владимирович

Официальные оппоненты:

доктор технических наук,

профессор Терсков Виталий Анатольевич

кандидат технических наук,

доцент Царев Роман Юрьевич

Ведущая организация: Институт вычислительного моделирования Сибирского отделения РАН, г. Красноярск

Защита состоится 13 марта 2009 года в 14 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М. Ф. Решетнева по адресу: 660014, г. Красноярск, проспект имени газеты «Красноярский рабочий», 31.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева.

Автореферат разослан 12 февраля 2009 года.

Ученый секретарь

диссертационного совета Моргунов Е. П.

Актуальность работы.

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

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

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

Объектом исследования является программный комплекс критичной по надежности системы управления.

Предмет исследования – среда исполнения программного комплекса системы управления.

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

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

Для достижения цели требуется решить следующие задачи:

• Проанализировать существующие модели проектирования отказоустойчивого программного обеспечения.

• Разработать методику применения моделей для реализации программного комплекса системы управления.

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

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

• Реализовать и протестировать мультиверсионную среду программного комплекса системы управления.

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

Научная новизна результатов, полученных в диссертации, состоит в следующем:

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

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

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

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

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

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

Реализация результатов работы. В диссертационной работе были разработаны две программные системы, предназначенные для внедрения мультиверсионного подхода при проектировании программного комплекса системы управления. В рамках системы «СМВИ v1.0» предложена методика оценки эффективности мультиверсионных моделей в зависимости от количества мультиверсий, вероятностей их безотказной работы и качества проверочного модуля. Разработанная имитационная система «ИС-СМВИ v1.0» помогает выбрать мультиверсионную модель и наилучший алгоритм мультиверсионного голосования. Программные системы прошли экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ (ОФАП), что делает их доступными широкому кругу специалистов в области архитектуры, проектирования и разработки программного обеспечения отказоустойчивых информационно-управляющих систем.

На основе материалов диссертационной работы был разработан учебный курс, читаемый магистрам на кафедре «Системный анализ и исследование операций» Сибирского государственного аэрокосмического университета.

Апробация работы. Основные положения и результаты диссертационной работы прошли апробацию на международных и всероссийских научных конференциях: на всероссийских научных конференциях «Современные телекоммуникационные и информационные технологии» (2006), «Информационно-телекоммуникационные технологии и электроника» (2007), международных научных конференциях «Решетневские чтения» (2006), «Инновационные технологии» (2008).

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

Публикации. По материалам диссертации опубликовано 13 работ, включая публикации в журналах по Перечню ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, трех разделов и списка литературы из 121 наименования. Содержание работы изложено на 119 страницах.

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

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

Определяющим звеном мультиверсионной системы является блок принятия решения. Этот блок разделяет выходы многочисленных программных версий на «корректные» и «ошибочные». Существует несколько методик подобного разделения. Самые общие из них основываются на классификации выходов. Наиболее перспективными из этих методик являются голосование абсолютным большинством, голосование согласованным большинством, а также нечеткое голосование согласованным большинством. В рамках данной работы, автором был предложен ряд улучшений этих методик, а именно взвешенное голосование согласованным большинством и нечеткое взвешенное голосование согласованным большинством. Методики этой группы основаны на сравнении выходов мультиверсий и размещении идентичных из них в одинаковые классы (подмножества). Однако, в случаях, когда расчеты выполняются не с целыми числами определение, идентичны выходы или нет, является затруднительным. Для разрешения этой проблемы введем понятие соотношение равенства: мы будем говорить, что два числа равны, если они отличаются меньше, чем на некоторое допустимое отклонение. Эти соотношения не требуют выполнения свойства транзитивности. Иными словами, если известно, что |a ‑ b| < ε и |b ‑ c| < ε, то отсюда не следует что |a ‑ c| < ε, где a, b и c – некоторые числа. Потенциальной проблемой методик данной группы является возможная неверная классификация выходов, и как следствие, неверное принятие решения, что, в конечном счете, способно привести к отказу системы управления.

Вторая группа методик принимает решение без классификации выходов. В эту группу входят: медианное голосование и взвешенное медианное голосование. Они выбирают среднее значение из всех выходов как «корректное».

В разделе рассматриваются четыре основных алгоритма мультиверсионного голосования:

• алгоритм голосования абсолютным большинством (ГАБ);

• алгоритм голосования согласованным большинством (ГСБ);

• алгоритм нечеткого голосования согласованным большинством (НГСБ);

• медианное голосование.

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

В работе предложено улучшение этих алгоритмов, основанное на статистике работы программных модулей. Основная идея заключается в том, чтобы каждый модуль при принятии решения, обладал неким весом (числом от 0 до 1). В качестве веса программного модуля используется вероятность возврата «корректного» результата этим модулем.

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

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

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

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

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

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

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

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

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

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

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

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

При реализации мультиверсионных моделей на практике, возникает вопрос: как много мультиверсий необходимо иметь, чтобы достичь желаемой надежности системы? Чтобы ответить на этот вопрос, необходимо найти соотношение между «корректностью» системы и количеством мультиверсий. Среди мультиверсионных методологий, существует только два фундаментальных подхода: модель восстанавливающихся блоков и мультиверсионное программирование. Найдем данные соотношения для этих двух моделей.

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

Пусть мы имеем n версий, их надежности равны r₁,r₂,…,r_n соответственно. Надежность проверочного модуля есть b. Определим соотношение между корректностью выхода системы (S_n) и количеством мультиверсий (n). В работе получено следующее выражение для S_n:

S_n=S_n-1+[r₁(1-b)+(1-r₁)b]∙ … ∙[r_n-1(1-b)+(1-r_n-1)b]∙r_nb.

В случае если все модули обладают некоторой средней надежностью ¯;r:

S_n=S_n-1+[¯;r(1-b)+(1-¯;r)b]^n-1∙¯;rb.

Или без рекурсивности:

S_n= ¯;rb ∙ (1-[¯;r(1-b)+(1-¯;r)b]ⁿ) / (1-[¯;r(1-b)+(1-¯;r)b]).

Рассмотрим некоторые особые случаи.

1. Надежность проверяющего модуля равна единице (b = 1), тогда

S_n = 1 - (1-¯;r)ⁿ.

Легко заметить, что S_n→1, если n→∞. В этом случае мы получаем систему, в которой можно не беспокоиться о надежности отдельных модулей, главное чтобы их количество было достаточно велико.

2. Средняя надежность программного модуля равна единице (¯;r = 1), тогда

S_n = 1 - (1-b)ⁿ.

Также как и в предыдущем случае, S_n→1 при n→∞. В этом случае, надежность проверочного модуля не имеет значения, главное, чтобы количество мультиверсий было достаточно велико.

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

Голосование абсолютным большинством получает «корректный» результат, если более половины мультиверсий возвращают «корректный» результат и алгоритм голосования выбирает один из них. Предположим, что все программные модули обладают некоторой средней надежностью ¯;r, надежность модуля принятия решения ‑ b, а корректность выхода системы ‑ S_n, где n – количество мультиверсий в системе.

Пусть m модулей вернуло «корректный» результат, а (n-m) – вернули ошибку, тогда вероятность такой ситуации можно записать как:

P_n(m)= CCombin∙¯;r^m∙(1-¯;r)^n-m.

Тогда S_n можно представить как сумму вероятностей того, что m= модулей вернули «корректный» результат и алгоритм голосования принял правильное решение:

S_n=.

Голосование согласованным, нечеткое голосование согласованным большинством, а также взвешенные варианты алгоритмов голосования, служат для того, чтобы приблизить S_n к 1 для того же m. Получить выражения в аналитическом виде для данных алгоритмов не представляется возможным, но оценить предел улучшений данных алгоритмов можно, положив, что m достаточно мало (менее 0,5 от n, как в случае с ГАБ).

На рисунках 3 и 4 приведены графические оценки моделей мультиверсионного программирования и восстанавливающихся блоков для характеристик систем. Стоит отметить, что для МВП, b отклоняется от 1 за счет ошибок в конкретной реализации модуля мультиверсионного голосования. Следовательно, для данной модели b можно бесконечно приблизить к 1 за счет качественной отладки, а основным критерием, влияющим на S_n, является m (косвенно зависящий от ¯;r). В тоже время, для МВБ b характеризует, в первую очередь, качество проверочного модуля, а уже потом наличие ошибок в программной реализации.

Рисунок 3. Оценка эффективности основных мультиверсионных моделей при n=5

Рисунок 4. Оценка эффективности основных мультиверсионных моделей при n=15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

X_i = Y + r ∙ ∆x.

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

f(S) = {S / M} ,

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

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

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 с некоторым пороговым значением E_g:

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

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

N_i / (P_i ∙ S) ≤ 1.

Т

, если [ g(P_i, S) > E_g ] и [ N_i / (P_i ∙ S) ≤ 1 ],

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

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

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

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

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

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

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

Генерация межверсионных ошибок будет осуществляться аналогично генерации одиночных ошибок, но вместо P_i будем использовать P_м, а вместо N_i – N_m:

;

.

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

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

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

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

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

Для работы оптимизационных алгоритмов в среде мультиверсионного исполнения необходимо доработать модуль согласования результатов. Этот модуль, опираясь на выходы мультиверсий, генерирует оптимальный выход всей системы. Используя процесс оптимизации, целесообразно не сравнивать результаты версий алгоритмов оптимизации между собой, а выбирать оптимальную точку среди всех выходов. В этом случае будем считать корректными все те результаты, которые находятся в определенной окрестности этого значения, а остальные - ошибочными. Иными словами, результат алгоритма j считается корректным, если , i,j[1,N], где N – количество мультиверсий. Назовем такой способ голосованием по значению оптимизируемой функции.

Тестирование будем производить на одномерной унимодальной функции мультиверсиями, которые реализуют:

• метод дихотомии;

• метод «золотого сечения»;

• метод квадратичной интерполяции.

А также на функции Розенброка программными реализациями алгоритмов:

• алгоритм Гаусса-Зейделя;

• алгоритм Нелдера-Мида;

• алгоритм Хука-Дживса;

• алгоритм Флетчера-Ривса.

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

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

В заключении сформулированы основные выводы и результаты, полученные в диссертационной работе.

Таблица 1 Результаты исследования эффективности мультиверсионного подхода к алгоритмам оптимизации функций

Класс функций	Алгоритм	Время, по отн. к лучшему по времени	Время, по отн. к лучшему по результату	Среднее отклонение от точки экстремума
Класс одномерных унимодальных функций	Мультиверсионная система	35,71	1,00	1,00
	Метод квадратичной интерполяции	24,86	0,70	0,97
	Метод «золотого сечения»	1,00	0,03	0,49
	Метод дихотомии	1,15	0,03	0,49
Функция Розенброка	Мультиверсионная система	1,93	1,00	0,96
	Метод Нелдера-Мида (версия 2)	1,02	0,53	1,05
	Метод Нелдера-Мида (версия 1)	1,00	0,52	22,74
	Метод Хука-Дживса (версия 1)	9,32	4,83	137,67
	Метод Гаусса-Зейделя	0,04	0,02	9801,82
	Метод Хука-Дживса (версия 2)	35,80	18,55	12461,90
	Метод Флетчера-Ривса (версия 1)	130,03	67,37	32156,17
	Метод Флетчера-Ривса (версия 2)	86,60	44,86	37708,33

20

Основные результаты и выводы:

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

• Разработан программный инструментарий, позволяющий унифицировать применение мультиверсионного подхода к различным программным комплексам, который в отличие от существующих в настоящее время, позволяет исполнять модули не только с помощью методологии мультиверсионного программирования, но также с использованием остальных распространенных мультиверсионных моделей: восстанавливающихся блоков, согласованных восстанавливающихся блоков, t/(n-1)-версионного программирования и мультиверсионного программирования с самопроверкой.

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

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

• Путем тестирования показано, что примение методологии мультиверсионного программирования позволяет повысить отказоустойчивость системы.

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

Список публикаций по теме диссертации

Публикации в изданиях, рекомендованных ВАК РФ:

1. Ковалев, И.В. К проблеме выбора алгоритма принятия решения в мультиверсионных системах [Текст] / И.В. Ковалев, А.В. Котенок // Информационные технологии. – 2006. – № 9. – С. 39‑44.

2. Котенок, А.В. К проблеме выбора мультиверсионной модели повышения надежности программного обеспечения [Текст] // Вестник Сиб. гос. аэрокосмич. ун-та. – 2008. – Вып. 4 (21). – С. 63‑67.

Прочие публикации по теме диссертационного исследования:

3. Котенок, А.В. Программная система «СМВИ v1.0» (среда мультиверсионного исполнения программных модулей) [Текст] // Компьютерные учебные программы и инновации. – 2005. – № 8. – С. 6–7.

4. Котенок, А.В. Построение среды мультиверсионного исполнения программных модулей [Текст] / А.В. Котенок // Вестник НИИ СУВПТ : сб. науч. тр. / Под общ. ред. Н.В. Василенко. – Красноярск : НИИ СУВПТ. – 2003. – Вып. 14. – С. 13–21.

5. Котенок, А.В. Реализация алгоритмов мультиверсионного голосования [Текст] / А.В. Котенок // Вестник университетского комплекса : сб. науч. тр. / Под общ. ред. Н.В. Василенко. – Красноярск : ВСФ РГУИТП : НИИ СУВПТ, 2004. – Вып. 3 (17). – С. 86‑93.

6. Котенок, А.В. Среда мультиверсионного исполнения программных модулей [Текст] / А.В. Котенок // Вестник университетского комплекса : сб. науч. тр. / Под общ. ред. Н.В. Василенко. – Красноярск : ВСФ РГУИТП : НИИ СУВПТ, 2006. – Вып. 6 (20). – С. 219‑238.

7. Котенок, А.В. Имитационная система для среды мультиверсионного исполнения программных модулей (программная система «ИС-СМВИ v1.0») [Текст] // Компьютерные учебные программы и инновации. – 2007. – № 2. – С. 9.

8. Котенок, А.В. Модель среды мультиверсионного исполнения программных модулей [Текст] // Современные наукоёмкие технологии. – 2006. – № 4. – С. 60–61.

9. Котенок, А.В. Реализация алгоритмов мультиверсионного голосования [Текст] // Современные наукоёмкие технологии. – 2007. – № 8. – С. 44–45.

10. Котенок, А.В. Применение методологии мультиверсионного программирования к оптимизации гладких функций нескольких переменных [Текст] // Фундаментальные исследования. – 2008. – № 1. – С. 129–130.

11. Kotenok, A.V. Using N-Version approach to methods of optimization of multivariable functions [Text] // European Journal of Natural History. – 2008. – № 2. – С. 86.

Разработки, зарегистрированные в Отраслевом фонде алгоритмов и программ:

12. Котенок, А.В. Программная система "СМВИ v1.0" (Среда мультиверсионного исполнения программных модулей). / А.В. Котенок // Номер гос. регистрации 50200401366 от 25.11.2004 г. – М. : ВНТИЦ, 2004.

13. Ковалев, И.В. Имитационная система для среды мультиверсионного исполнения программных модулей (программная система «ИС-СМВИ v1.0») / И.В. Ковалев, А.В. Котенок / Номер гос. регистрации 50200501597 от 24.11.2005 г. – М. : ВНТИЦ, 2005.

КОТЕНОК Андрей Владимирович