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

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

Чубейко Сергей Валерьевич

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

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

6 НОЯ 2014

Ростов-на-Дону - 2014

005554224

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

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

доктор технических наук, профессор Бутакова Мария Александровна

Штейнберг Борис Яковлевич

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

Воробьев Сергей Петрович

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

Ведущая организация: федеральное государственное автономное

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

Защита состоится 08 декабря 2014 г. в 1530 часов на заседании диссертационного совета Д 218.010.03 в Ростовском государственном университете путей сообщения по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, д. 2, конференц-зал.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО РГУПС по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, д. 2 и на сайте http-Лwww.rgups.ru.

Автореферат разослан ^ октября 2014 г.

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

диссертационного совета Д 218.010.03 доктор технических наук, профессор

Бутакова М. А.

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

Актуальность темы исследования

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

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

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

Подтверждением актуальности темы исследования является участие автора в грантах, поддержанных Российским фондом фундаментальных исследований:

- 11-07-13110-офи-м-2011 -РЖД «Методы, модели и алгоритмы оценки качества функционирования и синтеза надежного ПО информационно-управляющих систем на железнодорожном транспорте»;

- 12-08-00798-а «Математическое и программное обеспечение интеллектуальной обработки неполных и слабоструктурированных данных в информационно-управляющих системах с повышенными требованиями к надежности и

качеству функционирования»;

- 13-01-00325-а «Гибридные модели интеллектуального управления и принятия диагностических решений в контролируемых динамических дискретных системах»;

- 13-01-00637-а «Модели интерполяций стохастических систем в условиях большой неопределенности: интеллектуальный анализ данных, алгоритмы и методы принятия оптимальных решений».

Степень разработанности проблемы

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

В первом направлении оно основано на преобразованиях функций со значениями в некоторых алгебраических полукольцах, причем обычные операции сложения и умножения заменяются на другие операции, связанные законом дистрибутивности. Если вместо обычного сложения используются операции нахождения максимума либо минимума, а вместо обычного умножения - операции обычного сложения, то получается подход, который в научной литературе называется (max, +), либо (min, +) алгеброй или идемпотентной математикой. Наиболее значительные результаты в этой области получены в нашей стране в работах В.Н. Колокольцова, Н.К. Кривулина, Г.Л. Литвинова, В.П. Маслова и их коллег. За рубежом в данной области значительные результаты получены Ф.Бачелли, П. Бутковичем, М. Гондраном, Ж.П. Квадра, Г. Коэном, У.М.

Макэнени, М. Мину и другими.

Во втором направлении дискретно-событийное моделирование основано на математических моделях роста надежности ПО вследствие обнаружения и исправления ошибок в ПО и его обновления. Наиболее важные результаты в рассматриваемой области получены в работах Д.С. Боуэна, А. Гоэла, 3. Дже-линского, Л.Д. Ла Падула, М. Липова, Г. Майерса, П.Л. Моранда, Дж. Муса, Т.А. Тейера, Н.Ф. Шнейдевинда, М. Шумана и других.

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

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

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

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

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

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

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

Объект, предмет и методы исследования соответствуют специальности 05.13.18, так как содержанием диссертации является разработка фундаментальных основ и применение математического моделирования, численных методов и комплексов программ для решения научных и технических, фундаментальных и прикладных проблем и соответствует п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента», п. 5 «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента» и п. 8 «Разработка систем компьютерного и имитационного моделирования» паспорта научной специальности.

Научная новизна. Основными новыми научными результатами являются

в области математического моделирования

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

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

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

- имитационная модель сетевой системы с гарантированным обслуживанием на основе (тт,+) подхода;

в области численных методов

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

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

- численный метод расчета (тт,+) интегральной свертки;

в области программных комплексов

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

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

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

- программная реализация на императивном языке программирования оценки прогнозирования надежности сетевого ПО.

Основные результаты, выносимые на защиту.

1. Метод модульного дискретно-событийного моделирования на основе интервальных временных событийных графов.

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

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

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

