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

Концепция мультиверсионного программирования (МВП), как подход к реализации программной отказоустойчивости, была введена А. Авижиенисом в 1977 году [14]. Употребляемый в литературе термин "N-версионное программирование" – NVP (N-version programming) является эквивалентным и многократно фигурирует в сокращенных обозначениях рассматриваемой методологии.

А. Авижиенис определил мультиверсионное программирование как независимую генерацию N≥3 функционально эквивалентных программ (мультиверсий) в соответствии с идентичными исходными спецификациями на проектирование ПС. Для этих N программ предоставлены средства конкурентного исполнения, по ходу которого в определенных точках контроля ("cc-points" от cross-check points, точки перекрестного контроля) программами генерируются векторы сравнения ("c-vectors" от comparison vectors, векторы сравнения). Составляющие векторов сравнения и контрольные точки генерации "с-векторов" предварительно определены еще на этапе исходных спецификаций.

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

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

1. Процесс исходной спецификации и мультиверсионного программирования (NVP), который предполагает гарантию независимости и функциональной эквивалентности N индивидуальных процессов программирования.
2. Результат (мультиверсионное программное обеспечение – NVS, N-version software) процесса мультиверсионного программирования, для которого имеются в наличии средства конкурентного исполнения со специфическими точками контроля и "с-векторами".
3. Внешние средства поддержки исполнения версий ПО (N-version executive или NVX), которые обеспечивают выполнение NVS и предусматривают алгоритмы принятия решений (decision algorithms) в контрольных точках.

Рисунок 1.8. Модель мультиверсионного программного средства при N=3.

 

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

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

Первоначально появился термин "избыточное программирование" (redundant programming) [16] с решающей функцией, аналогичной мажоритарной схеме голосования в технических системах, и лишь позднее при систематизации модель была выделена в мультиверсионное программирование.

По аналогии с многоканальными аппаратными средствами, работающими в критических условиях с повышенными требованиями по отказоустойчивости (наземные и бортовые комплексы управления летательными аппаратами, включая космические, компьютеризированные средства управления атомными реакторами и другими опасными для жизнедеятельности людей объектами), также предоставляющими собой N≥3 аппаратных блоков, необходимо расширение "простого" ПО путем добавления избыточных версий программных блоков. Наличие избыточных компонент предполагает компенсировать (замаскировать) версии программ, для которых в контрольных точках обнаруживаются сбои, отказы или ошибки. Следует отметить, что существенным отличием между аппаратными средствами и программным обеспечением является неэффективность метода простого дублирования при поддержании устойчивости к ошибкам в программном комплексе. Это связано с тем, что простое дублирование элементов, эффективное против случайных ошибок, имеющих физическую природу, в технических системах, неэффективно при отказах программного обеспечения, так как оно предопределяет дублирование необнаруженных на этапе отладки ("спящих") ошибок в программах. Поэтому N программных версий должны разрабатываться отдельно и независимо друг от друга, что и соответствует концепции проектирования избыточного программного обеспечения.

Однако, наличие N≥3 версий избыточных версий программных модулей еще не обеспечивает устойчивость КП к отказам, так как необходимо наличие среды исполнения (execution environment – EE) для мультиверсионного программного обеспечения. Как отдельные версии ПО, так и среда исполнения, должны отвечать следующим требованиям:

1. Среда исполнения должна предусматривать функции поддержки исполнения версий программных компонент в режиме контроля ошибок;
2. Индивидуальные спецификации версий ПО должны определять способы достижения отказоустойчивого исполнения, которые поддерживаются в среде исполнения;
3. Наилучший исход мультиверсионного программирования должен минимизировать вероятность необнаружения ошибочного исполнения мультиверсионного программного компонента в отличие от обычной программной системы.

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

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

Определив основные элементы мультиверсионного программирования, отметим не менее важные проектные этапы, относящиеся к:

1. Спецификациям версий NVS-систем ПО (с учетом требований к их дальнейшему конкурентному исполнению в ЕЕ-среде с использованием внешних средств поддержки исполнения NVX);
2. Непосредственному этапу программирования, учитывая, что основное требование NVP – максимальная независимость исходов процесса и, соответственно, версий ПО;
3. Созданию NVX-систем среды исполнения программных компонент мультиверсионного ПО как с высокой надежностью, так и с эффективными показателями по времени исполнения, что особенно важно для использования мультиверсионных КП в комплексах управления системами реального времени.

Решение первой из указанных проблем основывается на применении системы спецификаций мультиверсионного ПО, названной "V-Spec" (V‑спецификации), которая определяет:

