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

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

КРАПЧАТОВ Александр Иванович

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

05.25.05 – Информационные системы и процессы, правовые аспекты информатики

АВТОРЕФЕРАТ

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

кандидата технических наук

Москва 2009

Работа выполнена на кафедре моделирования в экономике и управлении

ГОУ ВПО «Российский государственный гуманитарный университет»

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

Косяченко Станислав Анатольевич

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

Попов Игорь Иванович

кандидат технических наук

Чернов Игорь Викторович

Ведущая организация: ГОУ ВПО «Московский государственный

институт электроники и математики

(технический университет)»

Защита состоится «02» октября 2009 г. в 14 -00 часов на заседании диссертационного Совета № Д 212.198.02 при ГОУ ВПО «Российский государственный гуманитарный университет» по адресу: 125993, Москва, Миусская пл., д. 6.

С диссертацией можно ознакомиться в библиотеке Российского государственного гуманитарного института.

Автореферат разослан «25» августа 2009 г.

Ученый секретарь

диссертационного совета Меркулов В.Н.

I. Общая характеристика работы

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

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

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

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

Степень разработанности проблемы. Основы методологии разработки и отладки сложных комплексов программ были заложены в работах зарубежных ученых Б. Боэма, Дж. Роббинса, М. Холстеда, М. Шумана и др. Кроме того, данной проблемой занимались отечественные ученые: В.В. Липаев, А.Г. Мамиконов, В.В. Кульба, С.А. Косяченко, П.П. Пархоменко, П.А. Правильщиков.

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

Объект исследования – сложные комплексы прикладных программ автоматизированных информационно-управляющих систем (АИУС).

Предмет исследования - методы планирования разработки и отладки комплексов программ АИУС.

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

Данная цель достигается посредством решения следующих задач:

- разработка методов повышения качества отладки и внедрения функциональных задач АИУС;

- планирование системной отладки и опытной эксплуатации комплексов программ АИУС на стадии технического проектирования;

- выбор оптимальной стратегии системной отладки комплексов программ АИУС;

- разработка методов реорганизации модульных комплексов программ АИУС.

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

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

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

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

На защиту выносятся следующие положения:

1. Методология планирования и организации отладки, определяющая методы и этапы отладочных работ, и последовательность их проведения для комплексов прикладных программ АИУС.

2. Основные показатели качества комплексов программ АИУС, характеризующие степень отлаженности исследуемого комплекса программ и его пригодности к эксплуатации после проведения отладки, и методы получения их количественных значений.

3. Основные требования и особенности оценки и планирования отладочных работ на этапе технического проектирования АИУС.

4. Общая задача максимизации объема отладочных работ при ограничении на выделенные ресурсы на этапах системной отладки и опытной эксплуатации комплексов программ АИУС.

5. Определение необходимого объема тестов и отладочных данных с использованием графа взаимодействия программ.

6. Методы и алгоритмы расчета средней длины и среднего количества маршрутов обработки информации на графовых моделях комплекса программ.

7. Определение состава и последовательности отлаживаемых подструктур комплекса программ, «заглушек» и «драйверов».

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

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

10. Задачи выбора оптимального периода реорганизации РБД при заданных стратегиях и различных типах структурных изменений предметных областей пользователей.

Теоретическая и практическая значимость работы.

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

Разработанные модели и методы позволяют оптимизировать процесс отладки и повысить качество сложных комплексов программ АИУС. Использование предлагаемой методологии планирования и организации отладки и совокупности формализованных моделей, методов и алгоритмов обеспечивает существенное снижение (на 15 - 20%) временных и стоимостных затрат на отладку при нормативных трудозатратах.

Внедрение. Предложенная методология планирования и организации отладки, методы выбора оптимальной стратегии отладки, методы выбора тестовых множеств и организации процессов тестирования по различным показателям применены при разработке и отладке различных функциональных задач АИУС РГГУ, что позволило повысить качество проектных решений, уменьшить количество необнаруженных ошибок, сократить трудоемкость и время проведения отладки на 20 – 25%.

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

Апробация результатов диссертационного исследования. Основные результаты диссертационной работы докладывались и обсуждались на Международных конференциях: «Проблемы управления безопасностью сложных систем», Москва 2007, 2008 гг., «Проблемы регионального и муниципального управления», Москва 2007, 2008, 2009 гг.

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

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