5. Методы имитационного моделирования и их программные реализации для технических приложений, связанных с задачами оценки надежное™ и производительности компьютерных систем: на основе (тт,+) фильтраций, метод расчета (тш,+) интегральной свертки и его реализация на функциональном языке программирования; метод имитационного дискретно-событийного моделирования производительности сетевых систем с гарантированным обслуживанием и его реализация на функциональном языке программирования; метод имитационного моделирования и прогнозирования надежности ПО на основе бутстреппинга и его реализация на императивном языке программирования.

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

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

Апробация результатов работы

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

- XII Всероссийском симпозиуме по прикладной и промышленной математике, 2011 г., г. Казань;

-Всероссийской научно-практической конференции «Транспорт-^ип»,

2011 г., г. Ростов-на-Дону;

- Первой научно-технической конференции «Интеллектуальные системы управления на железнодорожном транспорте (ИСУЖТ-2012)», 2012 г., г. Москва;

- Международной заочной научно-практической конференции «Теоретические и практические аспекты развития науки», 2013 г., г. Санкт-Петербург,

- Всероссийской научно-практической конференции «Транспорт-2013»,

2013 г., г. Ростов-на-Дону;

Международной научно-практической конференции «Строительство-

2013», 2013 г., г. Ростов-на-Дону.

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

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

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

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

результатов работы.

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

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

Определение 1 .

Временной событийный граф G имеет маркировку и является кортежем G^(P,T, А, со, М), С1) где Р - конечное множество мест, «places»; Т - конечное множество переходов, «transitions»; Aœ(PxT)U{TxP) конечное множество ребер между местами (условиями возникновения событий) и переходами (событиями, изменяющими состояние системы), а также^ между переходами и местами; a:(PxT)\J(TxP)->N" - весовая функция, приписывающая вес ребрам;

M е Ф - начальная маркировка графа.

Накладываются условия:

1) каждое ребро имеет единичный вес, ю(/>.',) = = 1;

2) множество всех входных переходов 'р, -»е Т | е л} дляр,-го

места и выходных переходов р] ->{/,.еГ|(я,,^)ел}(3ля /J, />авны 1,

N=H=1-D

На основе определения 1 сформулировано определение дискретном динамической системы на основе временного событийного графа.

Определение 2 .

Дискретная динамическая система на основе временного событийного графа является парой (G,s), где G - временной событийный граф, S - конечное множество состояний системы, начиная от начального f(0) со сменой состояний в моменты времени, описываемой уравнениями

«,(*)= М Ы*) + 5,);

ij{k + m) = si{k).

где (М") = {max,min),- наименьшее (или наибольшее) время k-го события активации перехода tr, ту(Л) - наименьшее (или наибольшее) время к-го события перехода т маркеров; S, - временная задержка в месте рг □

Добавление интервалов к временным событийным графам можно описать следующим образом. К каждому месту графа добавляется интервал p-ip. Нижнее значение р интервала обычно связывается с минимальным

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

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

Определение 3.

Интервальный временной событийный граф G, это кортеж G = {P,T,A,a,M,l),

где Р,Т,Л,а,М-такие, как в определении 1,

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

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

х,(* + 1)= © а9®х}{к-т), (2)

где^еКЗ, ©/„ , если {р, еР,М{р,) = т} = 0, то а}ев.

На рис. 1 показан пример интервального временного событийного графа.

[1Д

Рис. 1 - Интервальный временной событийный граф

Далее рассматриваются модули, из которых синтезируются дискретно-событийные системы в виде блоков «вход-состояние-выход» со следующими обозначениями, представленными на рис. 2.

4(4

. - 1 71 ф

ни V

т

• • •

-у,(ь)

Рис. 2 - Дискретно-событийная система с интервальными временными событийными графами

На рис. 2: ы, (А:) - к -й момент времени 1-го выходного воздействия. Динамика модулей в общем случае описывается системой уравнений:

\{к +1) = <М* ® (к),..., А,, ® хп(к),В, ® и, (к),...^ ® и„ (к)),

/=1,...,л; (3)

где (м* } = {min,шах}; А = - интервальная матрица состояния, В = [В^~ интервальная матрица входа; С = {с^} - интервальная матрица выхода, имеющая размерность рхп.

В матричном виде выражение (3) записывается как система

х(к + 1) = (А ® х(к))(М1)(В®и{к))-,

у(к) = с(м*)х(к),

где = {min,шах}.

Модуль последовательного исполнения событий показан на рис. 3.

ja^Ipi^Q—^...

Рис. 3 - Интервальный временной событийный граф последовательного исполнения событий

Вычислительная схема 1.

+ *„„[a.ä] ®х,{к +1 - и,));

У(к)=хм{к).

Модуль конкурентного исполнения событий показан на рис. 4.

[а. А]

щ(к)

х^к-т,)

