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

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

Шеенок Дмитрий Александрович

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

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

АВТОРЕФЕРАТ

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

г 11!оя 2013

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

005539544

005539544

Работа выполнена в ФГОУ ВПО «Красноярский институт железнодорожного транспорта» - филиале ФГБОУ ВПО «Иркутский государственный университет путей сообщения» и ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева».

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

Официальные оппоненты:

доктор технических наук, профессор Терсков Виталий Анатольевич

Комарцова Людмила Георгиевна

доктор технических наук, профессор, Калужский филиал Московского государственного технического университета им. Н.Э. Баумана, профессор кафедры «Компьютерные системы и сети»

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

Семёнкин Евгений Станиславович

доктор технических наук, профессор, Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, профессор кафедры «Системный анализ и исследование операций»

ФГБОУ ВПО «Национальный исследовательский Томский политехнический университет».

Защита состоится 10 декабря 2013 г. в 14 часов на заседании диссертационного совета Д 212.249.02, созданного на базе ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» по адресу 660014 г. Красноярск, проспект имени газеты «Красноярский рабочий», 31.

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

Автореферат разослан « Я » ноября 2013 г.

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

диссертационного совета Александр Алексеевич Кузнецов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- применить реализованную программную систему при решении тестовых и реальных практических задач проектирования архитектуры ПО;

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

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

направленных на повышение эффективности процессов разработки и модернизации программных систем.

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

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

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

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

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

Разработанная программная система внедрена в компании ООО «Сибирские интеграционные системы» и используется при модернизации программного обеспечения информационной системы Пенсионного Фонда Российской Федерации.

Результаты диссертационного исследования, разработанные алгоритмы и программная система используются при проведении занятий по дисциплинам «Алгоритмы и структуры данных», «Управление данными», «Технология автоматизированного проектирования информационных систем» в Красноярском институте железнодорожного транспорта.

Основные положения, выносимые на защиту:

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

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

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

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

- XV научно-техническая конференция КрИЖТ ИрГУПС (Красноярск,

2011);

- Вторая межвузовская научно-практическая конференция «Транспортная инфраструктура Сибирского региона» (Иркутск, 2011);

- VIII Международная заочная научно-практическая конференция «Актуальные вопросы технических, экономических и гуманитарных наук» (Георгиевск, 2012);

- IV Международная научная конференция «Актуальные вопросы современной науки» (Санкт-Петербург, 2012);

- Международная научно-практическая конференция «Логистические системы в глобальной экономике» (Красноярск, 2013);

- XI международной научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2013);

- VIII Международная научно-практическая конференция «Техника и технология: новые перспективы развития» (Москва, 2013);

- I Международная конференция «Научные аспекты инновационных исследований» (Самара, 2013).

- Международная научно-практическая конференция «The Strategies of Modern Science Development» (Елм, США, 2013).

Диссертационная работа в целом обсуждалась на научных семинарах кафедры «Математика и информатика» Красноярского института железнодорожного транспорта (2010-2012 гг.) и кафедры «Системный анализ и исследование операций» Сибирского государственного аэрокосмического университета (2012-2013 гг.).

Публикации. По теме диссертации опубликовано 20 работ, среди которых 6 статей в журналах, входящих в перечень ВАК.

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

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

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

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

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

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

Существует два основных метода реализации программной избыточности:

1. NVP (N-version programming - Диверсионное программирование) - был предложен в 1985 году А. Авижиенисом. При реализации данного метода версии выполняются параллельно во времени, а результат их работы выбирается с помощью какого-либо алгоритма голосования. Алгоритмы голосования могут быть различными в зависимости от задачи, при этом сравниваемые значения считаются идентичными с учетом заданной погрешности.

2. RB (Recovery Block - блок восстановления) - был предложен в 1975 году Б. Ренделом. При реализации данного метода версии выполняются последовательно. После выполнения первой версии программного компонента приемочный тест по результатам выполнения принимает результаты вычисления, либо запускает следующую версию компонента.

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

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

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

