Главная страница 1
скачать файл

Оптимизация контроля в программных проектах разработки больших систем

А. И. Марон, М. А. Марон (ГУ – ВШЭ)

127422 Россия, г. Москва, ул. Костякова 10, 302, Марону А. И.,
тел. моб. (+7-495 – 729-24-67), e – mail: amaron@hse.ru
The information approach is applied to a choice of control points in program complexes. The effective approach to optimization is offered

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

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

Содержательная постановка задачи. Современные программные комплексы, автоматизации технологических процессов строятся на основании объектного подхода [1]. Во многих случаях, это даёт возможность представить такой комплекс в виде совокупности функциональных блоков обменивающихся данными. В целей облегчения диагностирования для каждого функционального блока должна быть разработана система тестов, позволяющих, проверяя данные на выходах блока при известных входных данных, определить правильно ли работает блок. Если такая система тестов разработана, то программный комплекс становится эквивалентным объекту диагноза, представленному функциональной моделью. Он может быть представлен в виде ориентированного графа. Известно, что для обнаружения любой неисправности в таком объекте достаточно, установить контрольные точки на всех выходных вершинах. Под контрольной точкой понимается любой способ автоматической идентификации результата как правильного или неверного. Однако обнаружение неисправности, не обеспечивает её локализации. Поиск неисправного функционального блока может оказаться неприемлемо длительным. Для того чтобы решить эту проблему необходимо установить контрольные точки и к некоторым внутренним блокам. Создание контрольных точек обычно является достаточно затратным и сложным мероприятием. Поэтому их приходится устанавливать не к каждому блоку программного комплекса, что гарантировало бы однозначное определение неисправного блока, а к некоторым выбранным функциональным блокам. Очевидно, что такой выбор можно сделать различным образом. Каждому варианту будет соответствовать своя глубина диагностирования. Естественно желание найти наилучший вариант.

Задача допускает следующую формальную постановку.

Имеется программный комплекс, состоящий из функциональных блоков. Структурная схема комплекса задана ориентированным графом G, вершины которого соответствуют блокам, а дуги каналам передачи данных между ними. Дуга из вершины с номером i в вершину с номером j показывает, что результат работы блока i передаётся в блок j. Граф имеет r выходных вершин. На выходе каждого блока можно установить контрольную точку, позволяющую определить, является результат, выдаваемый этим блоком правильным или нет. При этом известно, что результат на выходе блока i, является правильным тогда и только тогда, когда он исправно функционирует, и на его входы поступают правильные результаты. Вероятность наличия неисправности в блоке i при условии, что зафиксирована неисправность комплекса, равна pi

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

Решение (Результаты).

Обозначим число внутренних вершин графа G через n. Соответственно общее число вершин этого графа равно (r + n). Допустим, что всего можно установить (m + r) контрольных точек. Причём r, из них устанавливаются к выходным вершинам. Выходной считается вершина, из которой не достижима ни одна другая. Пусть n > m. Задача состоит в том, чтобы определить оптимальный вариант расстановки m контрольных точек к n внутренним вершинам графа. Очевидно, что количество вариантов расстановки контрольных точек равно числу сочетаний из n по m. Для крупных программных комплексов число таких вариантов велико. Установим критерий оптимальности набора контрольных точек. Исходя из того, что он должен эффективно локализовать неисправный блок тогда, когда факт неисправности комплекса зафиксирован.

Пусть N – номер вершины, соответствующей неисправному функциональному блоку. Эта дискретная случайная величина может принимать значения от 1 до (r + n). Допустим, контрольные точки установлены к внутренним вершинам с номерами i1, i2, …, ij, …, im, а также выходным вершинам, n+1, n +2, …, n+r.

Обозначим этот набор контрольных точек через k, а множество всех возможных наборов контрольных точек через KT. Каждая контрольная точка набора k может выдать один из двух результатов: 1 - результат на выходе, является правильным; и 0 - результат на выходе, не является правильным. Соответственно этому набору соответствует двоичный вектор длиной (m + r) показаний, входящих в него контрольных точек. Все возможные значения этого вектора можно пронумеровать натуральными числами. Введём случайную величину K – показание контрольных точек набора k. Величины N и K являются зависимыми. Будем считать оптимальным тот, набор K*, который даёт максимальную информацию о номере вершине графа, соответствующей неисправному функциональному блоку программного комплекса


(1)

где
I(N,K) – средняя взаимная информация с величин N и K;



H(N) – начальная энтропия случайной величины N;

H(N/K) – условная энтропия (остаточная неопределённость).
Для нахождения оптимального варианта необходимо перебрать все возможные варианты расстановки контрольных точек, производя для каждого из них вычисления условной энтропии.
Непосредственное вычисление условной энтропии, основанное на её определении по Шеннону, связано с необходимостью генерации всех допустимых значений величины K и расчёте соответствующих сумм произведений условных вероятностей на их двоичные логарифмы. Это может вызвать огромные вычислительные трудности. Вместе с тем в данном случае можно предложить метод, намного упрощающий расчёт условной энтропии. Он состоит в следующем.

Если задан граф G, то можно считать, что задана матрица S связности этого графа. Она представляет собой квадратную матрицу размерности (n+r) x (n+r). Её элемент (i,j) равен 1, если существует путь из вершины i в вершину j, и он равен 0, в противном случае. Заполним главную диагональ этой матрицы символами 1. В результате получим матрицу, элемент (i,j) которой равен 1 тогда, когда неисправность в функциональном блоке i, проявляется и в контрольной точке, установленной на выходе блока j. Удалим из этой матрицы все столбцы кроме тех, номера которых входят в набор k. Получим прямоугольную матрицу Sk, строки которой соответствуют всем вершинам графа, а столбцы только тем, вершинам, к которым установлены контрольные точки. Номера совпадающих (не уникальных) строк этой матрицы, соответствуют номерам функциональных блоков, неисправности которых неразличимы при данном наборе контрольных точек. Только они вносят остаточную неопределённость. Обозначим множество не уникальных строк матрицы Sk через Fk. Оно состоит из определённого числа подмножеств попарно совпадающих строк. Обозначим подмножество попарно совпадающих строк через f. Можно показать, что справедлива формула


(2)

Выводы.

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


Авторы считают, что в данной работе новыми являются следующие положения и результаты:

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


Литература.

1.Липаев В. В. Программная инженерия – М.: ГУ – ВШЭ, ТЭИС, 2006.
скачать файл



Смотрите также:
Оптимизация контроля в программных проектах разработки больших систем
57.1kb.
Технология методологической поддержки командной разработки программных проектов
29.66kb.
Архитектор/разработчик баз данных, веб-разработчик – удаленная работа
44.25kb.
Код и наименование направления подготовки: 231000. 62 «Программная инженерия»
33.46kb.
Укрупненная технология разработки программных продуктов
336.05kb.
Тема Аппаратные реализации информационных процессов. Рассматриваются вопросы
169.3kb.
Вопросы для контроля по общему курсу "эвм и программирование"
40.12kb.
Теплообмен в электронной технике
58kb.
Лицензионный договор о предоставлении права использования программы для ЭВМ с открытым кодом
372.24kb.
Астапова Вера Александровна Учитель английского языка «Формы и виды контроля на уроках английского языка»
36.15kb.
Анализ эволюции систем менеджмента качества как фундаментальной основы знаниевых резервов предприятий и организаций
41.16kb.
Измерения, выполняемые в процессе разработки пп, помогают лучше оценить сам процесс разработки, принятый в организации, ход выполнения проекта и качество пп
200.87kb.