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

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

 

 

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

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

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

 

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

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

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

 

 

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

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

 

 

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

д.т.н., профессор Ковалев И.В.

 

 

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

СОДЕРЖАНИЕ

Введение. 3

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

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

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

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

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

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

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

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

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

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

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

1.3.6. t/(n-1)-версионное программирование. 49

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.1. Выводы.. 91

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

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

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

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

Заключение. 104

Список использованных источников. 105

 

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Секционирование – техника обеспечения изоляции функционально незавизимых модулей [21]. Секционирование может быть вертикальным и горизонтальным в срезе модульной иерархии программной архитектуры. Горизонтальное секционирование выделяет основные программные функции в независимые структурные ветви, соединяемые через специальные интерфейсы управления модулями. Вертикальное секционирование нацелено на распределение функций управления и обработки по уровням архитектуры: модули верхнего уровеня отвечают за функции упраления, а модули нижнего уровня – осуществляют основную обработку данных. Преимущества применения секционирования заключаются в упрощении отладки и тестирования, упрощение обслуживания и слабое распространение сторонних эффектов [21].

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

Обнаружение ошибок

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

Существует несколько видов проверок для обнаружения ошибок [39]:

· Проверка репликации представляет собой механизм обнаружения ошибок путем сравнения выходов модулей;

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

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

· Проверки кода используют избыточность для представления информации с четкой связью между рабочими и избыточными данными. Обнаружение ошибок проверяет эту связь до и после операций. Примером таких проверок является контрольная сумма (также коды Хэмминга, циклические коды и т.д.) [80]. Данный вид проверок особенно эффективен, когда данные перекомпоновываются либо передаются из одной точки в другую без изменений. Многие арифметические операции также обладают свойствами между рабочими и избыточными данными, и поэтому могут быть проверены на ошибки своего выполнения.

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

· Структурная проверка использует известные свойства структуры данных. Например, в списках, очередях и деревьях можно проверить правильность ссылок на элементы. Структурные проверки можно сделать более эффективными расширив структуру данных дополнительной (избыточной) информацией. Например, для деревьев можно хранить счетчик с количеством дочерних элементов, для списков – с общим количеством элементов, а также индивидуальные идентификаторы для всех элементов [47] [48].

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

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

Дублирование процессов

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

Разнообразие данных

В некоторых случаях, применим метод разнообразия данных, который позволяет автоматически «обходить» отказы, связанные с определенными последовательностями входных данных. Смысл данного подхода заключается в том, часто на практике отказы проявляются на определенном наборе входных данных, в ситуациях, не смоделированных в процессе тестирования и отладки. Разнообразие данных часто используется совместно с методом контрольной точки и перезапуска с модернизацией входных данных при каждом повторе [116]. Цель каждого повтора заключается в генерации такого выхода, который являлся бы идентичным или логически эквивалентным. В общем случае, эквивалентность выходов является зависимой от конкретной задачи. Существует три основных модели разнообразия данных:

· Модернизация входных данных (рисунки 1.4 и 1.5)

Рисунок 1.4. Точно восстановления и перезапуск с использованием метода разнообразия данных (модернизация входных данных)

Рисунок 1.5. Разнообразие данных с использованием модернизации входных данных

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

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

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

Рисунок 1.7. Разнообразие данных с использованием декомпозиции входных данных

Требования для обеспечения простоты

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

 

Требования для обеспечения производительности

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

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

 

Требования для обеспечения компактности

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

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

 

Требования для обеспечения надежности

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

§ отсутствие каких-либо ошибок в программном коде самой среды;

§ устойчивость СМВИ к ошибкам и отказам модулей;

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

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

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

 

Требования для обеспечения универсальности

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

 

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

 

 

 

Таблица 2.1 Требования к разрабатываемому программному комплексу

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

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

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

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

Для реализации данного метода используется булева матрица согласования R. Элементы этой матрицы определяются следующим образом:

Иными словами, если выход версии i «согласен» с выходом версии j и дополнительно включает некоторую область ε, то r_ij = 1, иначе r_ij =0.

Для принятия решения, используя алгоритм голосования абсолютным большинством, необходимо в матрице R найти такую строку i, сумма элементов которой будет больше или равна пороговому значению m. Тогда все мультиверсии j, которым соответствуют r_ij равныеединице, являются корректными, а остальные ошибочными. В случае, когда такой строки не существует, происходит ошибку – решение принять невозможно.

 

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

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

Для реализации, как и в методе ГАБ, составляется матрица согласования R. Выбор нужного множества корректных выходов осуществляется в два этапа:

1. выбираются и запоминаются все строки, сумма элементов которых максимальна
2. случайным образом выбирается любая из этих строк

Если у найденной строки номер i, тогда все мультиверсии j, которым соответствуют r_ij равныеединице, являются корректными, а остальные ошибочными.

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

Основным недостатком классического алгоритма ГСБ является то, что решение принимается без учета накапливаемой статистики сравнения. При недостаточно высокой надежности самих программных модулей, снижается вероятность того, что класс с относительно большим числом элементов будет корректным. Это связано, с одной стороны, с тем, что корректные состояния может быть и в группе с несколько меньшим числом элементов, чем самая большая. А с другой – это элемент случайности при выборе среди классов с одинаковым числом состояния.

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

, где

i – номер строки в матрице согласования;

p_j – вероятность корректного выхода мультиверсии j;

n – количество мультиверсий.

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

Тогда схема выбора нужного класса выходов принимает вид:

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

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

 

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

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

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

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

Эта функция имеет прямоугольную форму (рисунок 2.4а) с центром в точке a и шириной основания равной ε. Степень принадлежности внутри этого прямоугольника равна 1, вне – равна 0. Однако, более удобно задавать степень принадлежности так, чтобы она уменьшалась по мере удаления от a. Например, задавать ее в виде треугольника (рисунок 2.4б):

(1)

 

Рисунок 2.4. Характеристическая функция соотношения равенства x и a
как а) четкого множества и б) нечеткого множества в форме треугольника

 

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

R = { r_ij }, где

Далее, производят усечение значений элементов полученной матрицы R к булевому виду , по некоторому заданному пороговому значению λ. Причем, значение λ нередко указывают в названии применяемой методики - например, для λ=0,5, название будет НГСБ-0,5.

Усечение значений происходит по следующей схеме:

После этого, полученная матрица = { } используется как матрица согласования в четком методе голосования согласованным большинством (как базовом, так и взвешенном), рассмотренном выше.

 

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

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

, где

r – корректный результат;

α_i – весовой коэффициент;

x_i – выход мультиверсии i;

n – количество мультиверсий.

Если α_i ≠ 1, то данный алгоритм называется взвешенное медианное голосование.

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

Выводы

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

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

 

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

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Показатель количества побед как мультиверсия отобра