Затем рассматриваются модели оценки стоимости программных систем. Одной из наиболее хорошо зарекомендовавших себя является модель СОСОМО II, которая впервые была опубликована в 1999 году. Для калибровки параметров модели использовались данные по 161 проекту. Среди сильных сторон модели СОСОМО II можно выделить следующие:

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

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

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

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

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

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

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

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

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

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

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

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

Если каждой обнаруженной ошибке сопоставить время на её устранение, то можно получить зависимость:

ад,

где 7} - время разработки и тестирования программного компонента, соответствующего функциональной точке, после устранения /-ой ошибки; й, -надёжность функционирования программного компонента после устранения /-ой ошибки, /= 1,2,...«;«- количество обнаруженных и исправленных ошибок.

Рассмотрим пример разработки программного модуля определенной сложности. По модели Джелинского-Моранды получена зависимость надёжности от времени тестирования (таблица 1). Также было зафиксировано время исправления ошибки.

№ Время Надёжность Время Время Время

ошибки тестирования после устранения разработки разработки и

до устранения ошибки 1е1, Лы, час. тестирования

обнаружения ошибки Л/. час. Т„ час.

ошибки tiesiu

час.

1 0.2 0.61 0.9 5.9 6.1

2 0.3 0.67 1.2 7.1 7.4

3 0.5 0.73 4.6 11.7 12.2

4 0.3 0.80 1 12.7 13

5 0.6 0.82 0.2 12.9 13.5

6 1 0.90 2.1 15 16

7 1.2 0.92 0.3 15.3 16.5

8 1 0.97 0.4 15.7 16.7

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

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

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

М- количество архитектурных уровней в архитектуре ПО;

Д'; - количество компонентов на уровне /, / е {1 ,..,М};

Ду - множество индексов компонентов, зависимых от компонента / на уровне /, /€{1,..,^}, ;е{ЦМ};

Ец - множество индексов компонентов, от которых зависит компонент / на уровне/, /е{1,..,ЛГу-}, у'е{1,..,А/};

Fy - событие сбоя, возникшего в компоненте i на уровне j, i е {1,.., /V,.},

PUij - вероятность, того что компонент i на уровне j будет использоваться; PFy - вероятность, того, что в компоненте / на уровне j возникнет сбой; R,j - вероятность того, что в компоненте i на уровне j сбой не появится; PL„m' - условная вероятность того, что в компоненте т на уровне п возникнет

сбой, если возникнет сбой в компоненте i на уровне j, i e{\,..,Nj},

j e{l,..,M},ne{l,..,Nm},me {1 ,..,M} i

TAij - относительное время доступа к компоненту i на уровне j, i е {1,.., N j },

j 6 {1 ,..,М}, определяемое отношением среднего времени доступа к компоненту i на уровне j к числу сбойных компонентов на более низких архитектурных уровнях во время доступа к компоненту; параметр ТА у имеет смысл использовать, если компонент работает на удаленных или изолированных системах;

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

ТСу - относительное время анализа сбоя в компоненте / на уровне j, определяемое отношением среднего времени анализа сбоя в компоненте i на

уровне j, i&{\,..,Nj}, j е {1,..,М), к числу сбойных компонентов на всех

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

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

ТЕу - относительное время устранения сбоя в компоненте / на уровне j, определяемое отношением среднего времени восстановления в компоненте i на уровне j, i е {1,.., N j}, j е {1,.., М}, к числу сбойных компонентов на всех

уровнях архитектуры, в которых происходит устранение сбоев в одно и тоже время;

Ntey - число сбойных компонентов на всех уровнях архитектуры, в которых происходит устранение сбоев во время устранения сбоя в компоненте / на уровне j;

TUij - относительное время использования компонента i на уровне j, определяемое отношением среднего времени использования компонента / на

уровне j, i е {\,..,Nj}, j e {1,.., M}, к числу компонентов на всех уровнях

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

NtUy- число компонентов на всех уровнях архитектуры, используемых в одно и тоже время с компонентом i на уровне j;