Список литературы содержит 79 наименований.

II. Основное содержание работы

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

В первой главе проведен детальный анализ и обзор существующих методов обеспечения качества и эффективности отладки программного обеспечения (ПО) АИУС и анализ возможностей их совершенствования»

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

Ошибки в комплексах алгоритмов и программ укрупнено классифицируются следующим образом.

1. Системные ошибки, обусловленные неправильным пониманием требований задачи и условий ее реализации в АИУС.
2. Алгоритмические ошибки, связанные с некорректной формулировкой и реализацией алгоритмов программным путем.
3. Программные ошибки (описки, ошибки в логике, кодировании и т. д.).
4. Технологические ошибки, возникающие в процессе подготовки программной документации и перевода ее на машинные носители.

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

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

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

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

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

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

Для формализованной постановки задачи будем считать заданными:

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

События нумеруются таким образом, что если событие i предшествует событию j, то i < j.

4. Управление , состоящее в назначении анализа результатов проектирования на события (работы) сети.

При анализе результатов по событиям ,

1 – если при наступлении i-го события проводится анализ

результатов проектирования;

0 – в противном случае.

При анализе результатов проектирования по работам ,

1 – если при завершении работы (ij) проводится анализ

результатов проектирования;

0 – в противном случае.

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

, (1)

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

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

, (2)

где – множество возможных путей при проектировании системы; – множество возможных путей при проведении анализа результатов проектирования для работ, анализ выполнения которых производится по окончании проектированиями и – множество возможных путей при повторном проектировании; – время повторного проектирования работы (i, j) и – время анализа результатов работы (i, j); – работы, результаты которых анализируются в процессе проектирования и – работы, результаты которых контролируются по окончании проектирования.

Критерий минимизации среднего времени проектирования будет иметь вид

. (3)

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

Для сетей с небольшим числом событий (работ) наиболее эффективным является метод «ветвей и границ». В работе определены процедура ветвления и способ нахождения оценок.

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

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

На основании проведенных исследований и обобщения опыта отладки комплексов программ АИУС выделено пять этапов отладочных работ.

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

На втором этапе системной отладки выявляются ошибки в использовании памяти ЭВМ (тестирование физической реализуемости).

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

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

На пятом этапе проводится анализ эффективности комплекса программ, полученного в процессе системной отладки.

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

В работе используются следующие группы показателей качества: 1) сложность С, избыточность И; 2) физическая реализуемость Фр; 3) время функционирования Вф, согласованность по управлению Су, согласованность по информации Си, функциональная корректность Кф; 4) показатели, характеризующие надежность Н, эффективность системы защиты 3, эффективность средств восстановления В; 5) показатель, характеризующий затраты на проектирование и отладку комплекса программ Э. Систематизированы методы количественной оценки приведенных показателей качества.

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

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

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

Во второй главе рассматриваются модели и методы планирования разработки и отладки программного обеспечения АИУС на этапе его технического проектирования.

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

Рассматриваемые в работе таблицы решений состоят из четырех квадрантов. В левой части таблицы в двух квадрантах приводятся перечни подлежащих проверке при системной отладке или опытной эксплуатации входных условий и входных действий . Взаимнооднозначное соответствие между определенной совокупностью входных условий и выходных действий задается в правой части таблицы в виде столбца , называемого правилом. Для каждого входного условия записываются возможные значения , , а для действия – возможные значения, , . Значения и принадлежат конечному множеству числовых значений. В рассматриваемых таблицах принимает одно их трех значений (0, 1 или прочерк), а – одно из двух значений (0 или 1). При этом прочерк в строке означает, что значение условия для выполнения данного правила неосуществимо.

Разработка и программирование правил таблиц решений, формирование исходных данных (условий) и реализация процедур обработки данных (действий) требует определенных стоимостных Q0 и временных затрат. Т0, Q0 и Т0 определяются суммированием соответствующих затрат на разработку и программирование (QР и ТР ), системную отладку (QС и ТС ) и опытную эксплуатацию (QЭ и ТЭ ) комплекса программ задачи. Величины QР и ТР вычисляются из выражений:

ТР = ; ,