п т,

и1{к)

[л.Рз]

2{к-т2)

-И т ,

Н т,

-И-

Рис. 4 - Интервальный временной событийный граф конкурентного исполнения событий

Вычислительная схема 2. Для г = 1,2,..., л

X,(к + 1)(м:)([р,, а]® х, (к - т,),и,(*),*„, (*));

г„+1 {к+1){м:)([г1,д ] ® л-, (*+1 - «,), ...,[£„ л] ® х. (*+1 - я.));

Я*) = *«»(*)•

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

[Ро>Ро]

-И т

| *(*) -И-►

[Рп>Рп~\*Лк~т»)

■X т.

УМ —►

Рис. 5 — Интервальный временной событийный граф синхронизированного исполнения событий

Вычислительная схема 3.

Для / = 1,2,..., п

у, &)=*,(!)■

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

Пусть X(t)~ это случайный процесс с дискретным временем, имеющий

конечные математическое ожидание е[х,\ = ех и дисперсию Var[X,\ = Varx = ах. Коэффициент вариации процесса

с =Ei (4)

■ Е '

Индекс дисперсии процесса

jx=c2x±Px,. е>

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

Функционал вариативности информационной нагрузки это

(6)

Очевидно, что (6) при ц -> 0 имеет вид zх (0) = lim zx (ц), а с учетом (4) и

(5) может быть определено как

1+45>хд l+J

« _ l + Jx (7)

Аналитическую модель функционала оценки пиковой нагрузки в общем случае при ц ф 0 можно получить, если рассматривать случайный процесс X как вероятностный процесс с восстановлением (и без последействия). Для этого определим случайный точечный процесс Т = {Тк), ке.Ъ* на основе процесса X

как ^ = X X и соответствующий ему считающий процесс а таюке

математическое ожидание этого процесса

(8)

Тогда оценку пиковой информационной нагрузки можно выполнить, как

(9)

= —\г+Мх№>

где Мх (ц) = (/), ц £ 0 - это преобразование Лапласа-Стилтьеса.

о

Для улучшения оценки (9) рассмотрим модификацию (8) в виде Мх({) = Е\_Ых{Тк,Тк +*)], а также применим свойство эргодичности (усреднение по времени) к рассматриваемому случайному процессу X .

В связи с этим представляется возможным рассматривать процесс X, как имеющий п -мерную функцию плотности вероятности, и имеет место Утверждение 1

Пусть случайный процесс Х-{Хк], кеХ*, обладает свойством эргодичности и имеет аналитически определяемую п -мерную функцию плотности вероятности. Тогда

Л/л.(() = ¿Рг| а пиковая информационная нагрузка оценива-

ется по выражению (9).П Доказательство

Рассмотрим одну траекторию Х(я) случайного процесса X. Число событий, подсчитанных на интервале [?; (л),Г4(*) + /] считающим процессом Ых ^ будет определяться как

. (-1 м V» ;

где и - это индикаторная функция.

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

= Е

= Рг

=Рг

) и-1

' для считающего процесса получаем

мл w+o]=- ■' )•a У411™8^

Mx(/) = E[NX(Tt,Tt +1)] получаем

Mx (0 = Ekj {Tt (s),Tt (s) + /)] =

= Et

.«=! v .-1 J J v i-1 J

Далее в главе предложена модификация и построена аналитическая модель оценки пиковой информационной нагрузки в условиях скрытой Марковской модели, то есть в условиях, когда рассматриваемый случайный процесс X не является наблюдаемым (скрытым), а наблюдаемым является случайный процесс Y = {Yt}, к eZ+, однако для любого к вероятностное распределение Yk полностью определяется (управляется) Х„. Обычно, скрытая Марковская модель (Hidden Markov Model) представляет собой двумерный случайный процесс с дискретным временем, обозначается как HMM(X,Y) и определяется

следующим набором параметров tfAfllf (x,n,P,Y,Q). Первые три параметра

относятся к определению процесса X и обозначают X - множество состояний скрытого процесса X, л - вектор распределения вероятностей начального состояния модели, Р - матрица вероятностей переходов из одного состояния в другое. Четвертый и пятый параметр определяют соответственно: Y -множество состояний наблюдаемого процесса, Q - множество функций распределения или плотности вероятностей, устанавливающие связь между X и Y. Доказано утверждение 2. Утверждение 2.

Пусть случайный процесс Y определяется скрытой Марковской моделью НММ (X,У) = ЯШ(Х, it, P,Y,Q) с iV = |X| скрытыми состояниями. Также определена квадратная матрица Z(у) N -го порядка, элементами которой являются функции вида Z (у): [0, со) -> задаваемые как

'M = PuSej{x)dx,i,je{l,2,..,N}. _ (Ю)

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

где Z(n) - преобразование Лапласа-Стилтьеса Z{y), I - единичная квадратная матрица N -го порядка, 1„ - единичный вектор длины N, Ег

=т -

математическое ожидание случайного процесса У.О Доказательство.

Из определения НММ и выражения (10) можно сделать вывод, что вероятности Рг(^<г) можно рассчитать по формуле Рг(1^:£/) = я2(*)!„, а для

суммы значений процесса У - в виде свертки = Ис-

пользуя утверждение 1, заключаем, что Мг (*) = ^¿Г' (г). Выполнив преобразование Лапласа-Стилтьеса для левой и правой частей последнего выражения, получим Л/г(ц) = я2(ц)(/-2(ц))"Ч. Для получения оценки пиковой нагрузки, применив выражение (9), получим

гг (я) = 1 + *г(у)[1 -2(ц))" -4- = (7 - 2{У)){1 - 2(ц))" +

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

как

1 1

где /■'/(ц) - это преобразование Лапласа-Стилтьеса для кумулятивной вероятностной функции Гу (>>) = Рг(У, < у).

Заключительным результатом главы является Алгоритм 1. Числовая оценка пиковой информационной нагрузки. Часть 1.Расчет а.

1.1. Ввод последовательности наблюдаемых значений процесса {Х,} ^.

1.2. Расчет автокорреляционной функции процесса рх (1).

1.3. Расчет коэффициента вариации процесса по формуле (4).

1.4. Расчет индекса дисперсии процесса по формуле (5).

1.5. Расчет оценки пиковой информационной нагрузки по формуле (7).

1.6. Расчет а = 2,,(0)-1. Часть 2. Расчет р .

Входные параметры: рассчитанные в части 1 рх (1) и 2Х (0).

2.1. Ввод начального значения ц„, А.

2.2. Расчет р^ (1),

2.3. Рекурсивный расчет оценочных значений 2х (цу) 2.3.1.

7,(0),

к=0;

2.3.2. к =1;

к>1.

2.4. Расчет усредненной оценки р по формуле

1 ¿^/р-Ч^))