Kjj - глубина программной избыточности компонента /, на уровне j; Zy - множество версий компонента /", на уровне j; RTy - среднее время выполнения модуля i на уровне j; Ту - трудоемкость разработки компонента i на уровне j;

Ту - трудоемкость разработки версии к компонента / на уровне j, keZjj, в чел-часах;

NVX/j - трудоемкость разработки среды исполнения версий (приемочного теста для RB (recovery block, блок восстановления) или алгоритма голосования для

10

NVP (N-version programming, Диверсионное программирование);

B/j - бинарная переменная, принимающая значение 1 (тогда NVPq=0, RBij=0), если в программном компоненте не используется программная избыточность, иначе равна 0;

NVP,j - бинарная переменная, принимающая значение 1 (тогда Д,/=0, /¿8,/=0), если в программном компоненте введена программная избыточность методом NVP, иначе равна 0.

RB/j - бинарная переменная, принимающая значение 1 (тогда В,у=0, NVP,f= 0), если в программном компоненте введена программная избыточность методом RB, иначе равна 0.

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

MTTF - среднее время возникновения сбоя в системе, которое определяется как среднее время, в течение которого сбоев в программном обеспечении не возникает;

S — коэффициент готовности программной системы;

Ts - общая трудоемкость реализации программной системы.

Надёжность мультиверсионного компонента i на уровне j, построенного из К версий методом мультиверсионного программирования для любого К равна:

к

R,:

№

■Pi)

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

Надёжность мультиверсионного компонента / на уровне j, построенного из К версий методом блока восстановления для любого К равна:

**=± ир"№ - р"

где р' ,у - вероятность безотказной работы приемочного теста для компонента г, /=1,..,Д' на уровнеу',у=1,..,М; р^ — вероятность безотказной работы версии Вероятность сбоя таких компонентов равна:

PFt]= 1

■r9.

Среднее время выполнения программного компонента ; на уровне ] вычисляется как сумма времени работы компонента без сбоев и времени простоя компонента:

RT., = TU„ ■ Ntu„

PFt+ Y\PL1-PF*-PV*)

^TA,rNtaiJ.+TCirNtcv+TEirNte^ PFlf+ ^{PL^-PFab-PuJ

где РЬ^ - условная вероятность того, что в компоненте / на уровне ] возникнет сбой, если сбой возникнет в компоненте а на уровне Ь, ае{\,..,Ыь}, 6е{1,..(М}, /е {1,,.,/у,}, у'е {Р11у - вероятность того, что компонент / на уровне] будет использоваться; РР'у - вероятность того, что в компоненте / на уровне у возникнет сбой;

При расчете трудоемкости разработки учитываются затраты на реализацию среды исполнения версий модуля (Л'КЛ^) и затраты на реализацию каждой версии (7*(,). Трудоемкость разработки системы рассчитывается следующим образом:

м ( / А'

у=1 1=1

А=1

Среднее время сбоя в системе равно:

МПТ 1 -)х[77/, +

№ ¿=1

М

(т=1 )&(т*У) п=1

2 2

л/

га,, +

(т=1)&(т*/) п=1

^ ^ (1-М*,)* ^6'„т + ^((1-Р/Г)хШ/т)

]}

Среднее время простоя системы равно:

М

7Я = ]Г 2] х «V х КЧ + ГС, + ГЯ,) +

м <=1

л/ N.

2 I

)&(/№./) Я=1

(^пт + + 7Е«,) + (яс х (7^ + ГС,т + ТЕ1т))

Л 2 М&, И. + + Г^) + х (ГЛ. + + Щи))

Коэффициент готовности системы равен:

МПТ

]]]}

5 = -

МТТР + ТН .

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

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

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

На коэффициент готовности системы и трудозатраты на её разработку влияют значения PFtj и Ту. Прогнозные значения вероятности сбоя могут быть рассчитаны по моделям надёжности ПО, а значения трудозатрат по модели СОСОМОII. Если для компонента сложно определить значения вероятности сбоя и трудозатрат, то можно задать множество альтернативных вариантов «вероятность сбоя/трудозатраты» с помощью модели роста надёжности SGRM, зависимости затрат от надёжности или экспертной оценки.

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

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

