автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Герт-анализ мультиверсионных программных архитектур информационно-управляющих систем

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

Ковалев Павел Владимирович

ГЕРТ-АНАЛИЗ МУЛЬТИВЕРСИОННЫХ ПРОГРАММНЫХ АРХИТЕКТУР ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

05.13.01 - Системный анализ, управление и обработка информации (космические и информационные технологии) 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

904606888

Красноярск - 2010

004606888

Работа выполнена в ФГОУ ВПО «Сибирский федеральный университет», г. Красноярск

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

доцент

Попов Алексей Михайлович

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

доцент

Ступина Алена Александровна

кандидат технических наук, доцент

Зеленков Павел Викторович

Ведущая организация:

Томский государственный университет систем управления и радиоэлектроники

Защита диссертации состоится <ь£» июля 2010 г. в 14 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М. Ф. Решетнева по адресу: 660014, г. Красноярск, проспект имени газеты «Красноярский рабочий», 31, ауд. П-207.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева по адресу: 660014, г. Красноярск, проспект имени газеты «Красноярский рабочий», 31.

Автореферат разослан « I » июня 2010 г.

Ученый секрете диссертационнс

Е. П. Моргунов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

Целью исследования является повышение эффективности анализа вероятностно-временных характеристик функционирования

мультиверсионных программных архитектур информационно-управляющих систем.

Задачи исследования:

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

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

- Разработать алгоритм преобразования ГЕРТ-сети к эквивалентному виду с учетом особенностей функционирования и реализации мультиверсионного программного обеспечения информационно-управляющих систем.

- Реализовать различные способы применения методологии мультиверсий в виде базовых ГЕРТ-сетевых моделей.

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

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

Новые научные результаты, полученные лично автором

1. Впервые разработана методика ГЕРТ-сетевого описания программного обеспечения, построенного на основе мультиверсионной архитектуры.

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

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

Научная новизна результатов работы

1. Предложенная методика позволяет описать программное обеспечение, построенное на базе мультивсрсионной архитектуры, в виде ГЕРТ-сети, чтобы учесть особенности вероятностного функционирования и реализации мультиверсионных программных средств, обеспечивая как гибкость, так и универсальность данной методики.

2. Впервые в рамках алгоритма преобразования ГЕРТ-сети, предложенного в работе, реализован новый способ представления мультиверсионных участков сети путем использования для таких участков эквивалентных преобразований. Это обеспечивает для полученной эквивалентной ГЕРТ-сети возможность применения математического аппарата классических ГЕРТ-сетей.

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

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

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

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

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

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

Достоверность полученных результатов подтверждается тестированием и оценкой результатов разработанной ГЕРТ-системы анализа вероятностно-временных характеристик мультиверсионного ПО, а также согласованностью расчетных и экспериментальных данных,

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

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

Публикации. По теме диссертации опубликовано 14 печатных работ, из них 3 статьи в журналах из Перечня ВАК РФ. Полный список публикаций представлен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы общим объемом 125 с. и приложения объемом 30 с. Список использованной литературы содержит 302 наименования.

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

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

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

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

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

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

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

Проблемы оценки качества информации и надежности аппаратных и программных средств рассматриваются в трудах Байхельта Ф., Герасименко В. А., Липаева В.В., Ляпунова A.A., Майерса Г., Ушакова И.А., Франкена П., Ясина Е.Г. и других ученых. В настоящее время при оценке вероятностно-временных характеристик ПО информационно-управляющих систем применяется ряд специализированных методов и технологий, ориентированных на различные приложения программных средств, в частности, сети Петри и их модификации. Для общей оценки вероятности успешного завершения работы ПО некоторые исследователи предлагают применять модель последовательности испытаний Бернулли. Для исследования систем, содержащих узлы с не гарантированной надежностью, применяются, как правило, Марковские цепи.

Одним из методов, обладающим универсальностью, является ГЕРТ-сетевой анализ вероятностно временных характеристик функционирования ПО на основе универсальной ГЕРТ-узловой логики. Использование ГЕРТ-сетей для анализа характеристик программного обеспечения информационно управляющих систем, построенного на основе мультиверсионной архитектуры, позволяет учесть особенности функционирования и реализации мультиверсионной архитектуры. Использование универсальной ГЕРТ-узловой логики обеспечивает как гибкость, так и универсальность данной методики, позволяя решить задачу методами .классических ГЕРТ-сетей или при необходимости перейти к решению задачи на основе Марковских цепей или сетей Петри.

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

Во второй главе представлен математический аппарат классических ГЕРТ-сетей, а также ГЕРТ-подобная узловая логика.

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

Для стохастической ГЕРТ-сети весом дуги </, /> является вектор \р,„ 1?у\, гдеру -вероятность выполнения дуги </,_/> при условии активации узла г, а Ру - функция распределения времени выполнения дуги </,/>.

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

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

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

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

Рассмотрим виды входных функций:

1. АЖ-функция - узел активируется, если выполнены все дуги, входящие в него.

2. ЮИ-функция - узел активируется, если выполнена любая дуга, входящая в него.

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