Р =

3. Конец алгоритма.

Третья глава диссертации «Дискретно-событийное моделирование в задачах оценки надежности программного обеспечения» посвящена разработке нового класса моделей, предназначенных для оценки надежности современного компонентного ПО. В главе проанализированы существующие динамические и статические модели оценки надежности ПО и установлено, что дискретно-событийный подход к такой оценке в данное время не предложен. Центральным результатом главы является оригинальный подход, характеризуемый следующими процедурами, которые в предлагаемом подходе можно разделить на две группы. Первая группа предназначена для генерации процессов, имитирующих появление ошибок в ПО. Сгенерированные модельные значения разделяются на несколько классов и составляют исходные данные для следующей группы процедур, которая предназначена для оценки надежности компонентного ПО. Модельные значения, которые разделены на классы, сопоставляются с различными классами ошибок в событийной модели типа «вход-структура-выход». При этом анализируемый с точки зрения надежности программный компонент также относится к одному из классов, в зависимости от используемых в нем программных конструкций. Каждому варианту программной конструкции соответствует отдельный вариант расчета оцениваемой надежности ПО.

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

1. Установление исходных положений моделирования

2. Выбор математического аппарата моделирования.

3. Генерация модельного процесса.

4. Переход к численному и алгоритмическому моделированию процессов.