Общий вид задачи оптимизации архитектуры следующий: S—ушах, Г,—>min,

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

RTV <RT„° U е {1,..,Nj }, j е {1,..,М} ), S >£>,

где Ts°, RTjf - предельные значения критериев.

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

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

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

Время расчета критериев S w Ts зависит от количества компонентов и связей между ними. На персональном компьютере со средней производительностью требуется около 1.5 сек. для расчета архитектуры из 10 компонентов, для архитектуры из 1000 компонентов требуется около 150 секунд. С ростом

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

Количество возможных решений рассчитывается следующим образом:

где W - количество комбинаций; D - количество программных компонентов, в которых возможно введение избыточности; Vara - количество вариантов «вероятность сбоя/трудозатраты» для компонента с возможностью введения избыточности; Vera ~ количество используемых версий при введении избыточности (2 < Verd < Lj); Lj - предельно допустимое количество версий компонента; F -количество программных компонентов, в которых невозможно введение избыточности; Fa/y - количество вариантов «вероятность сбоя/трудозатраты» для компонента, в котором невозможно введение программной избыточности.

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

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

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

1. Метод реализации программной избыточности: мультиверсионное программирование (NVP,j= 1, RBtJ= 0) или блок восстановления (NVP-,j= 0, RB,j= 1). Если выбран метод NVP, то устанавливается значение гена 0, если RB, то 1.

2. Номер варианта (альтернативы) Varn - «вероятность сбоя/трудозатраты». Возможные варианты задаются аналитиком для каждого компонента (¡<VarviSVi/). V,y - количество альтернативных вариантов разработки для каждого компонента.

3. Номер варианта Var^...Varv]a - вероятности сбоя для каждой версии компонента, аналогично пункту 2 (OSVar^. iu^Kj, 0 - версии нет). Предельное количество версий программного компонента, если будет применена избыточность, заранее задается аналитиком и не может быть больше 10 версий, т.к. большее количество вносит в компонент дополнительную сложность и стоимость, неоправданную увеличением надёжности.

Если гены все Varv2...Var„in принимают значение 0, то считается, что программная избыточность не вводится в данном компоненте (5,/= 1).

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

Уу).

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

Таблица 2 - Генотип и фенотип особи

Группа компонентов, с возможностью программной избыточности Группа компонентов, без возможности программной избыточности

Компонент 1 Компонент N Компонент 1 Компонент М

NVP/RB Vor., Var* NVP/RB Var„ Vafvj Var Var

1 3 0 0 1 0 2 3

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

Входные параметры ГА следующие: размер популяции (N); вероятность скрещивания (prob cross); вид скрещивания (1,2,3-точечное, равномерное); вероятность разрыва связанных генов (prob cross inter)', вероятность мутации особи (probmutate); вероятность мутации гена (prob mutate_gen);

критерии останова (максимальное время работы timejga, количество популяций без улучшения решения (стагнация) stagnancy, количество популяций pop count);

процент популяций на обработку ограничений percent bound; количество ограничений на время выполнения компонентов В.

Собственно алгоритм реализуется следующей последовательностью действий:

1. Генерация родительской популяции Р размером N случайных особей.

2. Расчет критериев для всех особей популяции Р.

3. Пропорциональная селекция N/2 особей из Р по критерию S в промежуточную популяцию Р'.

4. Пропорциональная селекция N/2 особей по критерию Ts в промежуточную популяцию Р'.

5. Скрещивание с вероятностью prob cross N12 случайно выбранных пар особей из промежуточной популяции Р'. Формирование основной популяции Р из N выбранных особей.

6. Выполнение оператора мутации с вероятностью prob mutate на каждой особи основной популяции Р и каждому гену особи с вероятностью prob_mutate_gen.

7. Расчет значений критериев оптимизации для всех особей популяции Р.

