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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) МАИ

РГ6 О,

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

РЫБНИКОВ Дмитрий Леонидович

УДК: 519.68:681.3.06

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

СИСТЕМ

Специальность 05.13.13 - 'Вычислительные машины, комплексы,

системы и сети"

Автореферат

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

Москва Издательство МАИ 1997

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

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

профессор К. А. Иыуду

Официальные оппоненты: доктор технических наук,

профессор, Г. Н. Валаев

кандидат технических наук, старший научный сотрудникА. С. Марков

Ведущая организация: ЦНИИ АГ

Защита состоится ' _1997г. в_час._мин. на заседании

диссертационного совета Д05Э. 18.02 при Московском государственном авиационном института (техническом университете) по адресу: 125871, г. Москва, Волоколамское шоссе, д.4

Отзыв на автореферат в одном экземпляре, заверенном печатью, просим высылать по адресу: 125871, ГСП, г. Москва, Волоколамское шоссе, д.4.

Автореферат разослан

2 997г.

Ученый секретарь диссертационного совета,

кандидат технических наук, доцент У Ю. В. Горбатов

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

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

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

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

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

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

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

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

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

В соответствии с поставленной целью исследования проводились по следующим основным направлениям:

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

- разработка принципов построения моделей надежности отказоустойчивых многоверсионных программ при учёте влияния отказов и сбоев;

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

- исследование надёжности программ при учёте длительностей отказов версий;

- расчёт надёжности при рассмотрении допустимости временного нахождения в отказовом состоянии программ ответственных приложений;

- выбор ключевых вариантов организации вычислений многоверсионной программы в многопроцессорной БВС с учётом возможных отказов процессоров и построение соответствующей системы моделей;

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

Методы исследования. Решение перечисленных задач основывается на изучении опыта обеспечения надежности вычислений, выявлении эффективных суще-

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

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

Научная новизна.

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

- разработана методика представления длительностей нахождения версий программы в состоянии отказа в модели надёжности и проведено исследование влияния длительностей нахождения в состоянии отказа на безотказность;

- разработаны метод, методика и модели представления надежности голосования, проведено исследование эффективности алгоритмов голосования

- предложен метод отображения размещения версий по процессорным элементам (ПЭ) в комплексной модели надёжности;

- разработана методика учёта допустимости периодов нахождения процесса решения задачи в состоянии отказа при построении модели надежности;

- предложен метод представления реконфигурации в комплексной модели надежности;

-предложен метод представления сбоев различных ПЭ, вызываемых общими причинами, в комплексной модели надежности;

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

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

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

Внедрение результатов работы. Результаты диссертационной работы внедрены на ГНПО «Агат», и АОЗТ МО ПНИЭИ, что подтверждается соответствующими

актами.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях: 4-й всероссийской конференции "Качество информации" (Москва, 1994), международной научно-технической конференции "Методы и средства оценки и повышения надёжности приборов, устройств и систем" (Пенза, 1995), всероссийской научно-технической конференции «Вычислительные системы бортового базирования -95» (Москва, 1995), научной конференции "Актуальные проблемы анализа и обеспечения надёжности и качества приборов, устройств и систем" (Пенза, 1996).

Публикации. По материалам диссертации опубликовано 6 печатных работ.

Структура и объём работы. Диссертация состоит из введения и четырёх глав. Содержание изложено на 151 странице, в ЗВ рисунках и 24 таблицах. Список литературы содержит 105 наименований.

СОДЕРЖАНИЕ РАБОТЫ.

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

Первая глава посвящена анапизу состояния рассматриваемой проблемы, обоснованию и постановке основных задач исследования. Отмечаются высокие требования к надёжности бортового оборудования, в котором возрастающую роль играют средства вычислительной техники. Так, требования на допустимую вероятность отказа за 1 час полёта доходят до Ю-10 (пример - аэробус А-320).