Процедуры второй группы:

5. Формальное представление компонентной модели оценки надежности

ПО.

Определение 4.

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

1) | - некритические, не воздействующие на выход

своего и вход другого блока;

2) Гк - переходящие, воздействующие на выход своего и

вход другого блока;

3) ] - критические, воздействующие на выход своего

блока и не воздействующие на вход другого блока.

Оценкой надежности компонента с различной программной конструкцией будем считать вероятность возникновения события, связанного с проявлением ошибки любого вышеуказанного класса, рассматривая программный компонент как систему «вход-структура-выход» Рг(7,0), причем

У Рг(7,С>) = 1, V/

6. Варианты расчетов возникновения события, сигнализирующего появление ошибки ПО.

В связи с заявленным типом модели «вход-структура-выход» рассмотрим варианты расчета вероятности возникновения события, вызванного ошибкой, в зависимости от структуры программного компонента 6Л. Последовательная структура Вычислительная схема 4:

1. Генерация вероятностей Рг^(Д^),Рг^(/,0'),Рг^(/,С),

2. Для имитации возникновения некритической ошибки на выходе Ап:

(Г'°) = (/"р)' где

3. Для имитации возникновения переходящей ошибки на выходе А,:

4. Для имитации возникновения критической ошибки на выходе А„:

.....е>°)=рч,,-, (7'°')рч (о'-°) >

где 0*е^аСеКс.

6.2. Разветвляющаяся структура

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

Вычислительная схема 5:

1. Генерация вероятностей Рг^ (/,ГО), / е ГО е11^),7 = 1,...,л, Рг(с(), / = 1,...,л-1.

2. Для имитации возникновения ошибки рассчитывается

Рг(/,0) = (/.^О)Рг(^) + С-™/1" 2Рг(с- )1-

,«! V ¡-1 ;

6.3. Циклическая структура

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

■ раз

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

6.4. Параллельная структура

Если программный компонент предусматривает параллельное

исполнение п алгоритмов Л,, Л2.....Л„,то моделируется возникновение событий,

связанных с классами некритичных и критичных ошибок. Вычислительная схема 6:

1. Генерация вероятностей Рг^/.О^Р^Д/./^.Рг,,), 1,е ^, Г е ГЛ, Р и /$.) ] = 1,..., п.

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

3. Если л-1 параллельных ветвей имеют некритическую ошибку, а л-я ветвь имеет критическую ошибку, либо наоборот, то рассчитывается

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

следующие алгоритмы.

Алгоритм 2. Имитационное моделирование двумерного однородного

пуассоновского процесса на круге.

1. Ввод г,Х.

2. Генерация п событий пуассоновского процесса с интенсивностью

3. Генерация равномерно распределенных величин £/,,£/2,..Д, - •

4. Вычислить Я.г

^.Кг^и;.....Кг

5. Отсортировать Д„Л2,...Л в возрастающем порядке и получить Д(1),Я(2),...,.(?(„).

6. Генерировать п равномерно распределенных величин

и^,и^,...и2я~и( 0,1).

7. Вычислить 0, = 2пС/„,,©2 = = 2тIV 1п.

8. Сформировать пары (.Кщ.й^Др)'^)»—>(Я(>.)'0|)-

Алгоритм 3. Имитационное моделирование двумерного однородного пуассоновского процесса в области, ограниченной функцией f(x) в первом

квадранте.

1. Ввод к,Т.

2. j = l. л = 0. ш = 0. Х0=0.

