автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Мультиверсионная среда исполнения для отказоустойчивых программных комплексов систем управления

\о

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

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

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

05.13.01 - Системный анализ, управление и обработка информации (космические и информационные технологии) 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

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

12

.и

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

003464344

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

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

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

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

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

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

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

кандидат технических наук, доцент Царев Роман Юрьевич

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

сравнении выходов мультиверсий и размещении идентичных из них в одинаковые классы (подмножества). Однако, в случаях, когда расчеты выполняются не с целыми числами определение, идентичны выходы или нет, является затруднительным. Для разрешения этой проблемы введем понятие соотношение равенства: мы будем говорить, что два числа равны, если они отличаются меньше, чем на некоторое допустимое отклонение. Эти соотношения не требуют выполнения свойства транзитивности. Иными словами, если известно, что |а - Ь| < £ и |Ь - с| < е, то отсюда не следует что |а - с| < е, где а, Ь и с - некоторые числа. Потенциальной проблемой методик данной группы является возможная неверная классификация выходов, и как следствие, неверное принятие решения, что, в конечном счете, способно привести к отказу системы управления.

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

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

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

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

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

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

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

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

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

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

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

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

Множество корректных значений Множество выходов модуля N Одиночные ошибки Межверсионные ошибки

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

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

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

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

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

ошибки

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

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

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

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

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

Пусть мы имеем п версий, их надежности равны г1,г2,...,г„ соответственно. Надежность проверочного модуля есть Ъ. Определим соотношение между корректностью выхода системы (£„) и количеством мультиверсий (п). В работе получено следующее выражение для 5п^п.,+[Г1(1-Ь)+(1-Г1)Ь]- ... ■[гп.1(1-Ь)+(1-гп.1)Ь]т„Ь. В случае если все модули обладают некоторой средней надежностью г\

Зл=8п_,+[7(1-Ь)+0-ФГ' гЪ.

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

5„= гЬ ■ (1-1?(1-Ь)+(1-Т)Ь]")/(1-(7(1-Ь)+(1-7)Ь]).

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

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

5„ = 1 - (1-7)".

Легко заметить, что 5"„—»1, если п—»да. В этом случае мы получаем систему, в которой можно не беспокоиться о надежности отдельных модулей, главное чтобы их количество было достаточно велико.

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

5„ = 1 - (1-Ь)".

Также как и в предыдущем случае, 5„—> 1 при п—><ю. В этом случае, надежность проверочного модуля не имеет значения, главное, чтобы количество мультиверсий было достаточно велико.

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

Голосование абсолютным большинством получает «корректный» результат, если более половины мультиверсий возвращают «корректный» результат и алгоритм голосования выбирает один из них. Предположим, что все программные модули обладают некоторой средней надежностью г, надежность модуля принятия решения - Ъ, а корректность выхода системы - 5„, где и - количество мультиверсий в системе.

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

Ря(т)= Стп7п-(1-7Гт.

Тогда 5„ можно представить как сумму вероятностей того, что

- + 1 2

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

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

На рисунках 3 и 4 приведены графические оценки моделей мультиверсионного программирования и восстанавливающихся блоков для

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

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

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

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

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

Надежностные характеристики программных модулей

Программные модули (генераторы ошибок)

Модуль ввода

ТТТ

Д-Х-Х.

Надежностные характеристики блока принятия решений

СМВИ

Блок принятия решений

Модуль вывода

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

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

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

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

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

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

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

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

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

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

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

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

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

Qi - вероятность безотказной работы программного модуля г

Ы) - количество сгенерированных /-м программным модулем ошибок;

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

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

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

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

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

Х) - значение, возвращаемое г'-м программным модулем;

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

Ах - максимально допустимое отклонение X, от У, при котором X, все еще можно считать корректным.

Будем считать, что /'-й программный модуль завершил выполнение с ошибкой, если возвращаемая им величина Х1 отклоняется от образца У более, чем на некоторый порог Ах (рисунок 6). Причем Ах должен быть отличным от нуля, т.к. некоторые алгоритмы принятия решений используют в процессе выполнения степень равенства результатов.

(в, = 1-Р,)\

У+Дх

У-Дх

г

-1

+1

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

Формально это можно записать следующим образом: X, = У + г • Ах

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

ДБ) = {Б/М}, где {} - операция получения дробной части числа.

Учитывая, что М=1 / Р„ получаем:

ДР1,Б) = {Б-Р1}.

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