Рассмотрим виды выходных функций:

1. Детерминированная функция - все дуги, выходящие из узла, выполняются, если узел активирован.

2. Стохастическая функция - ровно одгга дуга, выходящая из узла, выполняется с заданной вероятностью, если узел активирован.

|/ - Е011- / - ЮИ- г - АШ-^ вход, вход, вход,

\ - стохастический - детерминированный / выход, выход.

Рис. 1. Графическое обозначение входных и выходных функций ГЕРТ-сети

Комбинируя все входные и выходные функции (рис. 1), получаем шесть различных типов узлов.

Таким образом, ГЕРТ-сеть - это сеть с источниками Я и стоками 5 вида «работа на дуге», в которой каждый узел принадлежит одному из шести типов узлов, для каждой дуги <г, /> определен вес вида [р,р /%,] с вышеуказанным значением и задано начальное распределение источников сети.

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

Рассмотрим сеть Л) содержащую только ГЕРТ-узлы, которые образуют множество N. Пусть время выполнения операции (I, ]) есть случайная величина Тц. По определению операция (7, может быть выполнена только в том случае, если выполнен узел. Поэтому для изучения вопросов, связанных с выполнением этой операции, необходимо знать вероятность (в дискретном случае) или плотность распределения (в непрерывном случае) случайной величины Ту при условии, что узел г выполнен. Это в свою очередь позволит провести исследования, связанные с выполнением всей сети. В частности, станет возможным определить моменты распределения времени выполнения сети, с помощью которых будут вычислены математическое ожидание и дисперсия времени выполнения сети.

Пусть /у— условная вероятность или плотность распределения времени выполнения операции (7, ]). Условная производящая функция моментов случайной величины У,-, определяется как = ]= е54.

Пусть ру — вероятность того, что операция (г, ]) будет выполнена при условии, что узел г выполнен. Для случайной величины Уи определим функцию как

= (1)

С помощью преобразования (1) всегда можно определить сеть б, структура которой идентична структуре сети С, только вместо двух

параметров дуг ру и у(1- присутствует один параметр }Уц ф - |ф

А Б

Рис. 2. Сети йя С.

А - элемент сети С; Б — элемент сети С'.

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

