Прочитать публикацию в формате PDF 108 Кб Для чтения PDF необходима программа Adobe Reader

УДК 004.052.3

П.В. Ковалёв

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

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

Ключевые слова: надежность, мультиверсионность, сети, методы оценки, методы анализа сетей.

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

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

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

Опишем модель N-версионного программирования [2] (рис. 1) в виде ГЕРТ сети (рис. 2) и рассчитаем её основные характеристики, при условии, что количество мультиверсий N = 3, а остальные параметры описаны в табл. 1.

Таблица 1

Характеристика операций

Рис. 1. Модель N-версионного программирования

Рис. 2. Модель N-версионного программирования в виде ГЕРТ сети

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим расчет сети содержащей IOR вход и детерминированный выход рис.4, состоящей из нескольких подсетей рис. 5

Рис. 4. IOR-вход

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

Необходимо учитывать, что j – вычисляемый IOR-вход, имеющий стохастическое начало в узле i. {l1-m1}, {l2-m2}, …, {lN-mN} – N непересекающихся подсетей.

Пусть p_ij — вероятность того, что операция (i, j) будет вы­полнена при условии, что узел i выполнен, тогда имеем:

(1)

Учитывая что от входа до узла 4 находится 3 непересекающиеся подсети, в данном частном случае, используя выражение (1) получим:

(2)

Итак, воспользовавшись правилом Мейсона для замкнутых потоковых графов получим эквивалентную W-функцию [3] для этой сети:

(3)

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

мс (4)

И дисперсия

мс² (5)

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

(6)

Зависимость между числом мультиверсионных модулей и надежностью системы демонстрирует рис.6. На оси Х обозначено количество мультиверсий, на оси Y – надежность системы для разного количества модулей с разной надежностью каждого модуля (от 30 до 80%)

Рис. 6. Зависимость между числом мультиверсионных модулей и надежностью системы

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

Библиографический список

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

2. Algirdas Avizienis, The Methodology of N-Version Programming, in R. Lyu, ed itor, Software Fault Tolerance, John Wiley & Sons, 1995.

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

P.V. Kovalev

GERT-BASED RESEARCH OF SOFTWARE BUILD ON N-VERSION ARCHITECTURE

In this article the technique of research the reliability of N-version software is offered. It allows using algorithms and methods of network analysis for researching the reliability of software, developed by using N-version approach.

Keywords: reliability, N-version, networks, estimation methods, network analysis.

Библиографическая ссылка

Ковалёв П.В. ГЕРТ-сетевой анализ мультиверсионных архитектур программного обеспечения // Научный электронный архив.
URL: http://econf.rae.ru/article/4425 (дата обращения: 23.12.2024).

Получить сертификат

Форма заказа сертификата

Ф.И.О.
Почтовый адрес
Телефон
Авторы
Название работы
E-mail