В целом рассмотрены основные методы повышения надёжности и отказоустойчивости ПО и аппаратного обеспечения. Ориентируясь на специфику бортовых программ реального времени выделен метод М-версионного программирования. Метод подразумевает написание А/ (// к. 3, обычно нечётное) версий программы; в процессе выполнения результат программы получается после выполнения версий на основе голосования; таким образом достигается отказоустойчивость программы -устойчивость к отказам версий. Применение Ы-версионных программ целесообразно

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

Подчёркнуто, что безотказность выполнения функциональных задач БВС зависит как от надёжности программ, так и от надёжности аппаратного обеспечения. Задача обеспечения и расчёта надёжности многоверсионной программы совместно с аппаратным обеспечением требует для своего решения комплексного подхода к проблеме. Вычисления 1Ч-версионной программы в многопроцессорной (многомашинной) ВС могут обладать устойчивостью не только к собственно отказам версий, но и к сбоям, отказам отдельных процессорных элементов (ПЭ), в результате которых в таких случаях откажут лишь отдельные версии. Учитывая это, отмечено, что надёжность И-версионной программы при рассмотрении сбоев и отказов ПЭ зависит от следующих факторов:

- от размещения выполняющихся версий по процессорным элементам

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

- от выбора алгоритма голосования, который определит эффективность маскирования отказов

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

ально сказывается на адекватности оценок надежности, относящихся к интервалу времени.

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

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

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

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

1) представление размещения версий по ПЭ,

2) представление длительностей отказов,

3) представление учёта резерва ПЭ для реконфигурации,

4) представление надёжности голосования.

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

Для решения первой из задач представляется способ отображения nporot-версионной программы в рамках одного цикла выполнения задачи, если её вере

распределены по М (1 й М й N ) ЛЭ. Прогон программы отображается с помощью схемы (рис. 1). Предусмотрена возможность представления сбоев одновременно группы ПЭ, что может быть обусловлено для них такими едиными причинами как нарушения в общем питании, синхронизации. Такие сбои затронут функционирование 4 всех версий, выполняющихся параллельно на различных ПЭ, и только одной из числа выполняющихся последовательно, допустим, на одном ПЭ. Напротив, в целом, отказ ПЭ не даст возможности получить результаты всех версий, если они выполнялись на одном ПЭ, или только одной, если версии выполнялись на различных ПЭ. Следовательно, возможность представления таких сбоев целесообразно предусматривать для выбора варианта размещения версий, учитывающего критерий надёжности.

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

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

:

у.-

ш

Объект модел|

./¿■количество версий на 1-оиПЭ.'Л+...+Д+...+]и "К

Схема представления прогона программы в воде графа, где:

В; - начало выполнения вычислительным элементом I размещенных на нем версий, Ал (кг/ - штрихи введены для уникального обозначения вершин)- по результатам выполнения г версий на ¿-ом вычислительном элементе А из них дали правильные результаты, ц - вероятность отказа ПЭ за время выполнения версии, р - вероятность, что версия откажет или во время ее выполнения Будет сбой ПЭ, Чн - вероятность «

отказа ПЭ в текущем цикле, но до начала выполнения версий £

модель представления надежности голосования;

.....ша:

моделирование длительности отказов версий

модель надежное!

Рис. 1. Обобщенная схема представления надежности при прогоне N - веосианной ппотяими ил м пиппогляпии.«

члаилитч«

I

и

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

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

Пусть вероятности отказа многоверсионной программы, состоящей из и версий (из первоначальных N версий после отказов ПЭ остаётся и, 1 й и £ N), на интервале времени ( задана функция Фи0).

Для случая выполнения каждой версии на отдельном ПЭ, не предусматривающего замены отказавших ПЭ, положив, что функция распределения (ФР) времени до отказа первого из N процессорных- (г), время до следующего отказа имеет ФР С?2 (') • время между (Н)-м и ]-м отказами ПЭ Оу (<). предлагаемую методику

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

Ф^О), если 1=0 \

0

1 /-/1