Если времена выполнения операций сети (7 представляются независимыми случайными величинами, то С обладает рядом свойств, представляющих интерес с точки зрения применения в рамках анализа вероятностно-временных характеристик мультиверсионных архитектур программного обеспечения.

Таким образом, для представления мультиверсионного ПО в виде ГЕРТ-сети необходимо последовательно выполнить следующие шаги.

1. Представить мультиверсионное ПО в виде стохастической сети с ГЕРТ-узлами.

2. Провести эквивалентные преобразования для участков полученной ГЕРТ-сети, которые содержат мультиверсионные модули.

3. Для каждой дуги определить условную вероятность и производящую функцию моментов.

4. Для каждой дуги вычислить ^¡У-функцию.

5. Преобразовать сеть в эквивалентную сеть, состоящую из одной

ветви.

В данном разделе представлен аппарат универсальной ГЕРТ-подобной узловой логики. Использование логики работы узлов ГЕРТ-сети позволяет, при необходимости, преобразовать ГЕРТ-сеть или в сети Петри и воспользоваться соответствующими методиками расчета, или перейти к Марковским цепям. Тот или иной переход зависит от архитектуры программного обеспечения информационно управляющей системы, которая описывается I НРТ сетью. Преимущество ГЕРТ-сетевого описания ПО ИУС заключается в том, что вероятностно-временные характеристики программного обеспечения могут быть получены с помощью математического аппарата классических ГЕРТ-сетей без дополнительных преобразований. Чтобы представить модель введем следующие обозначения: пусть (7 - сетевая модель с источниками и стоками (действия, соответствующие операциям процесса, представляются дугами), где множество узлов обозначается N, а множество дуг - А. Предположим, что (! имеет только один исток, который обозначается через г и соответствует началу рассматриваемого процесса.

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

Определение (1) Сетевую модель - только с одним истоком и

со стоками назовем сетью для планирования/решения, если каждый узел г из в определен через входную характеристику Х~ 6 ОД,..., |Р(01 и выходную характеристику X* е 0Д,...,|5(01 где множество узлов обозначается ТУ, а множество дуг - А\ \Р(0\, |5"(;)|- мощность множества предшественников и

последователей узлов i соответственно. Эти характеристики, формирующие узловую логику, имеют следующие значения:

(1а)-узел активируется сразу же, как только входные действия Х[' завершаются;

(16) - как только узел i активирован, то не более Xf выходных действий начинает выполняться, если узел i не активируется, то ни одно выходное действие не выполняется.

Иногда уместно заменить термин "не более" на "точно". Два условия из Определения (1) подразумевают, что каждое действие выполняется сразу, как только это становится возможно.

Для источника г полагаем Х[ = 0, т.е. он всегда активирован. Кроме того, X* = 0 для ies , где S - множество стоков G.

Нужно отметить, что, во-первых , если Х[ = 1, тогда узел i имеет OR-вход, и, если Xf 6 |P(i)|, то тогда i имеет AND-вход. И если "не более" заменяется на "точно" в (16), то Х* = 1 соответствует вероятностному выходу, а Х^ = |S(i)l соответствует детерминированному выходу. Во-вторых, если данная сеть G для решения имеет множество источников R (\R\>1) и множество R' с R, R1 ф 0 активизируется в начале выполнения процесса, то можно формально перевести G в соответствующую одноистоковуто сеть следующим образом. Введем новый единый источник г0 и для каждого i е R введем вспомогательную дугу (г0, i). Кроме того, установим Х~0 - = 0. Определим „_ _ f 0 для i е R' 1 ~ I 1ДЛЯ1 е R/R' Введем дуговые переменные ((ij> е Е ):

(1,если (i,j) выполняется;

w< / - п

,J ( 0, иначе;

и узловые переменные (t е V):

_ (1, если i активируется; l,i ~ 1 0, иначе;

где ur = 1, т.е. источник всегда активируется.

Тогда два условия узловой логики, введенные в Определении (1) могут быть переписаны в следующем вид

lkep(.i)Wki>^i i е V/{r], (5)

ЕкЕПО Wki < х'г + MiUi ' ®

где М( > |Р(01 ~Х[Л б V/{r],

Y.jes(i)wij S Xfui i e V/S. (7)

Если в (5) щ - 1, то это значит, что в результате активации узла i выполняется, по крайней мере, Х{ входящих воздействий. Если ц :: 0 и (б), то это значит, что узел i не активирован, так как менее чем X* входящих действий выполнено. Таким образом, оба эти неравенства вместе соответствуют (1а).

Определение (2) Каждая реализация процесса (или реализация сетевой модели) может быть соотнесена с множеством выполняемых действий сети или с функцией w-.E -»{ОД}; (<ij) е Е), значения которой задаются как

,,. ... (1, если (1,1) выполняется;

w((l,/)) == w¡ ■ = < - „ " 1,1 ( 0, иначе.

С другой стороны, если некоторая реализация сети уу задана, то, как узловые, так и дуговые переменные для этого случая также специфицированы. Будем говорить о допустимой реализации, если м> удовлетворяет условиям узловой логики. Тогда

е" = {и/: Е -> {ОД}; |\Уу - удовлетворяет (5) - (7); ({,}) е Е), е* - множество всех допустимых реализаций.

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

В третьей главе представлены модели ГЕРТ-сетей, описывающие различные способы применения методологии мультиверсий.

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

Используя методику преобразования ПО с мультиверсиовной архитектурой в ГЕРТ-сетевое представление, рассмотрим различные варианты применения методологии мультиверсий.

]. 1^-версионное программирование - это мультиверсионная методика, в которой все версии разработаны в соответствии с идентичными основными требованиями, а решение о правильности вывода основано на сравнении всех выводов (см. рис. 6).

Рис. 6. Модель ]\1-всрсионного программирования Альтернативная

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

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

Рассмотрим расчет сети, описывающей мультиверсионную архитектуру ПО и содержащей ЮК вход и детерминированный выход (рис. 8), состоящей из нескольких подсетей (рис. 9).

Рис. 8. КЖ-вход

с 1-т \

V /

Рис. 9. Произвольная подсеть с начальным узлом / и конечным узлом т

Необходимо учитывать, что / - вычисляемый 1СЖ-вход, имеющий стохастическое начало в узле /. {¡¡-т/}, {1гт2}, ..., {/\-w.v} - N непересекающихся подсетей.

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

Также следует учесть, что время работы N модулей будет не больше времени работы ?тах, где 1тт — максимальное время работы мультиверсионного модуля входящего в набор N.

Пусть Ру — вероятность того, что операция (г, у) будет выполнена при условии, что узел /' выполнен и Р],(1) - функция вероятности распределения времени выполнения работы (/,у) тогда имеем:

Р] = А • I! - 0 - ) ■ 0 ~ Рп.т1*)ш - • 0 - р!н,тык ) 3 , (8)

(9)

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

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

Альтернативная версия

Восстапоптепис \ ... /

И! контрольной \ / Присмо'шый гест Ммход

'1 очки \ • /

N

Рис. 10. Модель блока восстановления в виде ГЕРТ сети

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

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

Используя необходимое и достаточное условие функционирования мультиверсионного модуля проведем эквивалентные преобразования, которые упростят ГЕРТ-сеть, представленную на рисунке 11 б. После чего, воспользовавшись топологическим уравнением Мейсона для замкнутых потоковых графов, вычислим вероятность успешного завершения сети, математическое ожидание и стандартное отклонение.

а. б.

Рис, 11. Графическая постановка задачи: а - стохастическая схема процесса

б- ГЕРТ сеть

Результаты, полученные при помощи построенной модели работы системы, представлены в таблице 1.

Таблица 1. Результаты расчета ГЕРТ-ссти

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

РК/ БРК Подключение Тест Запуск Р (мин.) о, (мин.)

БРК 3 3 3 0.7755 13.3844 3.2148

БРК . " •■■ Ь 3 3 .....0.7756 --v •■.■ ■ 13.3859 ... 3.2177

БРК 9 -3 ' 3 0.7756 13.3862 : 3.2184

БРК 12 3 ■ 3 - • 0.7757 : . 13.3867 3.2193

БРК 15 3 3 0.7757 13.3871 v 3.2200

БРК 18 3 3 . 0.7757. . . 13.3875 . 3.2207

БРК 3 6 3 0.7778 13.3938 3.2234

БРК 3- 9 3 - 0.7790 13.3986 - 3 2278

БРК 3 12 3 0 7796 Г 13.4011 3.2300

ПЗРК 3 - 15 3 "0.7800 13.4024 3.2312

;БРК 3 18 3 0.7801 13.4030 . 3.2318

БРК - '3 L'3 • -6 0.&816 -■^.'Ь.4130 • - '*3 2776

БРК 3 - 3 0 9361 - ' 13,4277 3 3095 1

БРК" 3 ... 3 (19fi41 f „13.4353" * ,3.3258 '

ъж ; , 3 jy " 0.9784 " 13..43У2' .3.3341., \

ЬРК * 3- '.■0 9858 13-4411 3.-33S3 -

■ PK: . з ••■•■ 3 3 0.7512 17.0731. 4.5273

PK 6 3 3 0.7537 17.0761 4.5317 :

PK 9 ■ '3 |~3 •■•■ 0.7550 17.0776 4.5340

PK 12 3 •. 3 0.7557 17.0783 ■-. 4.5352:

PK: 15 3 3 ,■■• 0.7560 17.0787 4.5358

PK 18 3 3 0.7562 17.0789 4.5361

PK 3 6 3- - 0.7537 17.0867 4.5400

-PK 3 9 - 3- 0.7551 - 17.0937 4.5465

PK"1 - 3 12 3 0.7558 - 17.0972 4.5498 -

PK 3 15- 3 0.7561 17.0991 4.5515

PK • 3 18 3 - 0.7563 - 17.1000 " 4.5524

PK'- ~ : - 3 " *: 6-- б 8637 17.2213- -4,7442.

¡PK ~ 3 ! 3 - 9 -. 0.9224 ' ' , 17 2988 4,8555

PK - , 3 - - * . 3 12; . 0.9589 - '17.3384 4 9126"-

- PK- ■ 3" - -3-V - 16*" '/'0-9685 ■ = • 17.3595 .-.-LWIS""7""!

3: - 18 " 0,9765,1 - - . 17,3702 1 -»9568

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

межпроцессных взаимодействий с увеличением числа модулей.

Количество мультиверсий (шх)

Рис. 12. Зависимость вероятности успешного завершения системы от количества мультиверсий

Количество мультиверсий (шт )

Рис. 13. Зависимость среднего времени работы системы от количества мультиверсий

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

Результаты расчета моделей ПО ИУС, построенные при помощи ГЕРТ-сетей, согласуются с экспериментальными результатами, полученными с помощью имитационной модели среды исполнения мультиверсионных программных модулей, апредложенный в работе алгоритм вычисления вероятностно-временых характеристик ПО ИУС является более эффективным по сравнению с известными алгоритмами,

исходя из критерия вычислительной сложности.

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

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

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

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

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

Публикации в изданиях, рекомендованных ВАК РФ:

1. Ковалёв, П.В. Определение надежности мультиверсионного программного обеспечения с использованием методов анализа сетей / П.В. Ковалёв, А. Н. Лайков, С. Н. Гриценко // Вестник СибГАУ. Вып. 1(22) в 2 частях. - Красноярск, 2009. Часть 2. - С. 55-60.

2. Ковалёв, П.В. К вопросу формирования мультиверсионного программного обеспечения с учетом ресурсных ограничений / П.В. Ковалёв, И.А. Капчинский, А.Н. Лайков, С.Н. Гриценко // Вестник СибГАУ. Вып.2(23). - Красноярск, 2009. - С. 70-74.

3. Ковалёв, П.В. Графоаналитический метод анализа мультиверсионных архитектур программного обеспечения / П.В. Ковалев, И.А. Капчинский, С.Н. Гриценко // Вестник СибГАУ. Вып.3(24). - Красноярск , 2009. - С. 3739.

Публикации в других изданиях:

4. Ковалёв, П.В. Перспективы и проблемы практической реализации имитационной модели среды исполнения мультиверсионных программных модулей / П.В. Ковалёв // Вестник университетского комплекса: Сб. научн. тр. - Вып. 8(22). - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2006. - С. 158-163.

5. Ковалёв, П.В. Практическая реализация среды исполнения мультиверсионных программных модулей / П.В. Ковалёв, В.В. Лавригцев // Вестник университетского комплекса: Сб. научн. тр. - Вып. 8(22). -Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2006.- С. 168-188.

6. Ковалёв, П.В. Методы оценки временных характеристик мультиверсионного программного обеспечения как высоконадежной системы обработки информации / П.В. Ковалёв // Вестник университетского комплекса: Сб. научн. тр. - Вып. 10(24). - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2007.- С. 48-51.

7. Ковалёв, П.В. Методика определения времени работы алгоритмов и программ с помощью ГЕРТ сетей / П.В. Ковалёв // Вестник университетского комплекса: Сб. научн. гр. - Вып. 10(24). - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2007,- С. 65-68,

8. Ковалёв, I1.B. Анализ возможности практической реализации мультиверсионного ПО на платформе .NET сетей / П.В. Ковалёв // Вестник университетского комплекса: Сб. научн. тр. - Вып. 10(24). - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2007.- С. 68-71.

9. Ковалёв, П.В. Определение надежности мультиверсионного программного обеспечения с использованием ГЕРТ-сетей / П.В. Ковалёв, A.M. Попов // Вестник университетского комплекса: Сб. научн. тр. - Вып. 12(26). - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2008.- С. 125-137.

Ю.Ковалёв, П.В. Графоаналитический метод анализа

мультиверсионных архитектур программного обеспечения. // Журнал "Международный журнал прикладных и фундаментальных исследований". №6, 2009. - С.70.

11. Ковалёв, П.В. Определение надежности мультиверсионного программного обеспечения с использованием методов анализа сетей. // Журнал "Международный журнал прикладных и фундаментальных исследований". №6, 2009. - С. 39-40.

12. Ковалёв, П.В. ГЕРТ-сетевой анализ мультиверсионных архитектур программного обеспечения / П.В. Ковалёв // Журнал "Успехи современного естествознания" №9, 2009,- С. 161-164.

Разработки, зарегистрированные в «Объединенном фонде электронных ресурсов «Наука и образование»»:

13. Ковалёв, П.В. Среда исследования вероятностно-временных характеристик ГЕРТ-сетей. М.: ВНТИЦ, 2009. - Per. № 15106.

14. Ковалёв, П.В. Среда исполнения мультиверсионных программных модулей. М.: ВНТИЦ, 2009. - Per. № 15105.

КОВАЛЕВ Павел Владимирович

ГЕРТ-анализ мультиверсионных программных архитектур информационно-управляющих систем

Автореферат диссертации

Подписано в печать 25.05.2010. Заказ № Формат 60x84/16. Усл. печ. л. 1. Тираж 100 экз. Отпечатано в СибГАУ, 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий»

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

1. ПРОБЛЕМЫ ОЦЕНКИ ВЕРОЯТНОСТНО-ВРЕМЕННЫХ ХАРАКТЕРИСТИК ВЫСОКОНАДЕЖНЫХ ПРОГРАММНО-ИНФОРМАЦИОННЫХ СИСТЕМ.

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

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

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

1.4. Моделирование при помощи сетей Петри и их расширений.

1.5. Марковские цепи и стохастические сети.

1.6. Различные подходы к оценке вероятностно-временных характеристик информационно управляющих систем.

1.7. Выводы.

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СТОХАСТИЧЕСКОЙ ГЕРТ-СЕТИ.

2.1. Математическая модель ГЕРТ-сети.

2.1.1. Основные термины и обозначения.

2.1.2. Стохастическая ГЕРТ-сеть.

2.1.3. Структурные ограничения ГЕРТ-сети.

2.1.4. Методы расчета ГЕРТ-сети.

2.2. Методика представления мультиверсионного программного обеспечения в виде ГЕРТ-сети.

2.3. Алгоритм расчета ГЕРТ-сети описывающей мультиверсионные архитектуры программного обеспечения.

2.4. Выводы.

3. МОДЕЛИ ГЕРТ-СЕТЕЙ, ОПИСЫВАЮЩИЕ РАЗЛИЧНЫЕ СПОСОБЫ ПРИМЕНЕНИЯ МЕТОДОЛОГИИ МУЛЬТИВЕРСИЙ.

3.1. Необходимое и достаточное условие функционирования мультиверсионного модуля.

3.2. Применения методологии мультиверсий в виде базовых ГЕРТ-сетевых моделей.

3.2.1. N-версионное программирование.

3.2.2. Блоки восстановления.

3.2.3. N-версиониое программирование с самоконтролем.

3.2.4. N-версионное программирование с самоконтролем использующее сравнение

3.2.5. Блоки восстановления с согласованием.

3.3. Выводы.

4. АНАЛИЗ ВЕРОЯТНОСТНО-ВРЕМЕННЫХ ХАРАКТЕРИСТИК МУЛЬТИВЕРСИОННЫХ АРХИТЕКТУР ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРИ ПОМОЩИ ГЕРТ-СЕТЕЙ, С ИСПОЛЬЗОВАНИЕМ СРЕДЫ ПРОВЕДЕНИЯ ИССЛЕДОВАНИЙ GERTNETWORK.

4.1. Среда проведения исследований GERTNetwork.

4.2. Анализ вероятностно-временных характеристик мультиверсионных архитектур программного обеспечения при помощи ГЕРТ-сетей.

4.2.1. ГЕРТ-сети моделирующие режимы запуска задачи с резервным копированием и без него.

4.2.2. Результаты.

4.3. Выводы.

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

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

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

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

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

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

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

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

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

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

- Разработать алгоритм преобразования ГЕРТ-сети к эквивалентному виду с учетом особенностей функционирования и реализации мультиверсионного программного обеспечения информационно-управляющих систем.

- Реализовать различные способы применения методологии мультиверсий в виде базовых ГЕРТ-сетевых моделей.

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

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

Новые научные результаты, полученные лично автором

1. Впервые разработана методика ГЕРТ-сетевого описания программного обеспечения, построенного на основе мультиверсионной архитектуры.

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

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

Научная новизна результатов работы

1. Предложенная методика позволяет описать программное обеспечение, построенное на базе мультиверсионной архитектуры, в виде ГЕРТ-сети, чтобы учесть особенности вероятностного функционирования и реализации мультиверсионныхпрограммных средств, обеспечивая как гибкость, так и универсальность данной методики.

2. Впервые в рамках алгоритма преобразования ГЕРТ-сети, предложенного в работе, реализован новый способ представления мультиверсионных участков сети путем использования для таких участков эквивалентных преобразований. Это обеспечивает для полученной эквивалентной ГЕРТ-сети возможность применения математического аппарата классических ГЕРТ-сетей.

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

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

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 14печатных работ, из них 3 статьи в журналах их Перечня ВАК РФ. Полный список публикаций представлен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы общим объемом 125 с. иприложения объемом 30 с. Список использованной литературы содержит 102 наименования.

4.3.Выводы

1. Среда проведения исследований GERTNetwork:

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

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

- возможность экспорта полученных результатов и их последующего анализа;

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

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

Заключение

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

Создана новая методика ГЕРТ-сетевого описания программного обеспечения, которая позволяет описать программное обеспечение, построенное на базе мультиверсионной архитектуры, в виде ГЕРТ-сети, что позволяет учесть особенности функционирования и реализации мультиверсионной архитектуры, обеспечивая как гибкость, так и универсальность данной методики.

Разработан алгоритм преобразования ГЕРТ-сети, в котором реализован новый способ представления мультиверсионных участков сети путем использования для таких участков эквивалентных преобразований. Это обеспечивает для полученной эквивалентной ГЕРТ-сети возможность применения математического аппарата классических ГЕРТ-сетей.

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

1. Avizienis, A. On the implementation of N-version programming for software fault-tolerance during execution. / A. Avizienis, L. Chen. In Proc. IEEE COMPSAC 77, c. 149-155, ноябрь 1977.

2. Avizienis, A. Fault tolerance and fault intolerance: complementary approaches to reliable computing. / A. Avizienis. In Proc. 1975 International Conference on Reliable Software, c. 458-464, апрель 1975.

3. Avizienis, A. DEDIX 87 A supervisory system for design diversity experiments at UCLA. / A. Avizienis, M. R. Lyu, W. Schuetz, U. Voges. // In Digest of 18th FTCS, c. 129-168, Токио, Япония, июнь 1988.

4. Bazan, Peter, German, Reinhard. An iterative approximate analysis method for non-Markovian models based on supplementary variables. Proc. of in 12th

5. Condor Version 6.6.10 Manual / Condor Team, University of Wisconsin-Madison. — Режим доступа: http://www.cs.wisc.edu/condor/manual/v6.6/

6. Chen, J. Software Diversity and Its Implications in the N-version Software Life Cycle. / J. J. Chen. PhD dissertation, UCLA, Computer Science Department, 1990.

7. Elmendorf, W. Fault-tolerant programming. / W. R. Elmendorf. // In Digest of 2-nd FTCS, c. 79-83, Newton, MA, June 1972.

8. Foster, Ian. What is the Grid? A Three Point Checklist. Электронныйресурс. / Argonne National Laboratory &University of Chicago. July 20, 2002. — Режим доступа: http://www-fp.mcs.anl.gov/~foster/Articles/WhatIsTheGrid.pdf.

9. German, Reinhard. Non-Markovian Analysis. Lectures on Formal Methods and Performance Analysis, First EEF/Summer School on Trends in Computer Science. Heidelberg : Springer, 2001, (LNCS Bd. 2090), S. 156-182.

10. Kamthe, Ankur, Lee, Soo-Young. A Stochastic Approach to Estimating Earliest Start Times of Nodes for Scheduling DAGs on Heterogeneous Distributed Computing Systems. 19th IEEE International Parallel and Distributed Processing

11. Symposium (IPDPS'05) Workshop 1, 2005. p. 121b.— Режимдоступа: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2005.70

12. Litzkow, M., Livny, M., Mutka, M., Condor A Hunter of Idle Workstations, Proceedings of the 8th International Conference of Distributed Computing Systems, June 1988. — Режимдоступа: http://www.cs.wisc.edu/condor/doc/icdcsl988.pdf

13. Lyu, M. Software diversity metrics and measurements. / M. R. Lyu, J. H. Chen, A. Avizienis. In Proc. IEEE COMPSAC 1992, c. 69-78, Chicago, Illinois, сентябрь 1992.

14. Neumann, K. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization : Lecture Notes in Economics and Mathematical Systems. -Berlin : Springer-Verlag, 1990. ISBN 3-540-52664-1.

15. Pfister G. Sizing Up Parallel Architectures. DataBase Programming & Design OnLine. Электронныйресурс. May 1998.— Режимдоступа: http://www.dbpd.com/vault/9805feat.htm,http ://www. citforum.ru/hardware/articles/art5. shtml.

16. Raman, Rajesh. Matchmaking frameworks for distributed resource management. / A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Computer Sciences) at the University of

17. Wisconsin.— Madison, 2001.— Режимдоступа:http://www.cs.wisc.edu/condor/doc/rajesh.dissert.pdf

18. Thompson, W.J. Computing for scientists and engineers. — NY: John Wiley & Sons, Inc., 1992. — ISBN 0-471-54718-2.

19. Yuan, Shi. Reevaluating Amdahl's Law and Gustafson's Law (ABSTRACT). Электронныйресурс. / TempleUniversity. Computer and Information Sciences Department. — Philadelphia, 1996. — Режимдоступа: http://www.cis.temple.edu/~shi/docs/amdahI/amdahl.htm.

20. Авербах, Л.И., Воропаев, В.И., Гельруд Я.Д. Планирование работ проекта с учетом приведенной стоимости. Электронный ресурс. /

21. Публикации Российской Ассоциации Управления Проектами "СОВНЕТ", 2003. —Режим доступа: http://www.sovnet.ru/pages/casm5.rar

22. Аврамчук, Е.Ф., Вавилов, А.А., Емельянов, С.В. и др. Технология системного моделирования. —М.: Машиностроение; Берлин: Техник, 1988. — ISBN 5-217-00150-Х.

23. Андреев, А.Н., Воеводин, В.В. Методика измерения основных характеристик программно-аппаратной среды. / ВВС ДВО РАН. — Режим доступа: http://www.dvo.ru/bbc/benchmarks.html

24. Антамошкин А.Н.О быстродействии алгоритмовслучайного поиска. // Автоматика и вычислительная техника. Рига: Изд-во «Зинатне», 19875. с. 3844

25. Бахвалов, Н.С., Жидков, Н.П., Кобельков Г.М. Численные методы. — 3-е изд. — М.: Бином. Лаборатория знаний, 2004.— ISBN 5-94774-175-Х.— 636 с.

26. Букатов, А. А., Дацюк, В.Н., Жегуло, А.И. Программирование многопроцессорных вычислительных систем. — Ростов-на-Дону: ЦВВР, 2003. ISBN 5-94153-062-5.

27. Вентцель Е.С. Теория вероятностей. — 8-е изд., стер. — М.: Высш. шк., 2002, —575 с.

28. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. Учеб. пособие для втузов.— 2-е изд., стер.— М.: Высш. шк., 2000.—480 с.

29. Воеводин, В., Филамофитский, М. Суперкомпьютер на выходные. Электронный ресурс. // Открытые системы, № 05, 2003. — Режим доступа: http://www.osp.ru/os/2003/05/043.htm

30. Воропаев, В.И., Гельруд, Я.Д. Использование ЦАСМ при управлении проектами. Электронный ресурс. / Публикации Российской Ассоциации Управления Проектами "СОВНЕТ", 2001.— Режим доступа: http://www.sovnet.ru/pages/casm4.rar

31. Воропаев, В.И., Гельруд, Я.Д. Применение циклических альтернативных сетевых моделей при управлении проектами. Электронный ресурс. /

32. Публикации Российской Ассоциации Управления Проектами "СОВНЕТ", 2001. —Режим доступа: http://www.sovnet.ru/pages/casm3.rar

33. Давыдов, И.Н. Оптимизационные сетевые модели формирования циклических технологических процессов: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, САА, 2000.

34. Дегтерев А.С., Письман Д.М. GERT-сетевой анализ времени выполнения задачи на неспециализированном гетерогенном кластере. // Фундаментальные исследования. 2006, № 4. с. 79-80.

35. Дегтерев А.С., Письман Д.М. Оценка времени изготовления деталей на конвейере, допускающем устранение брака в процессе производства при помощи модифицированной ГЕРТ-сети. // Современные наукоёмкие технологии. 2006, № 7. с. 87-89.

36. Джиоева, Н.Н. Многокомпонентная сетевая модель формирования алгоритмов распределенной обработки и управления в АСУ: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, НИИ СУВПТ, 2004.

37. Доррер, Г.А. Методы анализа вычислительных систем: Учеб. пособие для студентов направления 552800 и специальности 220400 всех форм обучения. — Красноярск, СибГТУ, 2000 г.

38. Зализняк, В.Е. Основы научных вычислений. Введение в численные методы для физиков: Учеб. пособие для студентов естественно-научных и технических специальностей высших учебных заведений. — М.: Едиториал УРСС, 2002. — 296 с. : ил. — ISBN 5-354-00138-2.

39. Климанов В.П., Сутягин M.B., Быстрикова B.A. Кластеризация вычислительных систем и вопросы их катастрофоустойчивости // Автоматизация и управление в машиностроении. № 18, 2002.

40. Ковалев, И.В., Письман, Д.М., Сл обо дин, М.Ю. Модели оценки времени выполнения задачи на кластере с последовательной и параллельной архитектурой обмена данными. // Системы управления и информационные технологии. № 3 (20), 2005. с. 58-62.

41. Ковалев, И.В., Царев, Р.Ю. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах : учеб. пособие. Красноярск: ИПЦ КГТУ, 2004. — 111 с.

42. Коваленко, В.Н., Корягин, ДА. Организация ресурсов ГРИД. Электронный ресурс. — М., 2004. — Режим доступа: http://www.gridclub.ru/library/publication.2004-ll-29.9287628406/view.

43. Королюк, B.C., Турбин, А.Ф. Полумарковские процессы и их приложения. —Киев: Наукова думка, 1975. — 184 с.

44. Корячко, В. П., Шибанов, А. П., Шибанов, В. А. Численный метод нахождения закона распределения выходной величины GERT-сети. // Информационные технологии. 2001. № 7 — М.: Машиностроение, с. 16-21.

45. Котов В.Е. Сети Петри.— М.: Наука. Главная редакция физико-математической литературы, 1984.

46. Ларионов, А. М., Майоров, С.А., Новиков, Г. И. Вычислительные комплексы, системы и сети. Л.: ЭНЕРГОАТОМИЗДАТ, 1987.

47. РАН В. А. Сойфера. Самара, 2004.с. 181-185.— Режим доступа: http://www.ipsi.smr.ru/hpc-2004/tezisy.pdf

48. Майерс, Г. Надежность программного обеспечения: Пер. с англ. Галимова Ю. Ю. / Г. Майерс, В. Ш. Кауфман. М.: Мир, 1980. - 360 с.

49. Письман Д.М. Анализ временных параметров сетевых моделей на базе модифицированной ГЕРТ-сети. // Проблемы машиностроения и автоматизации. 2006, № I.e. 18-26.

50. Письман Д.М. Использование стохастически заданного параметра времени выполнения работ в МКП и ПЕРТ и расчет данных сетей при помощи модифицированных ГЕРТ-сетей. // Фундаментальные исследования. 2006, № 2. с. 44-45.

51. Письман Д.М. Сравнение производительности прямого и обратного алгоритмов расчета модифицированной ГЕРТ-сети. // Фундаментальные исследования. 2006, № 2. с. 45-47.

52. Письман Д.М., Слободин М.Ю. Оценка вероятности завершения расчетов задачи в условиях ограниченности времени для вычислительного кластера Condor при помощи модифицированной ГЕРТ-сети. // Современные наукоёмкие технологии. 2005, № 8. с. 30-31.

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

54. Материалы Международного научно-практического семинара / Под ред. проф. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2001. с. 141-149.— Режим доступа:http://www.software.unn.ac.ru/ccam/files/Seminar/Seminarl.pdf

55. Предсказатель производительности DVM-программ (Предиктор). Руководство пользователя. Июнь, 2000 г. Электронный ресурс. — Режим доступа: http://www.kiam.ru/dvm/dvmhtmll07/rus/usr/predictor/predUGr.html

56. Родин, А.В., Бурцев, B.JI. Классификации распределенных систем? Электронный ресурс. / Московский инженерно-физический институт (государственный университет). — Режим доступа: http://www.gridclub.ru/library/publication.2006-02-07.3586958006/view

57. Ступина, А.А., Письман Д.М., Кожевников С.В. Анализ временных параметров сетевых моделей на базе модифицированной ГЕРТ-сети. // Проблемы машиностроения и автоматизации —М.: Наука, 2006. с. 55-62.

58. Трохов, Н.Н. Оптимизация технологи управления опасными производствами: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, НИИ СУВПТ, 2002.

59. Филлипс, Д., Гарсиа-Диас, А. Методы анализа сетей. — М.: Мир, 1984.

60. Царев, Р.Ю. Семенько Т.И., Гаврилов Е.С. Модели формирования и алгоритмы распределенной обработки информации и управления : учеб. пособие. Красноярск: ИПЦ КГТУ, 2005. 240 с.

61. Шибанов, А.П. Нахождение закона распределения выходной величины GERT-сети большой размерности. // Информационные технологии. 2002. № 1 —М.: Машиностроение.

62. Шибанов А.П. Нахождение плотности распределения времени исполнения GERT-сети на основе эквивалентных упрощающих преобразований // Автоматика и телемеханика, 2003. № 2. С. 117-126.

63. Шнитман, В. Современные высокопроизводительные компьютеры. Электронный ресурс. / Информационно-аналитические материалы Центра Информационных Технологий, 1996. — Режим доступа: http://www.citforum.ru/hardware/svk/contents.shtml.

64. Шпаковкий, Г.И., Серикова, Н.В., Программирование для многопроцессорных систем в стандарте MPI — Минск: БГУ, 2002.

65. Шураков, В.В. Надежность программного обеспечения систем обработки данных. — 2-е изд. — М.: Финансы и статистика, 2008. — 272 с.