Мультиверсионное программирование как методология проектирования отказоустойчивого программного обеспечения систем управления и обработки информации 17 2. <...> Неоднозначность принятия решения в алгоритмах голосования согласованным большинством…… 39 3.2. <...> Мультиверсионный подход предполагает независимую генерацию и параллельное исполнение нескольких версий одного и того же программного модуля. <...> Алгоритмы голосования в мультиверсионном ПО зарекомендовали себя как достоверный способ выбора корректных ответов из всего множества результатов работы версий. <...> Мультиверсионное программирование как методология проектирования отказоустойчивого программного обеспечения систем управления и обработки информации Все принципы и методы обеспечения надёжности в соответствии с их целью можно разбить на четыре группы [46]: предупреждение ошибок, обнаружение ошибок, исправление ошибок и обеспечение устойчивости к ошибкам. <...> Употребляемый в литературе термин «N-версионное программирование» – NVP (N-version programming) является эквивалентным и многократно фигурирует в сокращенных обозначениях рассматриваемой методологии. <...> Авижиенис определил мультиверсионное программирование как независимую генерацию N ≥ 2 функционально эквивалентных программ в соответствии с идентичными исходными спецификациями на проектирование ПС. <...> Результат (мультиверсионное программное обеспечение – NVS, N-version software) процесса мультиверсионного программирования, для которого имеются в наличии средства конкурентного исполнения со специфическими точками контроля и «с-векторами». <...> Внешние средства поддержки исполнения версий ПО (N-version executive, или NVX), которые обеспечивают выполнение NVS и предусматривают алгоритмы принятия решений в контрольных точках. <...> Первоначально появился термин «избыточное программирование» [1] с решающей функцией, аналогичной мажоритарной схеме голосования в технических системах, и лишь позднее при систематизации <...>
Мультиверсионное_программное_обеспечение._Алгоритмы_голосования_и_оценка_надежности.pdf
Министерство образования и науки Российской Федерации
Сибирский федеральный университет
Р. Ю. Царев, А. В. Штарик, Е. Н. Штарик
МУЛЬТИВЕРСИОННОЕ
ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ.
АЛГОРИТМЫ ГОЛОСОВАНИЯ
И ОЦЕНКА НАДЁЖНОСТИ
Монография
Красноярск
СФУ
2013
1
Стр.2
УДК 004.451.46
ББК 32.973.233-018
Ц181
Рецензенты:
А. Н. Антамошкин, доктор технических наук, профессор, зав. кафедрой
математического моделирования и информатики КрасГАУ;
А. В. Медведев, доктор технических наук, профессор кафедры системного
анализа и исследования операций СибГАУ им. М. Ф. Решетнёва
Царев, Р. Ю.
Ц181 Мультиверсионное программное обеспечение. Алгоритмы голосования
и оценка надёжности : монография / Р. Ю. Царев, А. В. Штарик,
Е. Н. Штарик. – Красноярск : Сиб. федер. ун-т, 2013. – 120 c.
ISBN 978-5-7638-2749-1
В монографии представлены современные алгоритмы голосования, используемые
в мультиверсионном программном обеспечении при принятии решения
о корректности полученных результатов; приведена их классификация.
Рассмотрены проблемы применения алгоритмов голосования в мультиверсионном
программном обеспечении. Показана модель оценки надёжности мультиверсионного
программного обеспечения, представлены результаты ее исследования
при имитировании поведения реальной мультиверсионной системы с распределенной
архитектурой.
Результаты исследования служат теоретической базой для разработки высоконадёжного
и отказоустойчивого программного обеспечения на основе мультиверсионной
парадигмы.
Предназначено специалистам, работающим в области проектирования и
разработки программного обеспечения, а также аспирантам и докторантам. Материалы
монографии рекомендуются к использованию при проведении лекционных
и практических занятий у магистрантов, обучающихся по программе подготовки
магистров 230100.68 «Информатика и вычислительная техника».
УДК 004.451.46
ББК 32.973.233-018
ISBN 978-5-7638-2749-1
2
© Сибирский федеральный
университет, 2013
Стр.3
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ……………………………………………………………… 5
1. МУЛЬТИВЕРСИОННОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
КАК СПОСОБ ПОВЫШЕНИЯ НАДЁЖНОСТИ
ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ…………….. 7
1.1. Программный компонент систем управления
и обработки информации……………………………………….. 7
1.2. Надёжность функционирования программного обеспечения
1.2.1. Надёжностная характеристика программного модуля
9
9
1.2.2. Обеспечение надёжности программ
с помощью введения избыточности……………………... 14
1.3. Мультиверсионное программирование как методология
проектирования отказоустойчивого программного
обеспечения систем управления и обработки информации
17
2. АЛГОРИТМЫ ГОЛОСОВАНИЯ В МУЛЬТИВЕРСИОННОМ
ПРОГРАММНОМ ОБЕСПЕЧЕНИИ……………………………….. 22
2.1. Алгоритмы голосования, основанные
на сравнении выходных данных………………..……………… 23
2.1.1. Неформализованные алгоритмы голосования………….. 24
2.1.2. Формализованные алгоритмы голосования…………….. 34
2.2. Алгоритмы с принятием решения вне зависимости
от схожести выходных данных………………………………… 35
2.2.1. «Максимально вероятное» голосование (MLV)………… 36
2.2.2. Усреднённое голосование………………………………… 38
3. СПЕЦИФИКА ПРИМЕНЕНИЯ АЛГОРИТМОВ
ГОЛОСОВАНИЯ В МУЛЬТИВЕРСИОННОМ
ПРОГРАММНОМ ОБЕСПЕЧЕНИИ
ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ…………….. 39
3.1. Неоднозначность принятия решения
в алгоритмах голосования согласованным большинством…… 39
3.2. «Склеивание» подмножеств выходных данных……………….. 49
3.3. Оценка результатов голосования……………………………….. 55
3.4. Несовместность разбиений в алгоритмах с минимизацией…… 58
3.5. Выбор значения -сечения в нечётких алгоритмах……………. 59
3.6. Комплексное применение алгоритмов голосования
в мультиверсионном программном обеспечении……………… 62
4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМОВ
ГОЛОСОВАНИЯ В МУЛЬТИВЕРСИОННОМ
ПРОГРАММНОМ ОБЕСПЕЧЕНИИ………………………………. 70
4.1. Программа NVX…………………………………………………. 70
4.1.1. Особенности программы…………………………………. 70
3
Стр.4
4.1.2. Взаимодействие с исполняемыми версиями……………. 71
4.1.3. Общая схема работы программы………………………… 72
4.1.4. Обобщенная схема работы версий………………………. 74
4.1.5. Требования к разработке версий…………………………. 75
4.2. Программа NVX-m………………………………………………. 75
5. МОДЕЛИ И МЕТОДЫ ОЦЕНКИ НАДЁЖНОСТИ
ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ……………………………… 78
5.1. Модель анализа на этапе дизайна архитектуры
программного обеспечения……………………………………… 79
5.2. Анализ надёжности программного обеспечения
на фазе кодирования……………………………………………... 81
5.3. Анализ надёжности программного обеспечения
на фазе тестирования системы………………………………….. 82
5.4. Модель оценки транзакционной надёжности
объектно-ориентированного программного обеспечения…….. 83
5.5. Универсальная модель оценки надёжности
объектно-ориентированного мультиверсионного
программного обеспечения с распределенной архитектурой
6. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МОДЕЛЕЙ И МЕТОДОВ
ОЦЕНКИ НАДЁЖНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
84
86
6.1. Система SMR……………………………………………………. 86
6.1.1. Назначение и общие сведения
о системе поддержки принятия решений SMR…………. 87
6.1.2. Структура информационной системы…………………… 88
6.1.3. Описание основных подсистем…………………………... 89
6.2. Результаты применения системы SMR………………….……… 90
ЗАКЛЮЧЕНИЕ…………………………………………………………. 98
БИБЛИОГРАФИЧЕСКИЙ СПИСОК…………………………………. 100
Приложение 1. Применение алгоритма выбора значения
λ-сечения CVS………………………………………… 109
Приложение 2. Условия успешного применения
алгоритмов голосования……………………………… 116
4
Стр.5