где di – оценка затрат на разработку части алгоритма задачи, соответствующей i –му правилу; и соответственно, средняя ставка и число разработчиков; и – затраты времени и средств на индивидуальную отладку программы задачи.

Затраты на системную отладку и опытную эксплуатацию находятся для каждого этапа следующим образом:

;

(4)

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

– время реализации действия ;

– время формирования условия при ;

= 1, если , = 0, если ,

т. е. = 1, если элемент k-го типа стоит на -м месте, и нулю в противном случае.

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

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

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

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

(5)

при ограничениях:

• на величину выделяемых ресурсов

; (6)

• на число проверяемых условий и выполняемых действий

; ; (7)

• на состав множества правил, включаемых в план отладки заранее, где xi = 1, если i-е правило включено в план системной отладки и нулю в противном случае; , если , , если ; zj = 1, если , zj = 0, если .

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

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

(8)

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

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

На завершающих этапах технического проектирования в качестве модели разработки и планировании отладочных работ используется граф G(V, U) взаимодействия программ, являющийся результатом преобразования блок-схемы задачи, информационные массивы которой отождествляются с множеством вершин V, а обрабатывающие их программы – с множеством дуг U графа G. Данная модель предназначена для исследования комплекса программ задачи на уровне функционирования функциональных связей и оценок трудоемкости отладки входящих в него программ. Предложен способ классификация программ, входящих в граф G, по степени сложности их разработки и отладки, позволяющий более качественно и обоснованно планировать дальнейшую разработку и отладку задачи как совокупности наборов программ различной сложности, выполняющих заданные функции обработки данных.

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

(9)

при ограничениях:

• на число отлаживаемых программ

; (10)

• на последовательность отладки программ

, (11)

где x(i,j) = 1, если программа–дуга (i, j) графа G включена в план отладки, и нулю в противном случае; – общее время отладки (i, j)-й программы; – множество дуг, заходящих в i-ю вершину графа взаимодействия программ.

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

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

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

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

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

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

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

,

где , если i-й программный модуль включается в v-й подграф при разбиении графа, , в противном случае; , если v-й подграф включается в k-й этап связной отладки и , в противном случае; – переменная, характеризующая состав программных модулей v-го подграфа разбиения; , – переменная, характеризующая состав подграфов и программных модулей, участвующих в k-ом этапе связной отладки; – переменная, определяющая состав k–1 этапов связной отладки; и – времена реализации тестов при автономной и связкой отладке; и – времена генерации тестовых данных при автономней и связной отладке; и – времена локализации ошибок при автономной и связной отладке; – вероятность обнаружения ошибки; – время создания подпрограммы «драйвера» для i-го программного модуля; – время создания подпрограммы «заглушки» для j-го программного модуля; , если между i-м и j-м программными модулями есть дуга связи по управлению, , в противном случае.

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

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

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

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

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

,

где , если выбирается m-й вариант разбиения и n-й вариант объединения графа, , в противном случае; – время автономной отладки подграфов разбиения; – время связной отладки подграфов объединения,

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

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

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

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

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

Время прогона теста предполагается равным одной условной временной единице. Поставим в соответствие i-му числу ошибок в программе () i-е состояние Марковского процесса. Тогда процесс отладки будет представлять собой случайное блуждание точки в пространстве (N+1) состояний. При предположении, что в программе во время отладки не может быть больше N ошибок и что в полностью отлаженной программе новые ошибки возникать не могут, процесс отладки можно представить в виде модели случайных блужданий с конечным числом состояний, с отражающим и поглощающим экранами. На основе использования данной модели определены некоторые наиболее важные характеристики процесса отладки, необходимые при ее планировании. К таким характеристикам относятся: математическое ожидание времени отладки программы, математическое ожидание времени поиска заданного числа ошибок, дисперсия этих величин и т. д.

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

Для каждого модуля задается общее число начальных изменений Аi, которые должны быть сделаны в i-м модуле. Пусть А есть вектор-строка с элементами Аi. т. е. А – общее число изменений за начальный цикл. Тогда АiР – общее число изменений, которые необходимо сделать в системе после внесения изменений в i-м модуле за начальный цикл. Элемент (i, j) матрицы Р2 есть сумма вероятностей того, что изменения в модуле i вызовут изменения в модуле k, а затем в модуле j, т. е. .