8(РЬ Б) =/(Р„ Б) + I ■ е = {Б ■ Р,} + I ■ е, где / - некоторый коэффициент, определяющий уровень влияния случайности на выход программного модуля.

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

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

> Е^ —► ошибка

Однако, ввиду влияния случайной величины 1-е, необходимо следить, чтобы количество сгенерированных ошибок ТУ, не превышало количество ошибок, ожидаемых к текущему этапу обработки данных Р, -Б\

М</(РГБ)<1.

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

Г(4 + , иу С,, если [ 8(Р„ Б) > К,А ] и [ Л', / (Р,-Б) < I ], г (5)=^

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

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

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

• в окрестности Ах от любого «ошибочного» значения одной

мультиверсии нет «ошибок» других мультиверсий.

Экспериментально было установлено, что для Eg оптимальным

значением является 0,85, а для I - 0,5. Характер XI при этих значения представлен на рисунке 7. На данном рисунке по оси абсцисс откладываются

итерации /-то модуля, а по оси ординат - отклонение выходного значение от «корректного». Отклонение от У более чем на Ах считается ошибкой.

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

Генерация межверсионных ошибок будет осуществляться аналогично генерации одиночных ошибок, но вместо Р, будем использовать Рм, а вместо N,-N„1

Гг + Н-д ,если[^(Рл(,5)>£'г]и[^и/(Ри-8)<и

г (5)=^

\ ¡ъ-д 5в противном случае.

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

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

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

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

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

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

Для работы оптимизационных алгоритмов в среде мультиверсионного исполнения необходимо доработать модуль согласования результатов. Этот модуль, опираясь на выходы мультиверсий, генерирует оптимальный выход всей системы. Используя процесс оптимизации, целесообразно не сравнивать результаты версий алгоритмов оптимизации между собой, а выбирать оптимальную точку среди всех выходов. В этом случае будем считать корректными все те результаты, которые находятся в определенной окрестности этого значения, а остальные - ошибочными. Иными словами, результат алгоритма j считается корректным, если /(X') < пуп /(X' ) + е/,

/¡/£[1^, где N - количество мультиверсий. Назовем такой способ голосованием по значению оптимизируемой функции.

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

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

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

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

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

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

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

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

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

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

Тестирование было произведено на различных тестовых функциях и множестве начальных точек. . Наиболее характерные результаты представлены в таблице 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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ:

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

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

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

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

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

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

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

программных модулей.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

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

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

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

9. Котенок, A.B. Реализация алгоритмов мультиверсионного голосования [Текст] // Современные наукоёмкие технологии. - 2007. - № 8, - С. 4445.

10. Котенок, A.B. Применение методологии мультиверсионного программирования к оптимизации гладких функций нескольких переменных [Текст] // Фундаментальные исследования. - 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.-C. 86.

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

программ:

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

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

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

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

Автореферат

Подписано в печать 29.12.2008. Формат 60x84/16. Бумага писчая. Гарнитура Times New Roman. Усл. печ. л. 1,39. Уч.-изд. л. 0,85. Тираж 100 экз. Заказ №_

Отпечатано в отделе копировально-множительной техники СибГАУ 660014, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31.

Введение.

1. Отказоустойчивые системы управления.

1.1. Программная составляющая критичных по надежности систем управления.

1.1.1. Надежностная характеристика программного модуля.

1.1.2. Обеспечение надежности программ с помощью введения избыточности.

1.2. Описание объекта исследования и его анализ.

1.3. Методы повышения надежности программных систем.

1.3.1. Моноверсионные модели.

1.3.2. Модели восстанавливающихся блоков.

1.3.3. Мультиверсионное программирование.

1.3.4. Мультиверсионное программирование с самопроверкой.

1.3.5. Модель согласованных восстанавливающихся блоков.

1.3.6. t/(n-l)-BepcH0HH0e программирование.

2. Мультиверсионная среда исполнения оптимизационных алгоритмов: программная реализация.

2.1. Анализ требований к среде мультиверсионного исполнения.

2.2. Применение мультиверсионной методологии к системе управления

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

2.3.1. Конструирование программной модели.

2.4. Реализация общих алгоритмов функционирования среды исполнения

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

2.6. Реализация алгоритмов принятия решения о корректности или ошибочности состояний мультиверсий.

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

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

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

2.6.4. Медианное голосование.

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

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

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

3.2.1. Выводы.

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

3.4. Методология выбора наилучшего алгоритма оптимизации.

3.4.1. Классы тестовых функций.

3.5. Анализ результатов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.1. Выводы

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

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

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

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

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

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

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

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

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

Для работы оптимизационных алгоритмов в среде мультиверсионного исполнения необходимо доработать модуль согласования результатов. Этот модуль, опираясь на выходы мультиверсий, генерирует оптимальный выход всей системы. Используя процесс оптимизации, целесообразно не сравнивать результаты версий алгоритмов оптимизации между собой, а выбирать оптимальную точку среди всех выходов. В этом случае будем считать корректными все те результаты, которые находятся в определенной окрестности этого значения, а остальные - ошибочными. Иными словами, результат алгоритма j считается корректным, если /(X') < min /(X* ) + sf, ye[l^V], где N — количество мультиверсий. Назовем такой способ голосованием по значению оптимизируемой функции.

3.4.Методология выбора наилучшего алгоритма оптимизации

Конкретную детерминированную задачу оптимизации можно решить различными алгоритмами. Отсюда возникают вопросы:

• какой алгоритм выбрать?

• какой алгоритм является «наилучшим»?

Ответ на эти вопросы возможен только в том случае, когда определен класс функций {Ф(Х)}, которому принадлежит критерий оптимальности Ф(Х). Без определения этого класса ответить на поставленные вопросы невозможно — нет алгоритма, наилучшего для всех возможных функций Ф(Х).

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

Для формальной постановки задачи определения наилучшего алгоритма из множества {А} на классе функций (Ф(Х)} необходимо еще ввести критерий качества алгоритма оптимизации. Обозначим этот критерий W^,A), где Фе{Ф(Х)}, Ае{А}. Положим, что оптимальным является наименьшее значение этого критерия.

Для построения критерия качества алгоритма на всем классе функций (Ф(Х)} можно воспользоваться

• принципом гарантированного результата: W(A) = ^ max IV(Ф, А);

• некоторым средним значением критерия качества алгоритма на классе функций (Ф(Х)}.

Если критерий качества алгоритма на классе функций (Ф(Х)} тем или иным образом определен, то задача отыскания наилучшего алгоритма оптимизации на этом классе функций формально может быть записана в следующем виде: W(A') = maxW(A).

Лф!)

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

В качестве критерия качества алгоритма оптимизации W(0,A) обычно рассматривают затраты времени на поиск. Эти затраты складываются I

• из затрат на испытания

• из затрат на нахождение точек Хг по информации о предыдущих испытаниях (можно сказать — из затрат на вычисления значений функции).

Обычно, на практике, последние затраты много меньше первых, поэтому в качестве критерия качества алгоритма оптимизации А можно использовать количество испытаний N(0,A,e,X°), необходимых для нахождения минимума функции Ф(Х) с заданной точностью 8 при начальном приближении Х°.

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

Поэтому будем в качестве критерия качества алгоритма оптимизации А на классе функций (Ф(Х)} использовать критерий Ы(Ф,А,Х°).

При заданной точности решения эффективность любого алгоритма поисковой оптимизации зависит от начального приближения Х°. Поэтому при экспериментальном тестировании обычно критерий Ы(Ф,Л,Х°) усредняют по множеству допустимых значений вектора варьируемых параметров D. Обозначим такой критерий N(d>,A).

Точность решения задачи оптимизации определяется используемым условием окончания поиска. При экспериментальном тестировании в качестве такого условия будем использовать одно из двух условий: ех, где Ф - значение функции mm re[0,JV]

Ф(ХГ)-Ф

Ф((ХГ) )-Ф ф ИЛИ

ХГУ-Х

Ф(Х) в точке истинного минимума, а Х- точка истинного минимума функции Ф(Х), ||*|| - некоторая векторная норма.

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

Сделаем следующие предположения:

• множество тестируемых алгоритмов {А} состоит из Па алгоритмов А,-, /g[1,#iJ;

• при тестировании алгоритма А,-, / е [1,ял] используется совокупность пф тестовых функций Ф, ^(Х) е {Ф(Х)}, j е [1,иф];

• при тестировании алгоритма А,-, /е[1,лл] с помощью функции Ф,ДХ)е{Ф(Х)},/е[1,яф] используется ^начальных приближений вектора варьируемых параметров X°jJc е Z), к е[1,гсЛ,].

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

Рисунок 3.12 Общая схема экспериментального тестирования алгоритмов поисковой оптимизации

3.4.1. Классы тестовых функций

Класс одномерных унимодальных функций.

Покроем интервал [а,Ь] сеткой из М узлов и обозначим Ф(х,)=Ф/, /е[1,М].

Положим, что необходимо построить одномерную унимодальную функцию, минимум которой находится в узле /* е[1,М], т.е. в точкех*.'Тогда для генерации такой функций может быть использован следующий алгоритм построения тестовых одномерных унимодальных функций.

1. Генерируем дискретную случайную величину i, равномерно распределенную на множестве 1,2,.,М

2. Генерируем случайные числа Фг по рекуррентной формуле: ГФ,=ФМ+Д

1 Фо = & ' где рг-, /е[0,М] - случайные величины, равномерно распределенные в * интервале (-а,0), если i<i, и в интервале (а,0), если i>i. Здесь а - некоторая константа, определяющая максимальную скорость изменения искомой функции.

3. Для получения функции Ф(х) используем линейную интерполяцию полученных значений Ф„ i е [1,М]. Минимум полученной функции Ф(х) достигается в точке х*—х*.

Функцию данного класса можно описать следующим образом: Ф, + к{ (jcj - х), х < х,

ЭС Д> iXi ф,—--+ ф2-— ,Xj <Х<Х2

Ф(Х) =

Х^ Xj

X \i X j- X Хх ф —ZМ.— + ф — M~l х <х<х

ХМ ХМ-1 ХМ ХМ-1

Фм + к2 (х где ki и к2 - некоторые случайные величины.

Класс многоэкстремальных функций нескольких переменных.

Алгоритм генерации многоэкстремальных функций нескольких переменных можно построить на основе использования совокупности М квадратичных функций, каждая из которых дает локальный минимум м искомой функции: Ф(Х) = ^]ФДХ), где j е[\,М] квадратичная функция j=1

Здесь п — размерность X, X*. =(x*i j,x*2 j,.,x*n j) — точка у'-го локального минимума глубиной Cj, постоянные akj, x'kJ, su, Cj - случайные величины с некоторыми законами распределения.

3.5.Анализ результатов

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

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

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

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

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

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

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

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

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

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

103

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

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

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

Результаты представлены в таблице 3.1.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. Котенок, А.В. Программная система "СМВИ vl.O" (среда мультиверсионного исполнения программных модулей) // Компьютерные учебные программы и инновации.- № 8, 2005.

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

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

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

5. Ковалев, И.В. К проблеме выбора алгоритма принятия решения в мультиверсионных системах / И.В. Ковалев, А.В. Котенок // Информационные технологии; №9, 2006. с. 39-44.

6. Ковалев, И.В. Имитационная система для среды мультиверсионного исполнения программных модулей (программная система «ИС-СМВИ vl.O») // Компьютерные учебные программы и инновации.- № 2, 2007.

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

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

9. Гантер, Р. Методы управления проектированием программного обеспечения: Пер. с англ./ Р. Гантер, Е. К. Масловский. М.: Мир, 1981. -392 с.

10. Липаев, В. В. Качество программного обеспечения. / В. В. Липаев. М.: Финансы и статистика, 1983. - 263 с.

11. Мамиконов, А. Г. Проектирование АСУ. / А. Г. Мамиконов. М.: Высшая школа, 1987. - 304 с.

12. Липаев, В. В. Проектирование программных средств: Учеб. пособие для вузов по спец. "Автом. сист. обр. информ. и упр.". / В. В. Липаев. М.: Высшая школа, 1990. - 303 с.

13. Майерс, Г. Надежность программного обеспечения: Пер. с англ. Галимова Ю. Ю. / Г. Майерс, В. Ш. Кауфман. М.: Мир, 1980. - 360 с.

14. Avizienis, A. On the implementation of N-version programming for software fault-tolerance during execution. / A. Avizienis, L. Chen. In Proc. IEEE COMPSAC 77, c. 149-155, ноябрь 1977.

15. Elmendorf, W. Fault-tolerant programming. / W. R. Elmendorf. // In Digest of 2-nd FTCS, c. 79-83, Newton, MA, June 1972.

16. Avizienis, A. Fault tolerance and fault intolerance: complementary approaches to reliable computing. / A. Avizienis. In Proc. 1975 International Conference on Reliable Software, c. 458-464, апрель 1975.

17. Avizienis, A. The methodology of N-version programming. In Software fault-tolerance / A. Avizienis, M. R. Lyu, c. 23-47, Wiley, 1995.

18. Avizienis, A. DEDIX 87 A supervisory system for design diversity experiments at UCLA. / A. Avizienis, M. R. Lyu, W. Schuetz, U. Voges. // In Digest of 18th FTCS, c. 129-168, Токио, Япония, июнь 1988.

19. Chen, J. Software Diversity and Its Implications in the N-version Software Life Cycle. / J. J. Chen. PhD dissertation, UCLA, Computer Science Department, 1990.

20. Pressman, R. Software Engineering: A Practitioner's Approach. // 4th Edition. Mc Graw-Hill, 1997.

21. Software Considerations in Airborne Systems and Equipment Certification. RTCA/DO-178B, RTCA, Inc, 1992.

22. Lyu, M.R. Improving the N-Version Programming Process Through the Evolution of a Design Paradigm / M.R. Lyu, Y. He, IEEE COMSPAC, 1993

23. Lyu, M. Software diversity metrics and measurements. / M. R. Lyu, J. H. Chen, A. Avizienis. In Proc. IEEE COMPSAC 1992, c. 69-78, Chicago, Illinois, сентябрь 1992.

24. Randell, B. The Evolution of the Recovery Block Concept / J. Xu, B. Randell University of Newcastle upon Tyne, England, 1995.

25. Anderson, T. Fault Tolerance: Principles and Practice / T. Anderson, P. A. Lea Practice Hall, 1981

26. Randell, B. System structure for software fault tolerance // IEEE Trans Software Engineering, том SE-1, c. 220-231, 1975

27. Peter J. Denning, Fault Tolerant Operating Systems // ACM Computing Surveys, Vol. 8, No. 4, December 1976, pp. 359 389.

28. Fetzer, C. Automatic Detection and Masking of Non-Atomic Exception Handling / C. Fetzer and K. Hogstedt (USA), P. Felber (France). 2003

29. Kim, K. Fault-Tolerant Software Voters Based on Fuzzy Equivalence Relations / K.Kim, M.A. Vouk and D.F. McAllister Department of Computer Science, North Carolina State University, 1997

30. Leung, Y.W. Maximum Likelihood Voting for Fault Tolerant Software with Finite Output Space / IEEE Trans. Rel, Vol. 44(3) c. 419-427, 1995

31. Mitchell, G. An approach for network communications systems Recovery / G.G. Mitchell, S. Brown Department of Computer Science, National University of Ireland, 2000

32. Romanovsky, A. Diversely Designed Classes for Use by Multiple Tasks. -University of Newcastle upon Tyne, 2000

33. Xu, J. The t/(n-l)-VP Approach to Fault-Tolerant Software / J. Xu, B. Randell — University of Newcastle upon Tyne, 1998

34. Steen, M. A Scalable Location Service for Distributed Objects / M. van Steen, F J. Hauck, A.S. Tanenbaum Vrije Universiteit, Amsterdam, 1996

35. Daniels, F. The Reliable Hybrid Pattern: A Generalized Software Fault Tolerant Design Pattern — Department of Electrical & Computer Engineering, North Carolina State University, 1999

36. Xu, J. Implementing Software-Fault Tolerance in С++ and Open С++: An Object-Oriented and Reflective Approach / J. Xu, B. Randell, A.F. Zorzo -Department of Computing Science, University of Newcastle upon Tyne, 2000

37. Bondavalli, A. Adaptable Fault Tolerance For Real-Time Systems / A. Bondavalli, J. Stankovic, L. Strigini CNUCE-CNR, Pisa, Italy, 1995

38. Brunie, L. Optimizing complex decision support queries for parallel execution / L. Brunie, H. Kosh LIP-CNRS at Ecole Normale Superieure de Lyon, France, 1997

39. Anderson Т., Fault Tolerance: Principles and Practice / T. Anderson and P.A. Lee//Prentice Hall, 1981.

40. Knight, J.C. An Experimental Evaluation of the Assumption of Independence in Multiversion Programming / J.C. Knight, N.G. Leveson // IEEE Transactions on Software Engineering, том SE-12, №1, c. 96-109, январь 1986

41. Avizienis, A. In Search of Effective Diversity: A Six-Language Study of Fault-Tolerant Flight Control Software / A. Avizienis, M.R. Lyu, W. Schutz //

42. Proceedings 18th Annual International Symposium on Fault Tolerant Computing Токио, Япония, 27-30 июня 1988.

43. Pradhan, D. К. Fault-Tolerant Computer System Design. / D. K. Pradhan -Prentice-Hall, Inc., 1996.

44. Laprie, J.C. Architectural Issues in Software Fault Tolerance, in Software Fault Tolerance, Michael R. Lyu, editor, Wiley, 1995, pp. 47 80.

45. Hecht, H. Fault-Tolerance in Software, in Fault-Tolerant Computer System Design. / H. Hecht, M. Hecht Dhiraj K. Pradhan, Prentice Hall, 1996.

46. Lorczack, P. R. A Theoretical Investigation of Generalized Voters for Redundant Systems. / P. R. Lorczack Digest of Papers FTCS-19: The Nineteenth International Symposium on Fault-Tolerant Computing, 1989. — pp. 444-451.

47. Taylor, J. Redundancy in Data Structures: Improving Software Fault Tolerance, IEEE Transactions on Software Engineering, Vol. SE-6, No. 6, November 1980, pp. 585 594.

48. Taylor, J. Redundancy in Data Structures: Some Theoretical Results, IEEE Transactions on Software Engineering, Vol. SE-6, No. 6, November 1980, pp. 595 602.

49. Broen, R. B. New Voters for Redundant Systems, Transactions of the ASME. / R. B. Broen Journal of Dynamic Systems, Measurement, and Control, March 1975.-pp. 41-45.

50. Abbott, J. Resourceful Systems for Fault Tolerance, Reliability, and Safety / Russell J. Abbott ACM Computing Surveys, Vol. 22, No. 1, March 1990, pp. 35 - 68.

51. Gersting, J. A Comparison of Voting Algorithms for N-Version Programming. / J. Gersting Proceedings of the 24th Annual Hawaii International Conference on System Sciences, Volume II, January 1991. - pp. 253-262.

52. Croll, P. R. Dependable, Intelligent Voting for Real-Time Control Software. / P. R. Croll — Engineering Applications of Artificial Intelligence, vol. 8, no. 6, December 1995. pp. 615-623.

53. Bass, J. M. Voting in Real-Time Distributed Computer Control Systems. / J. M. Bass-PhD Thesis, University of Sheffield, October 1995.

54. Kelly, J. P. J. Multi-Version Software Development. / J. P. J. Kelly -Proceeding of the Fifth IF AC Workshop, Safety of Computer Control Systems, October 1986. pp. 43-49.

55. Tso, K. S. Community Error Recovery in N-Version Software: A Design Study with Experimentation. / K. S. Tso, A. Avizienis Digest of Papers FTCS-17: The Seven teenth International Symposium on Fault-Tolerant Computing, July 6-8, 1987. - pp. 127-133.

56. Saglietti, F. The Impact of Voter Granularity in Fault-Tolerant Software on System Reliability and Availability. / F. Saglietti, M. Kersken, Software Fault Tolerance: Achievement and Assessment Strategies, Springer-Verlag, 1991.

57. Ковалев, И.В. Автоматизация создания программных средств систем управления. / В кн.: Микроэлектронные устройства: проектирование и технология. Красноярск. КПИ, 1990. - С. 79-85.

58. Ковалев И.В. Многоатрибутивная модель формированиягарантоспособного набора проектов мультиверсионных программных112систем. / И.В. Ковалев, Р.Ю. Царев; Вестник НИИ СУВПТ. Вып.7. -Красноярск: НИИ СУВПТ, 2001. - С. 129-137.

59. Ковалев, И.В. Оптимальное проектирование мультиверсионных систем управления. / И.В. Ковалев, А.А. Попов, А.С. Привалов. Доклады НТК с международным участием «Информационные технологии в инновационных проектах». - Ижевск: ИжГТУ, 2000. - С. 24-29.

60. Ковалев, И.В. Параллельные процессы в информационно-управляющих системах. Формирование и оптимизация: Монография. / И.В. Ковалев, Р.Ю. Царев, Ю.Г. Шиповалов. Под ред. д.т.н., проф. А.В. Медведева. -Красноярск: НИИ СУВПТ, 2001. - 143 с

61. Ковалев, И.В. Система мультиверсионного формирования программного обеспечения управления космическими аппаратами: Диссертация на соискание ученой степени доктора технических наук. / Красноярск: КГТУ, 1997.-228 с.

62. Ковалев, И.В. Надежность архитектуры программного обеспечения телекоммуникационных технологий. / И.В. Ковалев, Н.В. Василенко, Р.В.Юнусов; Международная научная конференция Telematica'2001, Санкт-Петербург, 2001- С. 23-24

63. Kovalev, I. Y. An Approach for the Reliability Optimization of N-Version Software under Resource and Cost/Timing Constraints. / 16th International Computer Measurement Group Conference, Nashville, TN, USA, December 9-13, 1991.

64. Kovalev, I. V. Computer-Aided Modelling of Production Cycles Optimal Sequence in: Letunovsky V.V.(Editor-in-chief): Problems of products quality assurance in machine-building: Proceedings of Int. Conf. KSTU / Krasnoyarsk, 1994. pp. 43-48.

65. Kovalev, I.V. Fault-tolerant software architecture creation model based on reliability evaluation / I.V. Kovalev, R.V.Younoussov; Advanced in Modeling & Analysis, vol. 48, № 3-4. Journal of AMSE Periodicals, 2002, pp. 31-43.

66. Юдин, Д.Б. Математические методы оптимизации устройств и алгоритмов АСУ / Д.Б. Юдин, А.П. Горяшко, А.С. Немировский -Москва, «Радио и связь», 1982. 288 с.

67. Антамошкин, А.Н. Оптимизация функционалов с булевыми переменными. Монография. Под ред. д.т.н. JI.A. Растригина. - Томск:

68. Издательство томского университета, 1987. 104 с.114

69. Антамошкин, А.Н. Оптимизация процессов автоматизированного синтеза систем управления космическими аппаратами. — Дисс. на соиск. уч. ст. доктора техн. наук — Красноярск: Сибирская аэрокосмическая академия, 1996, 285 с.

70. Antamoshkin, A. System Analysis, Design and Optimization / A. Antamoshkin, H.P. Schwefel, and others. Ofset Press, Krasnoyarsk, 1993. -312 p.

71. Семенкин, E.C. Поисковые методы синтеза управления космическими аппаратами. Монография / Е.С. Семенкин, О.Э. Семенкина, С.П. Коробейников Под ред. д.т.н. Е.С. Семенкина. - Красноярск: СИБУП, 1996.-325 с.

72. Березовский, Б.А. Многокритериальная оптимизация: математические аспекты. — Москва: Наука, 1989. — 128 с.

73. Вентцель, Е.С. Теория случайных процессов и ее инженерные приложения. / Е.С. Вентцель, JI.A. Овчаров. М.-.Наука, Гл.ред.физ.-мат.лит. - 1991. - 3 84 с.

74. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. // Под ред. P. JI. Добрушина и С. И. Самойленко. М.: Мир, 1976. - 594 с.

75. Семенкин, Е.С. Адаптивные поисковые методы оптимизации сложных сложных систем. Монография / Е.С. Семенкин, О.Э. Семенкина, С.П. Коробейников. Под ред. д.т.н. Е.С. Семенкина. - Красноярск: СИБУП, 1996.-358 с.

76. Аоки, М. Ведение в методы оптимизации. — М.: Наука, 1977. — 344 с.

77. Габасов, Р.Ф. Методы оптимизации. / Р.Ф. Габасов, Ф.М. Кириллова -Минск: Изд. бел. гос. ун., 1981. 350 с.

78. Моисеев, Н.Н. Методы оптимизации. / Н.Н. Моисеев, Ю.П. Иванилов, Е.М. Столярова М.: Наука. 1978.-352 с.

79. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

80. Дегтярев, Ю. И. Методы оптимизации: Учеб. пособие для вузов. — М.: Сов. радио, 1980. — 272 с.

81. Лебедев, В.А. Параллельные процессы обработки информации в управляющих системах: Монография. / В.А. Лебедев, Н.Н. Трохов, Р.Ю. Царев. Красноярск: НИИ СУВПТ, 2001. - 137 с.

82. Попов, А.А. Бинарная модель отказоустойчивой системы программного обеспечения: Доклады НТК с международным участием «Информационные технологии в инновационных проектах». / А.А. Попов, А.С. Привалов. Ижевск: ИжГТУ, 2000. - С. 77-83

83. Царев, Р.Ю. Многокритериальное принятие решений при создании отказоустойчивого программного обеспечения. / Вестник НИИ СУВПТ. Вып.2. - Красноярск: НИИ СУВПТ, 1999. - С. 190-194.

84. Юнусов, Р.В. Анализ надежности аппаратно-программного информационно-управляющего комплекса. / Вестник НИИ СУВПТ: Сб. научн. Трудов. / Под общей ред. профессора Н.В. Василенко; Красноярск: НИИ СУВПТ. 2003. Выпуск 11. С. 103-106.

85. Юнусов, Р.В. Оценка надежности и гарантоспособная модель архитектуры программного обеспечения. / Вестник НИИСУВПТ; Красноярск: НИИСУВПТ.2001. -Вып.8. С. 194-208.

86. Юнусов, Р.В. Моделирование программных архитектур автоматизированных систем управления. / Управляющие и вычислительные системы. Новые технологии: Материалы всероссийской электронной научно-технической конференции. Вологда: ВоГТУ, 2001. С. 60-61.

87. Фокс, Д. Программное обеспечение и его разработка: Пер. с англ. / Д. Фокс М.: Мир, 1985. - 268 с.

88. Козленко JI. Проектирование информационных систем. / JI. Козленко — М.: КомпьютерПресс, № 9-11, 2001.

89. Орлов С.А. Технологии разработки программного обеспечения. / С.А. Орлов СПб.: Питер, 2002.

90. Гантер, Р. Методы управления проектированием программного обеспечения: Пер. с англ. / Р. Гантер, Е. К. Масловский. — М.: Мир, 1981. -392 с.

91. Майерс, Г. Надежность программного обеспечения: Пер. с англ. / Г.

92. Майерс, В. Ш. Кауфман. М.: Мир, 1980. - 360 с.117

93. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++. / Г. Буч. М.: БИНОМ, 1998. - 560 с.

94. Поздняков, Д.А. Разработка и исследование среды мультиверсионного исполнения программных модулей. / Д.А. Поздняков, И.С. Титовский, Р.В.Юнусов; Вестник НИИ СУВПТ: Сб. научн. трудов; Красноярск: НИИ СУВПТ.- 2003. Выпуск 13.- с. 155-170

95. Gray, J. Why Do Computers Stop and What Can Be Done About It / Proceedings of the Fifth Symposium On Reliability in Distributed Software and Database Systems, January 13-15, 1986, pp. 3-12.

96. Randell, B. Predictably Dependable Computing Systems / Springer, 1995.

97. Pradhan, K. Fault-Tolerant Computer System Design / Prentice-Hall, Inc., 1996

98. Xu, J. Software Fault Tolerance: t/(n-l)-Variant Programming / Jie Xu and Brian Randell // IEEE Transactions on Reliability, Vol. 46, No. 1, March 1997, pp. 60 68.

99. Rosenberg, L. Software Metrics and Reliability / L. Rosenberg, T. Hammer, J. Shaw; Software reliability engineering was presented at the 9-th International Symposium, "Best Paper" Award, November, 1998

100. Shooman, M.L. Software Reliability for Use During Proposal and Early Design Stages / FastAbstract ISSRE Copyright 1999

101. Scott, R. Fault-Tolerant Software Reliability Modeling / R. Keith Scott, James W. Gault, and David F. McAllister // IEEE Transactions on Software Engineering, Vol. SE-13, No. 5, May 1987, pp. 582 592.

102. Silayeva, Т. K.-E. An Innovative Method for Program Reliability Evaluation / T. Silayeva, K.-E. Grosspietsch. Euromicro '95. Como (Italy), September 1995

103. Ammann, P.E. Data Diversity: An Approach to Software Fault Tolerance / P.E. Ammann, J.C. Knight // IEEE Transactions on Computers, Vol. 37, No. 4, April 1988, pp. 418 425.

104. Tai, A. Performability Enhancement of Fault-Tolerant Software / A. Tai, J. Meyer, A. Avizienis. IEEE Trans, on Reliability, 1993. - Vol. 42, No. 2 . -P. 227-237

105. Wattanapongsakorn, N. Reliability Optimization for Software Systems with Multiple Applications./ FastAbstract ISSRE and Chillarege Corp. Copyright 2001

106. Whitehouse, G. E. Applied operations research: a survey, Wiley, Inc. / G. E. Whitehouse, B. L. Wechsler. New York, 1976. - 424 c.

107. Xie, M. Regression Goodness-Of-fit Test for Software Reliability Model Validation / M. Xie, B.Yang; FastAbstract ISSRE Copyright 2000

108. Zahedi, F. Software reliability allocation based on structure, utility, price, and cost / F. Zahedi, N. Ashrafi. IEEE Trans, on Software Engineering, April 1991. - Vol. 17, No. 4. - c. 345-356