Содержание к диссертации
Введение
1. Мультиверсионное программное обеспечение как способ повышения надёжности информационно-управляющих систем 9
1.1. Программный компонент систем управления и обработки информации 9
12. Надежность функционирования программного обеспечения 13
1.2,1- Надежностная характеристика программного модуля , 13
12,2. Обеспечение надежности программ с помощью введения избыточности 19
1.3. Мультиверсионное программирование как методология проектирования отказоустойчивого программного обеспечения систем управления и обработки информации 23
Выводы 28
2. Алгоритмы голосования в мультиверснонном программном обеспечении 30
2.1. Алгоритмы голосования, основанные на сравнении выходных данных 32
2.1 Л. Неформализованные алгоритмы голосования 33
2.1.2. Формализованные алгоритмы голосования 49
22. Алгоритмы с принятием решения вне зависимости от схожести выходных данных 50
2.2.1. «Максимально вероятное» голосование (MLV) 51
2.2.2, Усреднённое голосование 54
Выводы 54
3. Специфика применении алгоритмов голосования в мультиверснонном программном обеспечении информационно-управляющих систем 56
3Л. Неоднозначность принятия решения в алгоритмах голосования согласованным большинством 56
3.2. «Склеивание» подмножеств выходных данных 71
33. Оценка результатов голосования 78
ЗА Несовместность разбиений в алгоритмах с минимизацией 82
3.5. Выбор значения Х-сечения в нечётких алгоритмах 85
3.6Г Комплексное применение алгоритмов голосования в мультиверснонном программном обеспечении 89
Выводы 97
4. Программная реализация результатов работы 99
4.1. Программа NVX 99
4ЛЛ. Особенности программы 100
4Л.2. Взаимодействие с исполняемыми версиями 101
4Л.З. Общая схема работы программы 103
4.1.4. Обобщенная схема работы версии 104
4.1.5. Требования к разработке версий 105
4.2. Программа NVX-m 106
Заключение 109
Список использованных источников * 112
- Обеспечение надежности программ с помощью введения избыточности
- Формализованные алгоритмы голосования
- Неоднозначность принятия решения в алгоритмах голосования согласованным большинством
- Взаимодействие с исполняемыми версиями
Введение к работе
Актуальность темы исследования. Информационно-управляющие системы, применяемые в критичных областях (контроль полётов, атомная промышленность и др.) должны быть максимально надежными. Решающую роль в обеспечении надёжности информационно-управляющих систем играет программный компонент.
На сегодняшний день существует ряд методов повышения надёжности программного обеспечения (ПО) информационно-управляющих систем (ИУС). Достаточно эффективным методом обеспечения надёжности ПО, положительно зарекомендовавшим себя на практике, является концепция мультиверсий [І, 5, 13-19, 25, 29-40, 47, 50-52, 57-68, 70, 72-75, 77-78, 80, 82-92, 96-99, 101-102, 105-108,110-113,115,119].
Мультиверсионный подход предполагает независимую генерацию и параллельное исполнение нескольких версий одного и того же программного модуля. При этом версии разрабатываются на основе идентичных исходных спецификаций. Концепция мультиверсий даёт ряд преимуществ, в частности, отказ одной версии не приведёт к отказу всей системы. Однако при использовании мультиверсионного подхода существует возможность, что версии выдадут различные результаты. Таким образом, возникает задача определить, какие результаты являются корректными, а какие ошибочными.
Задача может быть решена либо путём использования алгоритмов голосования, либо применением приемочных тестов. Алгоритмы голосования в мультиверсионном ПО зарекомендовали себя как достоверный способ выбора корректных ответов из всего множества результатов работы версий, В настоящее время предложено множество алгоритмов голосования, которые различаются схемами работы и требованиями к исходным данным.
Подчеркнём, что результат работы алгоритма голосования определяет итог работы всей мультиверсионной системы. Поэтому ошибка в процессе голосования может привести к отказу всей системы, и, соответственно к значительным потерям. Таким образом, процесс голосования в мул инверсионном ПО очень важен, что и определяет актуальность исследований в данной области.
Целью диссертационной работы является повышение достоверности принятия решений в мультиверсиониом программном обеспечении ИУС с использованием алгоритмов голосования. Для достижения поставленной цели решались следующие задачи теоретического и практического характера:
• Теоретический обзор концепций повышения надёжности программного обеспечения информационно-управляющих систем.
• Сравнительный анализ применяемых в настоящее время атгоритмов голосования.
• Разработка программной модели процесса голосования в мультиверсионных системах и исследование поведения алгоритмов голосования при различных исходных данных.
• Анализ специфики применения алгоритмов голосования в мультиверсиониом программном обеспечении ИУС.
• Повышение достоверности принятия решений в мультиверсиониом ПО путём модификации алгоритмов голосования и разработки методики комплексного применения алгоритмов.
• Реализация результатов исследования в программной среде исполнения мультиверсионных систем.
Методы исследования. При выполнении работы использовались системный анализ, дискретная математика, теория вероятностей, теория нечётких множеств, а также методология мультиверсионного проектирования программных средств.
Научная новизна работы:
1, Впервые предложена классификация наиболее распространённых и универсальных алгоритмов голосования в мультиверсионном программном обеспечении и определены условия успешного применения алгоритмов,
2- Модифицированы алгоритмы голосования согласованным большинством; модификация позволяет однозначно принимать решение в случаях, когда в матрице согласования имеются две и более различных строк с максимальным числом единиц (различные подмножества с максимальной мощностью).
3. Предложены методы оценки достоверности голосования в зависимости от значения А,-сечения, и в зависимости от алгоритма голосования; методы основаны на введении дополнительных критериев, таких как разброс в выбранных выходах и относительное количество согласных версий.
4. Разработан алгоритм выбора значения -сечения в нечётких алгоритмах, позволяющий учесть все возможные исходы голосования, а так же достичь максимальной достоверности голосования по предложенным критериям.
5. Разработана методика комплексного применения алгоритмов голосования с возможностью формализованного выбора окончательного результата из множества результатов применённых алгоритмов.
Значение для теории. Материалы работы могут послужить базой для проведения исследований в области принятия решений в мультиверсионном ПО. Реализованная в рамках работы программная модель NVX-m даёт следующие преимущества для исследователей:
- возможность наглядно изучать процесс голосования для произвольных исходных данных,
- возможность анализировать результаты применения различных алгоритмов голосования,
- возможность автоматического вычисления характеристик, позволяющих оценить достоверность голосова
Практическая ценность работы. Реализация алгоритмов и методик, которые предложены в работе, в промышленных средах исполнения позволит повысить достоверность принятия решений в мультиверсионном ПО ИУС. Реализованная в ходе работы программа NVX представляет собой среду исполнения мультиверсионных систем. В NVX реализованы как классические алгоритмы голосования согласованным большинством, так и модифицированный алгоритм, что позволяет эффективно применять механизмы голосования согласованным большинством.
Основные защищаемые положения 1- Предложенная модификация алгоритмов голосования согласованным большинством позволяет достоверно выбрать правильный ответ в случаях, когда в матрице согласования имеются две и более различные строки с максимальным числом единиц (различные подмножества с максимальной мощностью).
2. Разработанные методы оценки достоверности голосования, основанные на введении дополнительных критериев, позволяют адекватно вычислять достоверность в зависимости от значения А,-сечения, и в зависимости от алгоритма голосования.
3. Разработанный алгоритм выбора значения Х-сечения в нечётких алгоритмах, позволяет учесть все возможные исходы голосования, и достичь максимальной достоверности по предложенным критериям.
4. Предложенная методика комплексного применения алгоритмов голосования позволяет эффективно принимать решение по выбору корректных ответов за счёт учёта специфики алгоритмов и возможности формализованного выбора окончательного результата из множества результатов применённых алгоритмов.
5. Разработанные программные продукты дают базу для проведения исследований в области принятия решений в мультиверсионном ПО, и позволяют успешно реализовывать параллельные вычислительные задачи.
Публикации. По теме диссертационной работы опубликовано 12 печатных работ. Перечень публикаций представлен в конце автореферата.
Апробация работы. Основные положения и результаты работы обсуждались на международных и всероссийских научных и научно-практических конференциях- В том числе;
• X Международная научная конференция «Решетневские чтения» (Красноярск, 2006);
• V Международная научно-практическая конференция «Информационные технологии и математическое моделирование» (Томск, 2006);
• Международная научная конференция с международным участием «Проблемы передачи и обработки информации» (Дубай, ОАЭ, 2006);
• Международная научно-практическая конференция «Фундаментальные и прикладные исследования высшей школы» (Сингапур, 2007);
• Державинские чтения (Тамбов, 2007).
Диссертационная работа в целом обсуждалась на научных семинарах Сибирского государственного аэрокосмического университета, а также НИИ Систем управления, волновых процессов и технологий (2005-2007 гг.).
Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы из 120 наименований и двух приложений. Объем диссертационной работы 124 страницы, приложений- 11 страниц.
Обеспечение надежности программ с помощью введения избыточности
При искажении вычислительного процесса или данных задача состоит в максимально быстром обнаружении искажения, точной классификации типа уже имеющихся и возможных последствий искажения, а также в проведении мероприятий, обеспечивающих быстрое восстановление нормального функционирования программного обеспечения. Неизбежность ошибок в сложных программных системах, искажений исходных данных и аппаратных сбоев приводит к необходимости регулярной проверки процесса исполнения программ и сохранности данных, В процессе проектирования недостаточно создать правильные программы, выдающие верные результаты при идеальных исходных данных и абсолютном отсутствии любых возмущений. Требуется разрабатывать надежные программы, устойчивые к различным возмущениям и способные сохранять достаточное качество выходных результатов в реальных условиях функционирования. В любых ситуациях прежде всего должны исключаться катастрофические последствия и длительные отказы или в максимальной степени смяі маться их влияние на результаты, выдаваемые пользователю.
Избыточность для обеспечения надежности функционирования программной системы используется, прежде всего, для контроля и селекции искажений вычислительного процесса или данных и для выработки мер по снижению последствий этих аномалий. Основная задача состоит в ограничении или исключении возможности аварийных последствий, соответствующих отказу системы в процессе функционирования.
Под временной избыточностью понимается использование некоторой части производительности ЭВМ для контроля исполнения программ и восстановления вычислительного процесса. Для этого при проектировании программ должен предусматриваться запас производительности, который затем используется для контроля и повышения надежности функционирования. Диагностика искажений и операций восстановления требует в общем случае небольшой интервал времени, который выделяется либо за счет резерва, либо за счет сокращения времени решения функциональных задач.
Информационная избыточность состоит в дублировании накопленных исходных и промежуточных данных, обрабатываемых программной системой. Избыточность используется для сохранения достоверности данных, которые в наибольшей степени влияют на нормальное функционирование программ или требуют значительного времени для восстановления. Информационная избыточность может способствовать не только обнаружению искажений данных, но и устранению ошибок. Для этого данные защищают двух-трехкратным дублированием с соответствующей дисциплиной контроля сохранности и периодического обновления.
Программная избыточность используется для контроля и обеспечения достоверности наиболее важных результатов обработки информации. Она заключается в применении в программной системе нескольких вариантов программ, различающихся методами решения некоторой задачи или программной реализации одного и того же метода, Программная избыточность необходима также для реализации программ контроля и оперативного восстановления данных с использованием информационной избыточности и для функционирования всех средств защиты, использующих временную избыточность.
Последовательный характер исполнения программ процессором ЭВМ приводит к тому, что средства программного контроля включаются после исполнения рабочих программ. Поэтому средства программно контроля не могут обнаруживать непосредственное возникновение искажения вычислительного процесса или данных и фиксируют, как правило, только последствия первичного искажения. Последствия такого первичного искажения в ряде случаев могут развиваться во времени и принимать катастрофический характер отказа при увеличении запаздывания в обнаружении первичного искажения. Факт наличия любого искажения желательно обнаруживать при минимальных затратах ресурсов ЭВМ и с минимальным запаздыванием. Это приводит к использованию иерархических схем контроля, при которых несколько методов используется последовательно в порядке углубления контроля и увеличения затрат до достоверного выявления искажения. С точки зрения построения средств защиты и распределения ресурсов ЭВМ можно выделить искажения результатов трех типов:
приводящие к прекращению выполнения основных функций программной системы на длительное или неопределенное время;
кратковременно, но значительно искажающие отдельные результаты по их смысловому содержанию или величине;
мало и кратковременно влияющие на результаты, выдаваемые программами.
Такое качественное деление искажений предопределяет распределение ресурсов по защите. Наибольшие ресурсы целесообразно выделять и в максимальной степени следует принимать меры защиты от искажений информации и вычислительного процесса первого типа, последствия которых могут проявляться в следующем виде:
зацикливание, то есть последовательная повторяющаяся реализация определенной группы команд, не прекращающаяся без внешнего вмешательства;
останов и прекращение решения функциональных задач; искажение процессов взаимного прерывания программ, приводящее к блокировке возможности некоторых типов прерываний; прекращение или значительное снижение темпа решения некоторых задач вследствие перегрузки ЭВМ по пропускной способности;
значительное искажение или потеря накопленной информации о текущем состоянии внешней среды.
Искажения информации и вычислительного процесса второго типа также весьма опасны, и для защиты от них следует применять эффективные меры. Эти искажения могут проявляться в следующем виде: -пропуск модуля или группы программ;
Формализованные алгоритмы голосования
Отличительной чертой формализованного голосования является то, что в процессе голосования множество выходов разбивается на подмножества, которые не обязательно не пересекаются [101, 104]. Это так же означает, что при классификации некоторые выходы могут входить более чем в одно подмножество. К алгоритмам данного класса относятся алгоритмы FMV и FCV.
Формализованный алгоритм голосования абсолютным большинством (FMV)
Пусть число версий равно N, хьх2, ... , xN - значения выходов, є -допустимое отклонение. FMV работает по следующей схеме.
Шаг 1. Разбиение множества выходов на подмножества. Множество версий разбивается на N подмножеств. Каждому выходу соответствует свое подмножество. Для выхода і (і = 1,."»N) подмножество Q строится по следующему принципу
При этом каждый выход входит как минимум в одно подмножество.
Шаг 2. Определение набора корректных выходов. На этом шаге должны быть рассмотрены полученные подмножества. В каждом подмножестве подсчитывается количество элементов. Обозначим количество элементов в i-том подмножестве Yj. Если существует такое подмножество С;, для которого справедливо неравенство (2.11), то набор корректных ответов определяется как подмножество Cj. Если подмножество, удовлетворяющее требованию формулы (2.11) отсутствует, то принять решение с помощью алгоритма FMV не возможно. Формализованный алгоритм голосования согласованным большинством (FCV)
Пусть число версий равно N, хьх2, ... , х - значения выходов, є -допустимое отклонение. FCV работает по следующей схеме.
Шаг 1. Разбиение множества выходов на подмножества. Множество версий разбивается на N подмножеств. Каждому выходу соответствует свое подмножество. Для выхода і (і = 1,...,N) подмножество С; строится согласно формуле (2.12).
Шаг 2. Определение набора корректных выходов. На этом шаге должны быть рассмотрены полученные подмножества. В каждом подмножестве подсчитывается количество элементов. Обозначим количество элементов в i-том подмножестве YCJ. Далее выбирается подмножество, в котором Yc; максимально. Набор корректных ответов определяется как подмножество Cj. Если существует несколько подмножеств с максимальным числом элементов, то в качестве набора корректных ответов выбирается случайное подмножество.
Алгоритм FCV выдаёт результат в любом случае: даже если «согласных» версий нет, алгоритм вернёт выход, выбранный случайным образом.
Перед тем как перейти к рассмотрению схем работы алгоритмов остановимся на некоторых особенностях их применения:
результат работы алгоритмов не зависит от того, на сколько выходы версий «схожи» результатом работы алгоритмов является только одно значение (той же структуры что у выходов версий)
Концепция максимально вероятного голосования зарекомендовала себя как один из самых достоверных механизмов принятия решения в мультиверсионном ПО [81,93,104,116].
Неоднозначность принятия решения в алгоритмах голосования согласованным большинством
Рассмотрев схемы работы алгоритмов голосования согласованным большинством (NVP-CV, Fuzzy CV, minCV и FCV) можно сделать вывод, что данные алгоритмы неэффективны для некоторых наборов выходных данных. Неэффективность связана с тем, что если в матрице согласования присутствуют несколько различных строк с максимальным числом единиц (или несколько различных подмножеств с максимальным числом элементов для FCV и minCV), то выбор корректных результатов осуществляется случайно. Здесь под «различными строками» понимаются строки, в которых позиции единиц не совпадают («различные множества» - множества, различающиеся хотя бы одним элементом). Так, если мы имеем две различных строки с максимальным Шаг 2- Среди полученных подмножеств в Сі,С2,Сз,С5,Сб С7 количество элементов максимально. При этом С\=Сх=Сз и С =Сб=С7, но Ci Cs. Таким образом, множество корректных выходов равно либо {xi=0,32111; х2Ю,322556; х3=0,32399}, либо {х5=0,82199; х6=0,8221; х7=0, 82299}. Снова перед нами стоит задача выбора одного из множеств. При случайном выборе вероятность корректного срабатывания модуля рана только 50%,
Воспользуемся алгоритмом minCV.
Шаг 1. Разбиение множества выходов на подмножества. - Выбираем элемент Х] и заносим в подмножество С\ все выходы, эквивалентные Xi: Сі = {х,И),32111; х2=0?322556; ху=0,32399}
- Вычёркиваем из множества выходов элементы X] х2, и хз„ Теперь множество ВЫХОДОВ СОДерЖИТ ЭЛемеНТЫ Х4, Х5ч Хб, Х7? Xg, х9.
- Множество выходов пока не пустое. Выбираем элемент х4 и заносим в подмножество С2 все выходы, эквивалентные х4: С2={х4=0,65; х8-0,651}
Неоднозначное хь возникает в случаях, когда мы полу согласования с двумя и более различными еіроісами с едшвщ {ипы два и более различных нолмйоже мощностью). Поскольку выбор осуществляется только по одно? числу единиц (подмножеств), возникает пеодшшшч ее;щ бы мы имели возможность ержпштіь кошере кашму-то другому параметру, проблема могла бы быть j. ленолышвшь в качестве такого параметра надёжности г ! ы согласных версий. Так, например, Предлагаем : мч которые наборы версий {хьхэ,хз} и {х45х55х6} по надёжности, то следует вычислить надёжности и затем сравнить полученные значения R j и Ru.6 Принимая во внимание последний факт, предлагаем модифицированные алгоритмы NVP-CV, FCV, minCV, Fuzzy CV. В модифицированных алгоритмах принятие решения производится с учетом надёжностей версий. Назовём модифицированные алгоритмы L-CV, L-FCV, L-minCV, L-Fuzzy CV (Likely CV, Likely FCV, Likely minCV, Likely Fuzzy CV) или вероятностными алгоритмами голосования согласованным большинством.
Взаимодействие с исполняемыми версиями
Взаимодействие с процессами исполняемых версий (обмен командами) осуществляется с использованием оконных сообщений [24, 42, 45, 53]. То есть при посылке сигнала от среды к версии (или от версии к среде) в качестве адреса назначения выступает заголовок окна версии.
Программы-версии должны иметь способность посылать команды «running», «check», «done» и реагировать на единственную команду «resume». Посылка команд должна осуществляться по следующим принципам:
Посылка команды «running» - означает, что программа выполняется.
в Посылка команды «check» - означает, что программа доработала до контрольной точки и находится в ожидании, что остальные версии тоже доработают до контрольной точки.
Посылка команды «done» - означает, что программа завершила все вычисления и находится в ожидании, что остальные версии тоже завершат вычисления.
Программа NVX работает по следующей схем .
Независимо от задачи, которую решает мультиверсионныи модуль, логика работы каждой версии должна быть следующей:
Сама программа NVX является законченным продуктом. Это означает, что нет необходимости менять исходный код NVX в зависимости от состава и функций версий. Однако, к разработке версий предъявляются дополнительные требования:
1. Обеспечение взаимодействия с программой NVX:
- поддержка всех команд в соответствии с механизмом адресации данных и схемами работы среды (рис 4.1) и версии (рис 4.2),
- заголовок окна версии должен иметь фиксированный вид -version[HOMep версии]. Например, если используется три версии, то заголовки окон программ-версий должны быть versionl, version2, version3
- все сигналы (running, check, done) должны посылаться в адрес процесса с заголовком окна «NVX». При этом формат сообщений должен быть следующий [номер версии][пробел][команда].
2. Число контрольных точек для всех версий должно быть одинаково.
3. Если версия сохраняет результаты в текстовый файл, то файл должен содержать только числа, элементы массива должны быть разделены пробелами, целая часть числа от дробной должна отделяться запятой, должна быть обеспечена возможность перезаписи текстового файла программой NVX.
4. Если версии сохраняют выходные данные в таблицы базы данных MySQL, то необходимо выполнение следующих действий.
На сервере СУБД:
- создать базу данных для хранения выходов,
- в созданной базе данных создать таблицы для хранения выходов версий,
- задать необходимые права на доступ к таблицам. На компьютере где выполняется программа NVX:
- установить драйвер mysql-connector-odbc-3.51.12,
- произвести первичную настройку драйвера (установить драйвер как System DSN).
Программа NVX-m представляет собой модель иллюстрирующую работу алгоритмов голосования в мультиверсиопном ПО. Программа использует в качестве исходных данных числовые значения выходов версий. Число версий не оіраничено и задаётся в начале работы программы. Однако, выход каждой версии должен быть скалером. То есть, предполагается, что каждая версия имеет единственный выход - число.
В программе реализованы все 14 алгоритмов голосования, рассмотренные в данной работе, в том числе 4 модифицированных алгоритма.
Кроме того, в программе реализована возможность расчета достоверности голосования в зависимости от Х-сечения в нечетких алгоритмах. Расчёт производится с использованием формул (3.6) и (3.7).
При работе с NVX-m сперва необходимо указать исходные данные для голосования: число версий, допустимое отклонение, значение Х-сечения, выход каждой версии, надёжность каждой версии. Значение Агсечения следует устанавливать только в случае, когда предполагается использование нечётких алгоритмов голосования. Если не предполагается использование алгоритмов, использующих надёжности версий, надёжности версий могут не указываться. После того, как исходные данные установлены, можно смотреть результат по интересующему алгоритму голосования. Программа так выводит данные, на основе которых принято решение (матрицы согласования, отношения подобия, разбиения и другие).