Следовательно, АР2 есть число изменений, которое необходимо сделать за второй цикл. На k-м цикле общее число изменений системы есть АРk, k = 0, 1, 2..., а общее число изменений в системе равно N = А (I + р + р2 +...).

Полученный степенной ряд сходится, если | Р | < 1, что указывает на конечное число изменений в системе. Если ряд сходится, то общее число изменений определяется выражением , где I – единичная матрица размером n  n, а число изменений каждого цикла равно соответственно АI, AP, AP2 и т. д. На основе полученных соотношений предложена процедура оценки общего числа изменений в системе.

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

Выделены три типа структурных изменений. Изменения 1-го типа связаны с заменой системы управления распределенными или локальными базами данных; изменения 2-го типа обусловлены появлением дополнительных узлов вычислительной сети, новых пользователей, запросов, информационных элементов и взаимосвязей между ними; изменения 3-го типа связаны с изменением характеристик вычислительной сети, запросов пользователей, информационных элементов, структуры РБД и требований пользователей.

Исследованы следующие стратегии реорганизации РБД на заданном интервале времени Т:

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

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

Решение задачи базируется на точных аналитических и приближенных графических методах.

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

1. На основе проведенного обзора существующих методов обеспечения качества и эффективности отладки сложных комплексов программ анализа возможностей их совершенствования показана эффективность использования комплексного подхода к контролю, анализу и отладке программ при разработке АИУС.
2. Разработана методология планирования и организации отладки, определяющая методы и этапы отладочных работ и последовательность их проведения для комплексов программ АИУС, характеризующихся большим количеством взаимосвязанных структурированных программных модулей, выполняемых функций, большими объемами перерабатываемой информации и повышенными требованиями к времени функционирования, защите от несанкционированного доступа, надежности, достоверности исходных данных и т. п. Данная методология основана на представлении отладки в виде многоэтапного итеративного процесса получения комплекса программ с заданными показателями качества. Систематизированы также основные показатели качества комплексов программ АИУС, характеризующие степень отлаженности исследуемого комплекса программ и его пригодности к эксплуатации после проведения отладки, и методы получения количественных значений показателей качества.
3. Сформулированы основные требования и выявлены особенности оценки и планирования отладочных работ на этапе технического проектирования АИУС. В качестве формальных моделей правил, последовательности решения и отладки задач АИУС предложено использовать язык таблиц решений и графы взаимодействия программ. С использованием таблиц решений поставлена общая задача максимизации объема отладочных работ при ограничении на выделенные ресурсы на этапах системной отладки и опытной эксплуатации комплексов программ АИУС. Приведены наиболее целесообразные практические постановки задач планирования отладочных работ и предложен эффективный алгоритм их решения, использующий схему «ветвей и границ». Использование языка таблиц решений позволяет проводить предварительную оценку требуемых ресурсов на решение задач АИУС и их отладку на начальных этапах технического проектирования.

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

4. Поставлена общая задача выбора оптимальной стратегии системной отладки. В качестве критериев оптимальности использованы временные и стоимостные характеристики этапов системной отладки, в качестве ограничений – ограничения структурного типа, задающие множество допустимых стратегий проведения отладочных работ. Разработаны методы и алгоритмы расчета средней длины и среднего количества маршрутов обработки информации на графовых моделях комплекса программ, позволяющие определять временные и стоимостные характеристики различных стратегий организации и проведения системной отладки.
5. Разработаны методы выбора оптимальной стратегии системной отладки комплекса программ АИУС из множества заданных стратегий. Предложенные методы определяют состав и последовательность отлаживаемых подструктур комплекса программ и состав программ «заглушек» и «драйверов» при минимальных временных или стоимостных характеристиках системной отладки. Разработан метод выбора оптимального множества тестов для локализации обнаруженных ошибок, обеспечивающих минимальное время или стоимость на проведение процесса локализации при заданной полноте проверки исследуемых структур комплекса программ.
6. Исследованы процессы внесения изменений в модульное программное обеспечение. Предложена математическая модель отладки, базирующаяся на рассмотрении программы в виде отображения пространства входов программного модуля в пространство его выходов. Процесс реализации программы рассматривается как последовательность таких отображений, а процесс поиска ошибок связывается с поиском ошибочных отображений в последовательности. Число ошибок программного обеспечения связывается с числом состояний системы, а процесс их обнаружения связывается с переходом системы из одного состояния в другое, что обеспечивает учет «волнового» эффекта. Скорость обнаружения ошибок измеряется временем обнаружения одной ошибки, которое является случайной величиной с известным распределением.
7. Поставлены и решены задачи выбора оптимального периода реорганизации РБД при заданных стратегиях и различных типах структурных изменений предметных областей пользователей. Для каждой из выделенных стратегий реорганизации предложены и исследованы методы ее проведения. Поставлены и решены задачи определения оптимального периода реорганизации в заданном классе стратегий, обеспечивающего минимум суммарных потерь в РБД, связанных с невозможностью получения требуемой информации или получением неадекватных данных, а также с затратами на реорганизацию.
8. Предложенные методы использованы для повышения эффективности функционирования и реорганизации АИУС РГГУ.

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

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