А('Н/(*Л<<1>+ 1<ф//-1('2 ('-'1 ~<2 )№('2 ))сЮ\ (<!), если 1=2

О О

1-11 '-'2-/1 '-'I-...-//_!

/(«М'0+ I (Ф/\М('2)+ [ «.+

0 0 О О

хЛЗ1/ (// (//_|)).. .)<Й/1 (х 1), для 1=3,N-1 (I)

Поскольку вероятность отказа высоконадежной системы на интервале есть малая величина, полагается возможным Фи(0< Р вычислять как среднее количество отказов.

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

Для оценки Р при допущении о неограниченном количестве резерва ПЭ достаточно при построении модели воспользоваться вышеупомянутыми методиками, разработанными для задач 1 и 2. Подобная оценка применима и для такого количества ПЭ для замены, вероятность отказа которого значительно меньше Р.

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

На основа />/ получена формула надёжности медианного голосования. Медианное голосование упорядочивает результаты версий и выбирает серединный, и при допущении о нулевом значении медианы случайной величины ошибки результата отхаэавшей версии справедлива формула

N-1-1 2И~*~Х

ЛМ-1 __1

u

где N £ 3 - начётное количество версий.

Для построения комплексных моделей на основе разработанных инструментальных средств следует использовать подходящие модель надёжности ПЭ (определяет интенсивность/вероятность отказов и сбоев ПЭ) и модель отказов версий (определяет на основе статистических данных отладки версий интенсивности отказов или вероятности отказа за один прогон).

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

На основе построения моделей прогона программы получено граничное условие определения предпочтительности размещения версий на одном ПЭ или каждой версии на отдельном по критерию надёжности при учёте возможности сбоев различных ПЭ, вызываемых общими причинами: версии целесообразно размещать на одном ПЭ, если qKPf^-Pftj', где q - вероятность отказа ПЭ за время выполнения

версии, Phf - вероятность того, что за время выполнения версии произойдёт сбой выполняющего её ПЭ, Pf,f' -условная вероятность сбоя ПЭ за время прогона версии при условии, если на другом процессорном элементе за то же время сбой произошёл, иначе целесообразно размещение каждой версии на отдельном ПЭ.

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

Система моделей реализована программно в среде системы Maple.

Разработана математическая модель надёжности голосования, выбор результата которым основывается на итогах отдельных проверок - «проверочных признаках» (ПП). Пусть - вероятность, что в результате одного прогона версии N-

еерсионной программы находятся в состоянии X, где для разрядов двоичного

(0, если версия i не отказала представления X справедливо • ,

к н г « '(Ьесли версия I отказала '

г XY ~ Ученая вероятность (априорная), что система признаков примет состояние ¥, если версии находятся в состоянии X, где для разрядов двоичного представления Y справедливо

{О, если признак с номером w свидетельствует об отсутствии отказа I, если отказала хотя бы одна из контролируемых признаком версий

Фактически алгоритм голосования с ПП реализует зависимость /»(У) номера версии, результат которой выбирается в качестве результата программы. Вычислив Рх и ZXY на основе модели отказов версий и оценок вероятностей ошибок первого и второго рода для ПП, вероятность отказа программы за один прогон Рс вычисляем по формуле

2w-\ П-1

гс=Ра + 2 2 xn(ryPX-zXY (3)

" У=0 X=1 v '

N

где ii=2 -1. Полученная формула позволяет оценивать надёжность программы при голосовании с ПП, принимая в расчёт вероятности ошибок различных признаков и надёжность отдельных версий. Показана также возможность расчёта вероятностей ру для голосования на основе ПП.

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

2

max I.xnPX2XY W

" Jf=l

(по формуле может быть рассчитана табличная зависимость п(У)). Алгоритм голосования, построенный на основе такого соотношения обеспечивает максимально правдоподобный (на основе формулы Байеса) выбор результата многоверсион-ной программы.

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

Для сравнения рассмотрена возможность расчёта надёжности решения задачи на интервале Т как суммы вероятности отказа программы за время Т и вероятности отказа процессорных элементов за время Т. Сравнительные расчёты для варианта без реконфигурации показывают, что такая приближённая оценка может отличаться от предлагаемой оценки, учитывающей последовательность отказов во времени, в 7 и более раз, это подтверждает необходимость комплексного рассмотрения надёжности программы и аппаратуры в условиях, когда отказоустойчивая программа может быть толерантна к отказам, сбоям аппаратуры. Кроме того, оценка Р, получаемая при учёте длительностей нахождения версий в состоянии отказа может быть на 2-3 порядка точнее приближённых оценок без учёта таких длительностей На основании системы моделей рассчитана система графических зависимостей для совокупности рассмотренных вариантов (комбинаций значений факторов) для сравнения и оценки надёжности.

Проведено сравнительное исследование алгоритмов голосования по критерию надёжности. Для этого использовались разработанный способ представления надёжности голосования, модели надёжности голосования. В частности рассмотрено множественное (plurality) голосование, вывод о предпочтительности которого можно встретить в литературе. К основным рекомендациям по выбору алгоритма голосования по итогам сравнения и анализа алгоритмов можно отнести следующие: - если нельзя ожидать точного или приближённого равенства правильных результатов версий, то следует использовать медианное голосование

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

- если создаётся трёхверсионная программа, вероятности отказа версий о личаются не более чем в 2 раза, то предпочтительно медианное голосован

- для количества версий 5 и более, а также если вероятности отказа вера-отличаются более чем в 2 раза следует применять полученный в данной р боте алгоритм на основе формулы 4.

- если необходимо повысить надёжность голосования, то для алгоритма т формуле 4 возможно увеличить количество проверок результатов версий; среди таких проверок могут быть, в частности, контроль гладкости изменен значений квазинепрерывных переменных, сравнение результата версии с ожидаемым диапазоном значений, сравнение результатов пары версий и {. гиа

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

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

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

По результатам проделанной работы можно сформулировать следующие выводы:

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

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

3. Разработана система аналитических моделей, отражающая сочетания обеспечивающих различную степень отказоустойчивости и надёжности факторов: размещения версий по процессорным элементам, количества резерва процессорных элементов, метод голосования, допустимость/недопустимость кратковременных отказов. Модели предназначены для выбора варианта организации вычислений и расчёта соответствующей надёжности. Система моделей представляет собой реализацию разработанной методики построения моделей для выбранного случая -трёхверсионной программы. Для равнения вариантов и для выбора предпочтительного варианта получена система графических зависимостей.

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

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

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

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

8. Практическая ценность результатов работы подтверждена актами о внедрении на ГНПО 'Агат* и АОЗТ МО ПНИЭИ.

Публикации

Содержание диссертации отражено в следующих печатных работах:

1. Иыуду К. А, Рыбников Д. Л. Повышение достоверности работы версионной программной системы. - Тезисы докладов 4-й всероссийской конфер-ции "Качество информации*. -М.: МИИТ, 1994. с. 13.

2. Иыуду К. А, Рыбников Д. Л. Алгоритмы решающего органа при И-версио ном программировании. "Методы и средства оценки и повышения надёжности пр боров, устройств и систем"/ Тезисы докл. международной научно-технической ко* Под ред. А. М. Тартаковского, А В. Блинова. -Пенза : Изд-во Пенз. гос. техн. ун-тг 1995. с. 64-66.

3. Иыуду К. А., Рыбников Д. Л. Решающие правила для М-версионных программ. - Надёжность и контроль качества. -1995. - N 7., стр. 19-29.

4. Рыбников Д. Л. Моделирование Ы-версионной программы с учётом над6: ности выполняющих её процессоров. "Актуальные проблемы анализа и обеспече надёжности и качества приборов, устройств и систем'/Сб. докл. науч. конф. - Под ред. А М. Тартаковского, А В. Блинова. - Ч. 1. Пенза: 1996. с. 96-97.

5. Иыуду К. А., Рыбников Д. Л. О возможности автоматического генерирова версий и голосовании для М-версионных программ. - М.: МАИ, 1996. -12 с. - Деп, ВИНИТИ-30.12.96, №3835-В96.

6. Рыбников Д. Л. К вопросу об анализе отказоустойчивости М-версионных программ многокомпьютерных вычислительных систем. - М.: МАИ, 1996. -5с.-/] В ВИНИТИ - 30.12.96, №3836-В96.