3. Генерация равномерно распределенных случайных величин Uj-U (0,1).

4. а>у = -(1 / Я.)In(1 - СГу).

5. <В = со+СЙ,.

I

6. Если со <1 ff(x)dx, тогда п = п +1, переход к п.З.

о

«И

7. Найти xn,i = 1,2,...,л, удовлетворяющие условию J f(x)dx = a.

'С- 0

8. Генерация t/,+1,i/„+2,...l/2„ - t/(0,l) равномерно распределенных случайных величин.

9.

10. Формировать пары (-fy.x). / = 1,2,...,и.

11. Конец алгоритма.

Алгоритм 4. Имитационное моделирование двумерного неоднородного случайного пуассоновского процесса.

1. ¿ = 0. Ввод л.

2. Генерировать х, по алгоритму для одномерного неоднородного пуассоновского процесса с интенсивностью Ъх(х).

3. Генерировать у, в соответствии в соответствии с плотностью

MwVM*,)-

4. Формировать последовательность .

5. Если i <, п, то i := / +1. Перейти к п. 2.

6. Конец алгоритма.

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

Приведены примеры программ на функциональном языке J для расчета интенсивности обслуживания для канала CBR (Constant Bit Rate).

Програмлю 1 рг

]В1 =: тт(А1@$ + - я)) &>к11

Расчет метрик производительности.

1) максимальная задержка в обслуживании:

Программа 2

<1 =: тях@({@$ -

2) минимальная задержка в обслуживании:

Программа 3

=: Пно(к7)(1аи;(Г@5,: + 4аи)))"0.

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

Вычислительная схема 7. Прогнозирование ошибок ПО

1. Получить оценки м(Ь) = «(*,*, Д(Ь).А(Ь))> где Ь = 1,2.....В, размноженные методом бутстреппинга выборки, всего В оценок средней интенсивности ошибок.

2. Отсортировать по возрастанию полученные оценки средней интенсивности ошибок .

3. Определить требуемые доверительные интервалы (обычно нижнее значение а = 0.05, а верхнее значение а = 0.95) и отсечь не входящие в эти

интервалы оценки.

4. Используя оценку среднего значения и известные свойства функции

распределения Пуассона можно ожидать, что на интервале времени <„*, + г

количество ошибок будет не более 2_,-~Т] •

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

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

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

2 Классификация и подход к оценке пиковой информационной нагрузки функционалом специализированного вида. Оценка пиковой информационной

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

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

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

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

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

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

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

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

10. Метод имитационного моделирования и алгоритм прогнозирования надежности ПО путем модификации модели, построенной на неоднородном пуассоновском процессе, в котором применен способ размножения выборок, известный как бутстреп-метод. Реализована программа для оценки прогнозирования надежности ПО на императивном языке программирования.

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

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

1 Бугакова М.А., Гуда А.Н., Чубейко C.B. Моделирование и оценка качества функционирования сетевого программного обеспечения информационно-управляющих систем на транспорте в условиях предельных нагрузок // Вестник Донского государственного технического университета. - 2011. 1. 11. № о (57).- С.875-883.

2 Гуда А H Чубейко C.B. Прогнозирование надежности программного обеспечения на основе модели неоднородного пуассоновского процесса и буг-стреп-методов // Программные продукты и системы — 2012iJi-из.

3 Бутакова M А., Чубейко C.B. Имитационное моделирование процессов возникновения ошибок для оценки надежности программного обеспечения // Известия высших учебных заведений. Северо-Кавказский регион. Технические

науки.-2012.- №5(168).-, С.29-34.

4 Чубейко C.B. Алгоритмы и программное обеспечение для имитационного моделирования сетевых систем на основе (min,+) фильтрации // Современные проблемы науки и образования. - 2013. - № 6; URL: http://www.sc.ence, edncation.ru/113-11545 (дата обращения: 13.01.2014)

5 Чубейко С В. Дискретно-событийное моделирование сетевых компьютерных'систем в условиях высоких нагрузок // Фундаментальные исследования.

- 2014. - № 8 (Ч. 2). - С. 340-344.

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