1. Крапчатов А.И. Оптимальная система отладки сложных комплексов программ // Приборы и Системы. Управление, Контроль, Диагностика. – М. – 2009. – № 3. 0,3 п.л.
2. Гладков Ю.М., Крапчатов А.И. Кононов Д.А. Сценарное исследование социально-экономических систем: методология, задачи, практика применения // Вестник РГГУ. Серия Управление. – М.: РГГУ, 2007. № 12. 0,8 п.л.

Статьи и материалы конференций

3. Крапчатов А.И. Методы планирования отладки и опытной эксплуатации программного обеспечения задач автоматизированных информационно-управляющих систем на стадии технического проектирования // Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции. – М.: РГГУ, 2009. 0,2 п.л.
4. Косяченко С.А., Крапчатов А.И. Методология повышения качества отладки и внедрения программного обеспечения функциональных задач автоматизированных информационно-управляющих систем // Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции. – М.: РГГУ, 2009. 0,1 п.л.
5. Косяченко С.А., Крапчатов А.И. Выбор оптимальной стратегии системной отладки комплекса программ АИУС // Труды IV Международной конференции по проблемам управления. – М.: ИПУ РАН, 2009. 0,2 п.л.
6. Крапчатов А.И. Общая задача выбора оптимальной стратегии системной отладки комплекса программ АИУС // Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции. – М.: РГГУ, 2008. 0,2 п.л.
7. Крапчатов А.И. Методы повышения качества отладки и внедрения функциональных задач АИУС // Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции. – М.: РГГУ, 2008. 0,2 п.л.
8. Крапчатов А.И. Методы и алгоритмы определения основных характеристик тестовых множеств // Проблемы управления безопасностью сложных систем: Труды ХVI международной конференции. – М.: РГГУ, 2008. 0,3 п.л.
9. Косяченко С.А., Крапчатов А.И. Задача выбора оптимальных тестовых множеств на этапе системной отладки // Проблемы управления безопасностью сложных систем: Труды ХVI международной конференции. – М.: РГГУ, 2008. 0,3 п.л.
10. Крапчатов А.И. Экономические аспекты обеспечения безопасности информационной среды предприятия в условиях глобализации // Глобализация: вызов национальной и мировой экономике: Материалы VII Чаяновских чтений. – М.: РГГУ, 2007. 0,3 п.л.
11. Крапчатов А.И. Графовая модель взаимодействия программ для определения необходимых ресурсов, состава и очерёдности отладочных работ // Проблемы регионального и муниципального управления. Материалы международной научной конференции. – М.: РГГУ, 2007. 0,4 п.л.
12. Крапчатов А.И. Методика предварительной оценки ресурсов на отладку комплексов программ и определение проверяемых условий и процедур с использованием таблиц решений // Проблемы регионального и муниципального управления. Материалы международной научной конференции. – М.: РГГУ, 2007. 0,3 п.л.
13. Крапчатов А.И. Планирование системной отладки и опытной эксплуатации программного обеспечения задач АИУС на стадии технического проектирования // Проблемы управления безопасностью сложных систем: Труды ХV международной конференции. – М.: РГГУ, 2007. Ч. 2. 0,2 п.л.

Личный вклад автора в совместные работы

В [2] предложена совокупность факторов, определяющих функционирование подсистемы «Социум».

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

В [4, 9] предложено использовать заданную совокупность показателей качества отладки для определения оптимальных тестовых множеств.