8. Выбор из популяции Р недоминируемых решений. Если в найденных ранее решениях есть решения, которые их доминируют, то stagnancy = stagnancy+l.

9. Если сработал хотя бы один критерий останова, то остановка алгоритма.

10. Если номер популяции меньше, либо равен percent bound*pop count, то переход на шаг 3.

11. Пропорциональная селекция N1(2+0) особей из Р по критерию нарушения ограничения на S в промежуточную популяцию Р'.

12. Пропорциональная селекция N1(2+0) особей по критерию нарушения ограничения на Ts в промежуточную популяцию Р'.

13. Пропорциональная селекция N1(2+0) особей по каждому критерию нарушения ограничения на время выполнения компонента RTy в промежуточную популяцию Р'.

14. Скрещивание с вероятностью prob_cross N/(2+Q) случайно выбранных пар особей из промежуточной популяции Р'. Формирование основной популяции Р из N выбранных особей.

15. Выполнение оператора мутации с вероятностью prob mutate на каждой особи основной популяции Р и каждому гену особи с вероятностью probmutatejgen.

16. Расчет критериев по ограничениям для всех особей популяции Р.

17. Выбор из популяции Р лучших решений по критериям ограничений. Если в найденных ранее решениях есть лучше, то stagnancy = stagnancy+l.

18. Если сработал хотя бы один критерий останова, то остановка алгоритма, иначе переход на шаг 11.

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

В четвертой главе рассмотрена программная реализация генетических алгоритмов, её применение на реальной задаче проектирования программной архитектуры. Также сформулирована методика применения ГА на стадии архитектурного проектирования ПО.

ГА был применен на задаче проектирования программной архитектуры по одной из модернизаций программно-технического комплекса «Администрирование страховых взносов» (ПТК АСВ), используемого в Пенсионном фонде Российской Федерации.

По оценочным данным было определено, что самое надёжное и затратное архитектурное решение имеет Ts = 720.2 чел-час. и S = 0.9904613, а самое ненадёжное и дешёвое — Ts = 403.2 чел-час. и S = 0.9883245. Для выполнения данной модернизации системы заданы следующие ограничения:

5 >0.99, Ts < 650 чел-час.

Пространство оптимизации такой задачи составляет 7.03-108 решений. Характеристики найденных недоминируемых вариантов модернизации системы приведены в таблице 3.

№ варианта Коэффициент готовности системы Трудозатраты на модернизацию, чел-час.

1 0.9900439 549.41

2 0.9900628 561.94

3 0.9901376 564.37

4 0.9903010 578.16

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

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

На рисунке 1 представлен процесс проектирования применения архитектуры с применением разработанной системы._

Рисунок 1 - Алгоритм применения ГА 17

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

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

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

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

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

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

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

Основные этапы предложенной методики оценки затрат на ПО следующие:

1. Сбор и анализ технических требований заказчика.

2. Декомпозиция задач, проектирование архитектуры.

3. Группировка компонентов на типы (функциональные точки) по аналогичному назначению и сложности.

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

5. Оценка трудозатрат на разработку компонентов.

6. Вычисление трудоемкости разработки.

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

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

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

М - количество типов компонентов (функциональных точек); / - тип компонента, / 6 М;

N1 — количество новых и подлежащих доработке компонентов /-го типа; у - номер компонента /-го типа, у е Л^;

7} - трудоемкость разработки компонента /-го типа, чел.-час;

гу - количество версий в компоненте, если вводится программная избыточность (если программная избыточность не вводится, то V,-, = 1);

Ш3, - трудоемкость разработки среды исполнения /-Й функциональной точки для блока восстановления, чел.-час. (если ЯВр>0, то ЫУР,=0);