6 Chernov A., Butakova M., Chubieko S., Klimanskaja E. Simulation Models and Algorithms based on Stochastic Jump Processes with Time Substitution// International Journal of Simulation Systems, Science and Technology " "SSST V14 -IJSSST'Vol 14 No Г, ГР H TrPT ' h^T^' infn/Vol-14/No-6/paper3.pdr.

1 Чубейко C.B., Бутакова M.A. Некоторые аспекты математических моделей очередей с обеспечением качества обслуживания // Обозрение прикладной и промышленной математики. - 2011.-Т.18. Вып. 1.-С. 165-166.

8 Чубейко C.B. Модели и методы сетеметрии в задачах разработки высо-конагруженных информационно-управляющих систем на транспорте // Труды Всероссийской научно-практической конференции «Транспорт-2011», май 2011 г. Часть 1. Естественные и технические науки. - Рост. гос. ун-т путей сообщения. Ростов н/Д, 2011. С. 59-61.

9 Гуда АН., Бугакова М.А., Чернов A.B., Чубейко C.B. Методы, модели и алгоритмы оценки качества функционирования и синтеза надежного программного обеспечения информационно-управляющих систем на железнодо-

транспорте // Труды Первой научно-технической конференции «Интеллектуальные системы управления на железнодоро-™ УЖТ-2012)», 15-16 ноября 2012 г. - М.: ОАО «НИИАС». - 2012. С. 270-274.

10 Чубейко C.B. Моделирование систем с гарантированным обслуживанием: элементы теории и программная реализация // Сборник научных статей по итогам Международной заочной научно-практической конференции «Теоретические и практические аспекты развития науки», 14-15 октября zun г. СПб.: Изд-во «КультИнформПресс», - 2013. С. 113-120.

тические и практические аспекты развития науки», 14-15 октября 2013 г. -СПб.: Изд-во «КультИнформПресс», - 2013. С. 113-120.

11. Москат H.A., Чубейко C.B. Моделирование телекоммуникационного трафика высокопроизводительных распределенных информационно-вычислительных систем железнодорожного транспорта // Труды Международной научно-практической конференции «Транспорт 2013». Часть 2. Технические науки. - Ростов н/Д: Рост. гос. ун-т путей сообщения, 2013. - С.65.

12. Паращенко И.Г., Чубейко C.B. Динамические модели оценки эффективности программного обеспечения // «Строительство-2013»: Экономика и управление: проблемы, перспективы, тенденции: материалы Международной научно-практической конференции. - Ростов н/Д: Рост. гос. строит ун-т 2013 -С. 234-236.

13. Паращенко И.Г., Чубейко C.B. Статистические методы оценки надежности программного обеспечения // «Строительство-2013»: Экономика и управление: проблемы, перспективы, тенденции: материалы Международной научно-практической конференции. - Ростов н/Д: Рост. гос. строит ун-т 2013 - С 237-239.

Личный вклад автора в работах, опубликованных в соавторстве:

[1] - функционал оценки пиковой нагрузки; [2] - разработка и программная реализация алгоритмов; [3] - модель оценки надежности ПО; [6] -программная реализация метода; [7] - идея (min,+) подхода к решению задачи-

[9]

оригинальный алгоритм оценки качества ПО; [11] - модель потока ошибок; [12,13] - обзор методов и моделей.

Чубейко Сергей Валерьевич

АНАЛИТИЧЕСКИЕ И ИМИТАЦИОННЫЕ МЕТОДЫ ДИСКРЕТНО-СОБЫТИЙНОГО МОДЕЛИРОВАНИЯ В ЗАДАЧАХ АНАЛИЗА НАДЕЖНОСТИ И ПРОИЗВОДИТЕЛЬНОСТИ КОМПЬЮТЕР1ШХ СИСТЕМ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Подписано к печати 29.09.2014 г. Формат бумаги 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,16. Уч.-изд. л. 1,11. Тираж 100 экз. Заказ № ? 61Ъ Ростовский государственный университет путей сообщения. Ризография РГУПС

^Р^ университета: 344038, г. Ростов-на-Дону, пл. им. Ростовского Стрелкового