§ функциональное предназначение с учетом ограничений по времени исполнения, исходных данных и начального состояния версии ПС;

§ требования по внутреннему контролю ошибок и тестирования версий модуля;

§ требования по диверсификации программирования;

§ контрольные точки (сс-точки), в которых решающий алгоритм среды исполнения предполагается быть примененным для контроля всех версий;

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

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

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

§ решающий алгоритм или множество алгоритмов;

§ входные последовательности данных для всех версий;

§ внутриверсионная коммуникация;

§ синхронизация исполнения версий (если позволяет аппаратно-программный комплекс) при жестких временных ограничениях;

§ "локальное" управление исполнением каждой версии;

§ "глобальное" исполнение мультиверсионного ПО в совокупности с решающими функциями.

Смысл проектной парадигмы мультиверсионного программирования проиллюстрируем с учетом взаимосвязи с традиционными этапами жизненного цикла ПО. Парадигма проектирования мультиверсионных КП преследует цели:

§ уменьшения вероятности проектных недочетов, ошибок и несообразностей в процессе разработки и тестирования мультиверсионных ПС;

§ устранения большинства обнаруженных ошибок этапа проектирования в независимо генерируемых версиях программ и установления причин ошибок, не отслеженных на этапе проектирования;

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

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

§ обеспечивать полную независимость (с учетом ошибок ПО) всех конкурентно разрабатываемых версий;

§ максимально способствовать разнообразию всех версий каждого программного модуля;

§ вырабатывать эффективный механизм обнаружения ошибок.

На рисунке 1.9 парадигма мультиверсионного программирования представлена мероприятиями двух типов [17]:

1. Стандартные процедуры разработки ПС (прямоугольники с одинарными стрелками на схеме);
2. Параллельная (конкурентная) реализация средств мультиверсионного исполнения (овалы и двойные стрелки на схеме).

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

1. Этап выработки требований к системе – формирование метода управления мультиверсионным ПО.

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

§ Выбор метода исполнения мультиверсионного ПО и способа распределения вычислительных ресурсов. На этапе выработки требований к системе формируется комплексная архитектура системы и устанавливаются параметры программной составляющей. Определяется число версий и обозначаются способы их взаимосвязи.

§ Разработка механизма поддержки и инструментария. Адаптируется существующая среда поддержки мультиверсионного исполнения для утилизации в проектируемой системе либо разрабатывается новая. Причем, NVX-среда может быть реализована программно, аппаратно, либо программно-аппаратно. Базовые функции среды поддержки мультиверсионного исполнения включают: (а) алгоритм (либо набор алгоритмов) принятия решений; (б) средства обеспечения соответствия исходных состояний всех версий; (в) синхронизацию версий и выполнение ограничений по времени; (г) "локальный" супервизор для каждой версии; (д) общее конкурентное исполнение и решающие функции для восстановления ошибочных версий; (е) интерфейс пользователя для контроля, ввода команд управления, сбора информации при исполнении программ. Сущность этих функций полностью раскрывается при описании самой первой мультиверсионной системы DEDIX, разработанной Университетом Лос-Анджелеса и рассмотренной в [18].

 

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

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

2. Этап выработки требований к ПО – диверсификация ПО.

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

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

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

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

3. Этап спецификации ПО – установка алгоритмов определения ошибок и восстановления.

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

4. Фазы проектирования и кодирования – ведение протокола разработки мультиверсионного ПО.

На этом этапе начинается мультипрограммирование конкурентных версий ПС в соответствии со спецификациями V-spec. Определяется строгий протокол взаимодействия и документирования (communication and documentation protocol, C&D protocol). Одним из положительных следствий ведения C&D протокола является то, что он дает достаточную совокупность деталей на более поздней стадии эксплуатации ПО.

5. Этап тестирования – предварительная эксплуатация мультиверсионного ПО.

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

6. Этап оценки и принятия – оценка гарантоспособности комплекса мультиверсионного ПО.

Оценка атрибутов, характеризующих отказоустойчивость ПС, подразумевает аналитическое моделирование, имитацию и эксперименты (или комбинацию этих подходов). Необходимо: определить критерии оценки отказоустойчивости; оценить признаки диверсификации; сделать предварительные заключения, для чего рассматриваются два аспекта, касающиеся выбора подходящей модели оценки надежности ПС и определения количественных показателей метода оценки, соответственно [19, 23].

7. Этап эксплуатации – выбор способа сопровождения системы мультиверсионного ПО.

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

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