ЫУР1 - трудоемкость разработки среды исполнения /-й функциональной точки для Диверсионного программирования, чел.-час. (если ЛУ/',>0, то &8,=0);

Т1к»~ трудоемкость этапа разработки, чел.-час;

С ¿ю- стоимость оплаты одного чел.-часа разработчика, руб;

Е - количество этапов в жизненном цикле ПО, кроме этапа разработки;

- весовой коэффициент, определяющий долю трудоемкости этапа 51 от трудоемкости этапа разработки;

Т, - трудоемкость этапа 5, зависящего от этапа разработки;

С5 — стоимость оплаты одного чел.-часа сотрудника занятого на этапе 5, руб;

Тр - общая трудоемкость проекта, чел.-час;

Ср - общая стоимость проекта, руб.

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

Д/ /V,

^+^" г-+(/?й<+шр<))

¡=1 м

Трудоемкость л'-го этапа жизненного цикла рассчитывается по соответствующему весовому коэффициенту и трудоемкости этапа разработки:

Общая трудоемкость проекта рассчитывается как:

Е

т = 1 р

СР-

5 = 1

Формула расчета общей стоимости в детализированном виде выглядит следующим образом:

М N,

Xс^ 'YsYJ(Т< + ^ ~r< + + Л'К/')) ¡=1 i=i

Проверка методики была произведена на системе ПТК АСВ и показала удовлетворительные результаты.

В заключение диссертации приведены основные результаты диссертационного исследования и выводы.

Основные результаты н выводы

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

1. Предложен подход к использованию зависимости надёжности функциональных точек и трудозатрат на её достижение при планировании трудозатрат на разработку ПО.

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

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

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

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

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

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

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

Публикации по теме диссертации

Статьи в рецензируемых изданиях, рекомендованных ВАК РФ:

1. Шеенок Д.А., Жуков В.Г., Терсков В.А. Повышение надежности программного обеспечения сложных систем // Вестник СибГАУ. Вып. 5(45). -2012.-С. 28-33.

2. Шеенок Д.А., Кукарцев В.В. Оценка затрат на модернизацию программного обеспечения критических по надежности систем // Вестник СибГАУ. Вып. 5(45). - 2012. - С. 62-65.

3. Шеенок Д. А. Инструментальное средство проектирования оптимальной архитектуры отказоустойчивых программных систем // Программная инженерия. №6. - 2013. - С. 20-26.

4. Шеенок Д.А. Оптимизация программной архитектуры при разработке информационной системы Пенсионного Фонда России // Информационные ресурсы России. №3. - 2013. - С. 30-33.

5. Шеенок Д.А., Кукарцев В.В. Прогнозирование стоимости разработки систем с программной избыточностью // Известия Волгоградского государственного технического университета №14(117). - 2013. (Сер. «Актуальные проблемы управления, вычислительной техники и информатики в технических системах». Вып. 17)-С. 101-105.

6. Шеенок Д.А., Терсков В.А. Оптимизация программной архитектуры на основе генетического алгоритма с аллелями в шкале порядка // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. Вып. 2. - 2013. - С. 17-24.

Материалы конференций, статьи в сборниках:

7. Шеенок Д.А., Ильин Е.С., Терсков В.А. Проблемы использования вычислительных систем при управлении сложными технологическими процессами // Вестник КРО РИА: сб. научн. трудов. Вып. 1(27). - 2010. - С. 98-103.

8. Шеенок Д.А., Терсков В.А., Ильин Е.С. Повышение надежности программного обеспечения систем управления технологическими процессами // Труды пятнадцатой научно-технической конференции КрИЖТ ИрГУПС (5 мая 2011 г.). Т.1.-2011.-С. 72-76.

9. Шеенок Д.А., Программная надежность автоматизированных систем управления технологическими процессами на железнодорожном транспорте // Транспортная инфраструктура Сибирского региона: Материалы второй межвузовской научно-практической конференции, 16-18 мая 2011 г. Иркутск, - том 1,- 2011.-С. 244-248.

10. Шеенок Д.А., Анализ существующих моделей оценки стоимости разработки программного обеспечения // Электронное научно-практическое периодическое издание «Экономика и социум». Вып. 5. - 2012. - С. 931-939.

11. Шеенок Д.А., Проектирование надежной архитектуры программного обеспечения финансово-управленческих систем // Актуальные вопросы технических, экономических и гуманитарных наук: Материалы VIII международной заочной научно-практической конференции, г. Георгиевск, 5-6 декабря 2012 г. - 2012. - С. 27-30.

12. Шеенок Д.А. Генетический алгоритм поиска оптимальной архитектуры программного обеспечения // Актуальные вопросы современной науки: Материалы IV международной научной конференции 14-15 декабря 2012 г. -2012. -С.62-68.

13. Шеенок Д.А., Кукарцев В.В. Оптимизация программной архитектуры логистических информационных систем // Логистические системы в глобальной экономике: материалы Междунар. науч.-практ. конф. (14-15 марта 2013 г., Красноярск). Ч. 1. - 2013. - С. 138-145.

14. Шеенок Д.А. Модификация модели программной архитектуры для многокритериальной условной оптимизации // Перспективы развития информационных технологий: Материалы XI международной научно-практической конференции. - 2013. - С.76-81.

15. Шеенок Д.А. Формирование модели трудозатрат для функциональных точек программного обеспечения // Научные аспекты инновационных исследований: Материалы I Международной конференции г. Самара, 6-8 марта 2013 г.-Т.1.-2013.-С. 39-42.

16. Шеенок Д.А. Планирование трудозатрат при разработке надежных программных систем // Техника и технология: новые перспективы развития: Материалы VIII Международной научно-практической конференции (25.02.2013). -2013.-С. 46-50.

17. Sheenok Dmitry. The model dependence labor and software reliability // The Strategies of Modern Science Development: International scientific - practical conference (Yelm, WA, USA, 29-30 March 2013). - 2013. - P. 54-61.

Свидетельства о регистрации программных продуктов:

18. Шеенок Д.А. Система оценки затрат на модернизацию программного обеспечения (Evaluation System Labor): свидетельство о государственной регистрации программы для ЭВМ / Шеенок Д.А., Кукарцев В.В. - М.: Реестр программ для ЭВМ, 2013. Номер гос. per. №2013611112.

19. Шеенок Д.А. Система расчета надежности программной архитектуры и трудозатрат (Software Architecture Reliability and Labor): свидетельство о государственной регистрации программы для ЭВМ / Шеенок Д.А., Терсков В.А. -М.: Реестр программ для ЭВМ, 2013. Номер гос. per. №2013616127.

20. Шеенок Д.А. Генетический алгоритм оптимизации программной архитектуры (Genetic Algorithm optimization software architecture): свидетельство о государственной регистрации программы для ЭВМ / Шеенок Д.А., Терсков В.А. -М.: Реестр программ для ЭВМ, 2013. Номер гос. per. №2013616165.

Шеенок Дмитрий Александрович

Многокритериальная оптимизация отказоустойчивой программной архитектуры специализированными эволюционными алгоритмами

Автореферат

Подписано к печати 06.11.2013. Формат 60x84/16 Уч. изд. л. 1.0 Тираж 100 экз. Заказ № 153

Отпечатано в типографии КрИЖТ ИрГУПС 660028, г. Красноярск, ул. Ладо Кецховели, 89.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГОУ ВПО «Красноярский институт железнодорожного транспорта» - филиал

ФГБОУ ВПО «Иркутский государственный университет путей сообщения» ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени

академика М.Ф. Решетнёва»

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

—у

04201 451 497

Шеенок Дмитрий Александрович

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

05.13.01 - Системный анализ, управление и обработка информации (космические

и информационные технологии)

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

Научный руководитель: д.т.н., профессор Терсков В.А.

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ......................................................................................................................4

1 РАЗРАБОТКА СЛОЖНЫХ ОТКАЗОУСТОЙЧИВЫХ ПРОГРАММНЫХ СИСТЕМ........................................................................................................................10

1.1 Проектирование программного обеспечения............................................10

1.2 Модели надёжности программного обеспечения......................................17

1.3 Модели оценки стоимости программного обеспечения...........................23

1.4 Планирование трудозатрат на разработку надёжного программного

обеспечения...........................................................................................................33

Выводы...................................................................................................................40

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

2.1 Исходная модель архитектуры программного обеспечения....................42

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

Выводы...................................................................................................................56

3 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПОИСКА ОПТИМАЛЬНОЙ АРХИТЕКТУРЫ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ...........................................57

3.1 Задача оптимизации отказоустойчивой программной архитектуры.......57

3.2 Генетический алгоритм многокритериальной безусловной оптимизации программной архитектуры...................................................................................70

3.3 Генетический алгоритм многокритериальной условной оптимизации ..81 Выводы...................................................................................................................95

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

4.1 Описание программной системы «GA optimization software architecture» . .........................................................................................................................97

4.2 Применение системы и анализ результатов.............:...............................103

4.3 Методика применения генетического алгоритма на этапе

архитектурного проектирования.......................................................................109

2

Выводы.................................................................................................................Ill

5 МЕТОДИКА ОЦЕНКИ ТРУДОЗАТРАТ НА РЕАЛИЗАЦИЮ

ПРОГРАММНЫХ СИСТЕМ.....................................................................................112

5 Л Описание методики оценки затрат программных систем......................112

5.2 Применение методики и анализ результатов...........................................118

Выводы.................................................................................................................119

ЗАКЛЮЧЕНИЕ...........................................................................................................120

СПИСОК ЛИТЕРАТУРЫ...........................................................................................121

ПРИЛОЖЕНИЕ 1. Акт об использовании результатов исследования..................134

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5

— применить реализованную программную систему при решении тестовых и реальных практических задач проектирования архитектуры ПО;

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

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

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

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

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

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

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

Разработанная программная система внедрена в компании ООО «Сибирские интеграционные системы» и используется при модернизации программного обеспечения информационной системы Пенсионного Фонда Российской Федерации.

Результаты диссертационного исследования, разработанные алгоритмы и программная система используются при проведении занятий по дисциплинам «Алгоритмы и структуры данных», «Управление данными», «Технология автоматизированного проектирования информационных систем» в Красноярском институте железнодорожного транспорта.

Основные положения, выносимые на защиту:

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

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

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

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

- XV научно-техническая конференция КрИЖТ ИрГУПС (Красноярск,

2011);

- Вторая межвузовская научно-практическая конференция «Транспортная инфраструктура Сибирского региона» (Иркутск, 2011);

- VIII Международная заочная научно-практическая конференция «Актуальные вопросы технических, экономических и гуманитарных наук» (Георгиевск, 2012);

- IV Международная научная конференция «Актуальные вопросы современной науки» (Санкт-Петербург, 2012);

- Международная научно-практическая конференция «Логистические системы в глобальной экономике» (Красноярск, 2013);

- XI международной научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2013);

- VIII Международная научно-практическая конференция «Техника и технология: новые перспективы развития» (Москва, 2013);

- I Международная конференция «Научные аспекты инновационных исследований» (Самара, 2013).

- Международная научно-практическая конференция «The Strategies of Modern Science Development» (Елм, США, 2013).

Диссертационная работа в целом обсуждалась на научных семинарах кафедры «Математика и информатика» Красноярского института железнодорожного транспорта (2010-2012 гг.) и кафедры «Системный анализ и исследование операций» Сибирского государственного аэрокосмического университета (2012-2013 гг.).

Публикации. По теме диссертации опубликовано 20 работ, среди которых 6 статей в журналах, входящих в перечень ВАК.

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

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

1.1 Проектирование программного обеспечения

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

Решению данной проблемы посвящены исследования, таких ученых как Авижиенис [89-90], Майерс [35], Боэм [93, 95, 96], Луи [106, 107], Дилон [17], Берман [91], Липаев [28-34], Ковалев [20-25], Орлов [40], Черкесов [61] и других.

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

Фаза архитектурного проектирования программного обеспечения

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

10

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

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

Для соблюдения требований к надёжности проектируемой программной

системы необходимо уже на стадии архитектурного проектирования детально

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