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

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

МАЛИНИН Дмитрий Игоревич

□ из 17 Ю32

ПРИБЛИЖЕНИЯ, МЕТОДЫ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ МАСШТАБИРУЕМЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ

05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей (технические науки)

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

2 3 [.;■ П 2С:3

Тула 2008

003171032

Работа выполнена в ГОУ ВПО «Тульский государственный университет»

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

БЕРСЕНЕВ Геннадий Борисович

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

БОГАТЫРЕВ Михаил Юрьевич

кандидат технических наук КУЛИКОВ Вячеслав Васильевич

Ведущая организация Российский университет дружбы народов,

г Москва

Защита состоится «<36 » июня 2008 г. в 900 часов на заседании диссертационного совета Д 212 271 07 при ГОУ ВПО «Тульский государственный университет» (300600, Тула, проспект им Ленина, 92, 9-101)

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Тульский государственный университет»

Автореферат разослан «оМ » _мая_2008 г

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

диссертационного совета -г^я&к---Ф.А. Данилкин

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

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

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

Таким образом, объектом исследования диссертационной работы являются масштабируемые системы обработки данных (МСОД)

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

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

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

Это позволило выбрать в качестве предмета исследования диссертационной работы математический и программный инструментарий для анализа производительности МСОД

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

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

1 Исследование диапазонов работоспособности известных методов анализа производительности систем обработки данных, формализованных в виде одноуровневых и многоуровневых СеМО

2 Разработка нелинейных приближений для характеристик производительности многоканальных узлов обслуживания и СеМО.

3 Разработка приближенных методов анализа открытых и замкнутых СеМО большой размерности, вычислительная сложность которых не должна зависеть от размерности СеМО.

4 Получение аналитических выражений для характеристик производительности МСОД, формализованных в виде многоуровневых СеМО

5 Разработка общедоступного программного инструментария для анализа производительности МСОД

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

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

1 Получены эффективные приближения в виде аналитических выражений для среднего времени пребывания в системах массового обслуживания (СМО) М/М/с и GI/G/c, где се[ 1 10"], вычислительная сложность которых не зависит от размерности моделей, а также методика анализа открытых СеМО второго порядка с многолинейными узлами

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

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

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

5 Предложено расширение системы обозначений Кендалла для кодирования моделей МСОД в виде двухуровневых СеМО и получены аналитические решения для двухуровневой модели ремонтника и двухуровневой СМО

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

7 Предложено использование редактора Visio пакета Microsoft Office в качестве встроенного в инструментальную среду средства подготовки визуальных моделей производительности программных систем

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

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

Реализация и внедрение результатов. Разработанные в диссертации методы и инструментальные средства были использованы в ЗАО «Тульские Ай-Ти Лаборатории» при создании и масштабировании программного обеспечения IP-телефонии на базе универсального коммуникационного сервера CommuniGate Pro

Теоретические результаты работы и созданная инструментальная система используются в учебных курсах «Моделирование» и «Объектно-ориентированное программирование» на кафедре ЭВМ Тульского государственного университета, в курсовом проекте "Инструментальные средства для импорта/экспорта и семантического анализа моделей производительности программных систем", а также в дипломном проектировании по специальности «Вычислительные машины, комплексы, системы и сети».

Апробация работы. Основные положения диссертационной работы докладывались на следующих конференциях и семинарах 1 Всероссийская конференция по проблемам математики, информатики, физики и химии (Москва, РУДН, 2006, 2007, 2008 гг) 2 XIX Международная научная конференция «Математические методы в технике и технологиях» (Воронеж, ВГТА, 2006 г) 3 Всероссийская научно-практическая конференция "Системы управления электротехническими объектами" (Тула, ТулГУ, 2005, 2007 гг) 4 10-я Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, РГРТА, 2005 г.) 5 Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2004 г) 6. Межрегиональная научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, ТулГУ, 2003, 2004, 2005, 2007 гг) 7 Всероссийская научно-техническая конференция «Проблемы информатизации образования» (Тула, ТулГУ, 2008)

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

работ

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

Краткое содержание диссертации

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

В первом разделе приведен анализ основных технологий и инструментальных средств для создания программного обеспечения систем обработки данных Показано, что существующие технологии создания моделей производительности основаны на многоэтапном преобразовании UML моделей сценариев производительности с использованием метамоделей и форматов S-PMIF 2 0 (Software Performance Model Interchange Format) и PMIF 2 0 Выполнен обзор инструментальных средств, используемых для

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

Проведены исследования возможности использования моделей массового обслуживания и методов их анализа для определения степени масштабируемости программных систем (таблица)

Ограничения существующего инструментария для анализаСМО и СеМО (А/, /V, с - параметры, определяющие уровень масштабирования СОД)

Модель Метод/Выражение Ограничения

М/М/с Аналитическое выражение с <130

Рекуррентное выражение Зависимость сложности анализа от с

0/0/1 Аналитическое выражение Набор различных выражений

аас Аналитическое выражение Приближения через 0/0/1 и М/М/с

М/М/с/Ы Аналитическое выражение с< 130, И< 170

Открытая однородная СеМО 2-го порядка Диффузионное приближение Одноканальные узлы обслуживания

Замкнутая однородная СеМО размерности (А/,Л/), относится к классу мультипликативных моделей, включая ВСМР Прямой метод (нахождение вероятностей состояний путем решения системы уравнений баланса), рекуррентный метод Бузена, Зависимость сложности анализа от (М,Ы), причем МЛ^ < (30-50)

Замкнутая однородная СеМО размерности (М,Щ Приближенные итерационные методы Полиномиальная зависимость сложности анализа от (М,ЬГ)

Неоднородная по маршрутам СеМО размерности (А/,ЛО Метод, использующий асимптотические приближения для узлов СеМО Численный метод решения нелинейного уравнения с одним неизвестным (5 -10 итераций)

Многоуровневая СеМО размерности (Ь.М.Ы) Имитационные моделирование Большая вычислительная сложность, зависит от Ь, М, N¡1 заданной точности

Модели Маркова большой размерности Декомпозиция и решение системы уравнений баланса потоков вероятностей Сложность реализации распределенное по узлам компьютерной сети решение системы уравнений

Установлено, что существующие приближения нижней и верхней границы среднего времени ответа для системы массового обслуживания (СМО) М/М/с являются грубыми и даже некорректными в определенном диапазоне параметров, а рекуррентные процедуры для точного анализа имеют возрастающую с увеличением размерности вычислительную сложность С другой стороны, существует необходимость иметь аналитическое приближение для М/М/с, поскольку оно входит в аналитическое приближение для среднего времени ожидания в узлах ОЮ/с Рассмотрены методы расчета открытых СеМО, основанные на аппроксимации потоков сети с узлами типа 0/01/1 процессами

восстановления, метод Кюна, метод Райзера и Кобайаши, метод Геленбе и Пюжоля, метод УДИ. Анализ этих методов показал, что они не предназначены для расчета СеМО с многолинейными узлами, посредством которых обычно моделируют обслуживание нагрузки в МСОД

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

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

Во втором разделе разработаны основные приближения и методы для анализа масштабируемых систем обработки данных, формализованных в виде открытых СеМО второго порядка и замкнутых терминальных СеМО

В работе предложено несколько подходов к получению приближений Elu для среднего времени пребывания в СМО М/М/с Простейшая оценка получена посредством эквивалентного преобразования модели М/М/с в модель М/М/1 при использовании среднего времени пребывания в СМО в качестве инварианта преобразований-

Etu\ = nif, /[1 -р5(р)], где Pj(р) = р [1 + (с-1) Рс]/с, р = (1)

где А,// - интенсивности входного потока и обслуживания.

Более точная оценка среднего времени пребывания в СМО М/М/с была определена посредством использования асимптотического приближения с -> оо и применения формулы Стирлинга для факториала

£,М2 в■ --i^fiL, (2)

с 1-р 1-р-г(с,р) л/2я с

где m h = 1 / [i - среднее время обслуживания.

Наилучшая по точности оценка среднего времени пребывания в СМО М/М/с выведена с использованием известного аналитического решения для модели ремонтника (модели М/М/1/N) на основе приближенного метода, использующего асимптотическое приближение для узла обслуживания

£/и3

1-Р1

ть

с (1-р рО 1 -р

+ ть>

(3)

где р! ^

[(с + \)(Х +1) + с2Х] - д/[(с + 1)(Х +1) + с2Х]2 - 4(с + Х)(с + \)сХ

2(с + X)

X = \!(р с)

В работе задача определения оценки для СМО в/в/с рассматривается как оптимизационная задача выбора из оценок (1)-(3) для М/М/с и известных оценок для 01/01/1, которые минимизируют вычислительную сложность, расширяют (по размерности) диапазон использования, обеспечивают получение решений с положительным запасом и имеющих допустимую для инженерных расчетов точность В результате была получена следующая оценка, использующая (3)

еш0101с * **(1,:Р1) (4)

2с(1-р)(1-рр])

где са,с£ - коэффициенты вариации интервалов функций распределения вероятностей (ФРВ) входного потока и обслуживания

Приводится методика расчета открытой СеМО второго порядка Для учета многоканальности узлов СеМО используются полученная оценка (4) и известное приближение для коэффициента вариации интервалов ФРВ выходного потока для узла С1/С1/с Эти результаты позволили переработать алгоритм метода УДН и свести анализ открытой СеМО с узлами С1Ю/с к решению следующей линейной системы уравнений размерности М

относительно квадрата коэффициента вариации с^ (г) потока заявок, входящего в / -й узел, I = 1, М

~ 1 М - , -

с2а{1)- — ЪЧ е^-ВД) = 1 = 1 л/,

К1 к=\

(5)

I

М

Ч во» 4(0,0+114 е*, {1 + е*,[к2(*)-Ч} , *=1

л:1(/)=1-Р<2, к20)=Р2 \ + (с1{1)-\)/4^\, где в = '¡в/с, | - матрица вероятностей перехода заявок в СеМО

В работе введено понятие нагрузочной характеристики как зависимости среднего времени ответа от количества заявок в замкнутой терминальной СеМО (рис 1) или от интенсивности входного потока, поступающего в открытую СеМО.

Линейное приближение £/и*(Л0 нагрузочной характеристики, задаваемое как < £/«(1), tga >, определяется следующим образом-

|/(//) = N■tga-(N tga-Еш( 1)), еслиЛг>/У , где - асимптотическая к Еш(Ы) наклонная прямая

ЕЗи

ЕШ( 1)

1Г N

Рис 1. Нагрузочная характеристика и ее линейное приближение

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

Утверждение 1. Гиперболическое приближение нагрузочной характеристики терминальной СеМО в случае, если ее линейное

приближение задается параметрами < Еш(1), имеет следующий

вид

.(7)

где к - положительная константа

Исследования показали, что к = N /2 дает наилучшее приближение, а при ¿ = 0 гиперболическое приближение (7) превращается в линейное приближение(6)

Для простейшей терминальной СеМО - модели М/М/с/Ы (модели ремонтника) доказывается следующее утверждение

Утверждение 2 Гиперболическое приближение нагрузочной характеристики модели М/М/с/Ы имеет следующий вид

<л/1 + <А2

(8)

где м,у - интенсивности обдумывания и обслуживания, р - условная загрузка каждого канала узла обслуживания, р = Ыи /(су) .

На базе гиперболического приближения разработан метод анализа замкнутых однородных СеМО, в соответствие с которым вначале находится наиболее загруженный узел в СеМО, определяющий параметры

< Еш{ 1), //*, íga > гиперболического приближения, а затем используется (7) или (8) для определения среднего времени ответа.

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

Р{р0=IЬт. с^м+с^см = ^

,=1 и, с1р1(п1+с1)-п1И,с1м1р1

причем областью допустимых решений уравнения (9) является пересечение следующих двух открытых интервалов

(0,тт(1,тт{с,|д, /(й^щ) г = 1,М})),

(О, тт(1, тт {с,/и, (п, + с,) /(й, л, с^ )л = 1,А/})),

а наименьший корень уравнения (9) является единственным допустимым решением Здесь И, - коэффициент передачи потока в ;-й узел из терминального узла, а п1 < N - ограничение на число заявок в / -м узле

Для решения уравнения (9) с заданной точностью применяется метод золотого сечения или метод половинного деления, а при использовании пакета МаЛСАЭ это уравнение решается автоматически методом секущих Однако при большом числе узлов сети использование этих итерационных методов приводит к достаточно заметным вычислительным затратам, линейно возрастающим при увеличении М

В диссертационной работе получено приближенное аналитическое решение уравнения (9), точность которого (примерно 0,01) приемлема для большинства инженерных расчетов Для этого предложена аппроксимация /Хр]) в виде

Р*(х) = А х (1-Я *)/(1-5Г х) (10)

и доказано следующее утверждение

Утверждение 3. Если известны точки (х],/7]),^,/^) и (*з>^з)> где

= Г(х,), то левая часть уравнения (9) аппроксимируется функцией F*(х) и решением уравнения (9) будет

p¡=[A + N Б)2 -4-А-В-Щ/(2-А В), (11)

где 5 = ^ (*3 -х2)/х1+Р2 (Х1-Х2)/Х2+Р2 (х2~*1)/*з (х3-х2) + Р2 (х1-х3) + Г3-(х2-Х1)

В =

х3 F2 (l-S-x2)-X2 F3-(l-S x3) x3 F2 (\-S-x2)-xI-F3 (l-S-x3)

F3 (1-5 x3) x3 (1 -B x3)

Проведенные исследования показали, что точки, имеющие следующие значения координаты х:

xi =(l-3/N)-r, x2=(l-2/N) г, х3 = (l-1 /N)-r, где г- координата х самой левой точки разрыва функции F(x)~ г = т\п{с1/и1(п1 +ct)t(hlnlc\fi\) i-1, М), дают приемлемые результаты

В работе предложено приближение на основе функции (10) для аппроксимации нагрузочной характеристики открытой СеМО

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

В соответствии с предложенными обозначениями терминальная замкнутая СеМО с экспоненциальным обслуживанием и экспоненциальной длительностью пребывания в источнике емкостью N (в терминальном узле) рассматривается как модель M/M/S/N, где S определяет одноуровневую или двухуровневую сеть обслуживания Например, двухуровневая модель ремонтника с пулом из С) задачи на верхнем уровне и г\ каналов (процессоров или ядер процессора) на нижнем уровне обозначается как MIMI[cxlrxyN

В работе проведен анализ модели М / М l[cl r]l N Получены следующие вероятности состояний (п\,п2), где п\- число заявок, ожидающих начала обслуживания на входе задач, а п2- число заявок, находящихся на нижнем уровне - уровне аппаратных ресурсов (предполагается, что К, ц - интенсивности обдумывания в терминальном узле и обслуживания в процессоре соответственно, a X = X/\i)

МО, «2) = Д0,0)(Х/ц)"2 NUKN - п2)\п2'], 0 йп2<г,

р( 0, г+ i) = р(0,0)(Х/ц)г+' Nl/[(N -г-¡У г' г' ], i>0,r + i<c, р{щ,с) = р(0,0){Х/ц)сЛ"/[(7V-с-щ)\г\гс+"х~г], 0<щ <N-c,

/>(0,0) =

X1

с

'¿о(N- + ¿+1 (ДГ _ky^rk~r + tl(N-с-*)»г>г

Хк

N-c

+ S

х

с+к

ч-1

MIM/S/N

М/Л//[с,/г,]/Лг

M/A//[(Cl,c2)/r,]/iV

М/Л//[(с„сг, .cj//;]/^

M ! M 1[{сх,сг\0)1 rxy N

Терминальная сетевая модель

Двухуровневая модель ремонтника (пул из с1 задачи, г1 - число параллельных процессоров)

Двухуровневая модель с двумя последовательными узлами (пулами задач) на верхнем уровне

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

Двухуровневая модель с двумя узлами на верхнем

уровне и с маршрутной матрицей б

. о*-1

'•>ч-гтА|пД---'

^ »-сш^-axjj^- -*-au|o|!

Рис 2 Двухуровневые терминальные СеМО и их обозначения

В работе доказано, что среднее суммарное время пребывания в фазе обслуживания модели M / M /[cl г]/ N не зависит от с при условии, что N>c>r, и может быть получено из модели M/M/г!N Для модели M / M /[с/г]/ N получено выражение для Ni - среднего число заявок на верхнем уровне - уровне задач, а также его линейное асимптотическое (при N-+ со ) и гиперболическое приближения-

ENi(N,c,r) = N-c-r/X, (12)

Ni(N,c,r)t

N-c-r/X + ^N-c-r/X)2 +N/J2

/2

(13)

Предложено обозначение MlМ1[с/г] для двухуровневой открытой СМО, узел обслуживания которой моделирует пул из с задач на верхнем уровне и г каналов обслуживания на нижнем, и проведен ее анализ Получены вероятности состояний системы, а также выражения для среднего количества заявок на каждом из уровней системы Показано, что среднее время пребывания в модели М /М/[с/г] при с > г можно определять посредством СМО М/М/r. Таким образом, проведенный анализ моделей M/M/[c/r]/N и М/М/[с/г] показал, что если имеющаяся в системе обработки данных память позволяет расширять размер пула задач до необходимого размера, то для анализа производительности МСОД данного класса можно ограничиться одноуровневыми моделями

В работе предложен экспериментально-индуктивный подход для получения аналитических выражений характеристик производительности для наиболее простых моделей двухуровневых процессов обработки данных В этом случае результаты решения систем уравнений равновесия для двухуровневых СеМО небольшой размерности используются для индуктивного перехода к моделям большей размерности, однако проверка индуктивного перехода здесь выполняется посредством имитационного моделирования При реализации этого подхода было выполнено исследование моделей М !М /[(2,2) /1]/ 2, М/М/[(3,3)/1]/3, М/Л//[(2,2|0/1]/2, Л//М/[(3,3|0/1]/3, М/Л//[(2,2,210/1]/2 и др Проведенный анализ выражений для вероятностей их состояний позволил сделать ряд индуктивных предположений, которые затем проверялись имитационным моделированием, для следующих моделей M/MI[(N,N)/\]/N, МIМ/[(с|, ,ck)/l]/N, M/M/[(ch ,ck)/rx]/N, где

1 < r[ < с,, с, < N, i = 1 ,к. В результате было сделано следующее предположение для произвольной сети из к пулов задач на верхнем уровне и одним общим обслуживающим устройством на нижнем (для модели Л/Ш/[(сь ,ck\Q)IX\IN).

Р{щ,пъ ,nM)=WI{N-mf}?P? pnMpQ, Znt=k, p,=xht, (14)

i

где х-Л/ju. Вероятность pq в этом случае имеет вид.

Р 0 =

N

I [NU(N - кУ ] k=О

-1

Проведенный анализ выражений для среднего времени ответа в двухуровневой модели МIМ/[{с\, |0/1]/А^ позволил сделать следующее утверждение

Утверждение 4. Пусть Etu(x) - среднее время ответа для двухуровневой модели M/A//[(q, |Q)lr\]lN, 1<Г) <с,,с, <N,i = l,k, тогда Etu(x) = EtuMiMir[iN(xYJhl) или

I

кХк + £ кХк

« г£__хк__| хк ,

к=0 ki(N -к-1)1 Ыг r!(jV _ к _ 1 угк-г

В четвертом разделе рассматриваются вопросы, связанные с разработкой инструментальной среды и методики исследования производительности МСОД В отличие от существующих дорогостоящих инструментальных систем в работе предлагается использовать "облегченный" набор инструментальных средств (математических и программных) для анализа производительности программных систем Данный подход основывается на следующих концепциях более широкое использование моделирования производительности и масштабируемости программных систем на ранних и последующих этапах их создания, возможность использования широко распространенных офисных программ для подготовки моделей производительности и их анализа (например, программ Visio и Excel пакета Microsoft Office) Рассмотрены вопросы реализации инструментальных средств для анализа производительности в виде интегрированной настольной инструментальной системы и в виде распределенной среды

Интегрированная настольная инструментальная система создана на языке CU для экспериментального исследования существующих и предлагаемых методов, содержит средства (решатели) для аналитического и имитационного моделирования Се МО и состоит из вспомогательного математического модуля MathHelpersLibrary, библиотеки моделей системы QNModelsLibraiy и библиотеки решателей QNSolversLibrary.

Библиотека моделей системы содержит класс основной модели -одноуровневой или двухуровневой СеМО (LQNModel), классы моделей узлов, маршрутов, заявок, а также вспомогательные классы VisioXMLParser и XMLVisioDocument, позволяющие выполнять преобразование Visio-документа, сохраненного как XML-документ В библиотеку входит класс ModelXMLSenalizer, позволяющий преобразовывать LQNModel в модель на языке XML

Для включения редактора Visio в инструментальную среду были разработаны набор мастеров (Masters), определяющих типы элементов модели, их графические изображения и перечни атрибутов элементов-фигур (Shapes) модели работы системы, метамодель и XML-формат на основе метамодели для представления моделей работы системы в виде СеМО, библиотека в виде набора классов на языке С# д ля обработки визуальной модели, сохраненной в Visio в виде Visio-XML документа, формирования из нее XML-файла модели

работы системы и импорта этой модели в программу моделирования посредством интерфейса XML DOM.

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

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

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

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

- создавать визуальные модели производительности в среде Visio пакета Microsoft Office;

- выполнять преобразование Visio-документа, сохраненного как XML-документ, в XML-модель производительности с последующим импортом/экспортом XML-модели посредством интерфейса XML DOM,

- проводить синтаксический (на основе метамодели и соответствующей ей XML-схемы) и семантический анализ XML-модели производительности,

- выполнять аналитическое и/или имитационное моделирование и сохранение полученных результатов в XML-документе,

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

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

Выполнено исследование точности приближений (1)-(3) для среднего времени пребывания Etu в СМО М/М/с, которые показали, что погрешность определения Etu с помощью Etщ не превышает (3-4)% в области больших значений р.

Аналитическое и имитационное исследование выражения (4) для среднего времени пребывания в СМО G/G/c показал, что при изменении параметров са,съ в диапазоне от 0 1 до 10 средняя погрешность выражения (4) не превышает 12%, что приемлемо для большинства инженерных расчетов

Экспериментальные исследования зависимости относительной погрешности гиперболического приближения (8) для модели M/M/c/N от числа каналов с узла обслуживания и относительной загрузки канала р при различных значениях числа пользователей п показали, что в большинстве случаев она не превышает нескольких процентов При и = 170 эта погрешность достигает наибольшего значения (около 8 %) при р = 1.1

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

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

В заключении сформулированы основные результаты и выводы по работе

В приложении представлены акты о внедрении, результаты аналитического и имитационного моделирования одноуровневых и двухуровневых СеМО

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

1 Получены эффективные приближения в виде аналитических выражений для среднего времени пребывания в системах массового обслуживания (СМО) М/М/с и GI/G/c, где се[! ю"], вычислительная сложность которых не зависит от размерности моделей

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

3 Получено гиперболическое приближение нагрузочной характеристики замкнутой терминальной СеМО с многолинейными узлами

4 Разработан метод анализа замкнутых однородных СеМО на основе гиперболического приближения

5. Получено приближенное аналитическое решение для итерационного метода расчета замкнутых неоднородных по маршрутам СеМО с многолинейными узлами

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

7 Предложено расширение системы обозначений Кендалла для кодирования моделей МСОД в виде двухуровневых СеМО и получены аналитические решения для двухуровневой модели ремонтника и двухуровневой СМО

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

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

Основные публикации по теме диссертации

1. Берсенев Г.Б., Малинин Д.И. Алюритмы приближенного анализа открытых сетей массового обслуживания с многоканальным» узлами // Известия Тульского государственного университета. Серия «Вычислительная техника. Информационные технологии. Системы управления». Выпуск 1. Вычислительная техника. - Тула: ТулГУ, 2005. -С. 69-75.

2. Берсенев Г.Б., Малинин Д.И. Приближенный аналитический метод для замкнутых неоднородных стохастических сетей // Известия ТулГУ. Серия "Проблемы управления электротехническими объектами". Вып. 3. Труды Третьей Всероссийской научно-практической конференции "Системы управления электротехническими объектами" - Тула, ТулГУ, 2005. - С. 187 -189.

3. Берсенев Г.Б., Малинин Д.И. Приближенный анализ многоканальных систем массового обслуживания // Известия ТулГУ. Серия "Проблемы управления электротехническими объектами". Вып. 3. Труды Третьей Всероссийской научно-практической конференции "Системы управления электротехническими объектами" - Тула, ТулГУ, 2005.-С. 174-177.

4. Малинин Д И Повышение вычислительной эффективности определен™ среднего времени ожидания в модели G/G/c // Интеллект-2005 Интеллектуальные и информационные системы: Материалы межрегиональной науч техн. конф / Тульский государственный университет — Тула, 2005. - С. 19 - 22

5 Малинин ДИ Выбор оценок систем 01/01/1 для приближенного расчета открытых сетей массового обслуживания И НИТ-2005 Новые информационные технологии в научных исследованиях и в образовании - в тез докл. Всероссийской научно-техн. конф - Рязань, 2005. - с 23-24

6 Берсенев Г Б , Малинин Д И Приближения и оценки для моделей массового обслуживания С/О/с и М/М/с/Ы // Сб. трудов МНК ММТТ-19 Т. 8 Воронеж-ВГТУ, 2006 - С 156-160

7. Берсенев Г.Б., Малинин Д.И. Анализ двухуровневых терминальных стохастических моделей вычислительных процессов // Известия Тульского государственного университета. Серия «Вычислительная техника. Информационные технологии. Системы управления». Выпуск 1. Вычислительная техника. - Тула: ТулГУ, 2006. -С. 21-29.

8. Берсенев Г.Б., Малинин Д.И. Приближения и методы для анализа терминальных стохастических сетей // Известия Тульского государственного университета. Серия «Вычислительная техника. Информационные технологии. Системы управления». Выпуск 1. Вычислительная техника. - Тула: ТулГУ, 2006. - С. 171 -179.

9 Берсенев Г Б , Малинин Д И Аппроксимация времени ожидания в одноуровневой и двухуровневой модели М/М/с/Ы // Х1Л1 Всероссийская конференция по проблемам математики, информатики, физики и химии Тезисы докладов Секции математики и информатики - М РУДН, 2006 - С 52

10 Малинин ДИ Анализ открытой двухуровневой модели системы обработки данных с многопотоковыми процессами // Вестник Тульского государственного университета Серия «Вычислительная техника» Выпуск 1 Вычислительная техника - Тула ТулГУ, 2007 -С 98-102

11 Берсенев Г Б , Малинин Д И Использование экспериментально-индуктивного подхода для анализа двухуровневых терминальных стохастических сетей // Вестник Тульского государственного университета Серия «Вычислительная техника» Выпуск 1 Вычислительная техника -Тула ТулГУ, 2007 - С 93-97

12 Берсенев Г.Б, Малинин ДИ Анализ двухуровневых моделей систем обработки данных с многопотоковыми процессами // Системы управления электротехническими объектами. Выпуск 4. Сборник научных трудов четвертой Всероссийской научно-технической конференции - Тула-Изд-во ТулГУ, 2007 - С. 50 - 53

13 Берсенев Г Б , Малинин Д И. Эффективные приближения и оценки среднего времени ожидания для моделей массового обслуживания // Х1ЛН Всероссийская конференция по проблемам математики, информатики, физики и химии Тезисы докладов Секции математики и информатики - М РУДН,2007.-С 61.

14 Берсенев Г Б, Малинин Д И. Анализ двухуровневых терминальных стохастических моделей процессов обработки данных // ХЫН Всероссийская

конференция по проблемам математики, информатики, физики и химии. Тезисы докладов Секции математики и информатики. - M РУДН, 2007 - С 62

15 Берсенев Г Б, Малинин Д.И. Программное обеспечение для анализа замкнутых сетей массового обслуживания с многоканальными узлами // Интеллект-2007 Интеллектуальные и информационные системы Материалы межрегиональной науч техн конф / Тульский государственный университет. — Тула, 2007. - С. 31 - 33

16 Берсенев Г Б , Малинин Д.И Объектно-ориентированная система имитационного моделирования многоуровневых процессов обработки данных // Интеллект-2007 Интеллектуальные и информационные системы Материалы межрегиональной науч техн конф / Тульский государственный университет — Тула, 2007 - С 33-35

17. Берсенев ГБ, Малинин ДИ Использование MS Visio в инструментальной среде для анализа производительности масштабируемых программных систем // XLIV Всероссийская конференция по проблемам математики, информатики, физики и химии Тезисы докладов Секции математики и информатики -М. РУДН, 2008 -С 92

18 Берсенев ГБ, Малинин ДИ Использование MS Visio в инструментальной системе для дисциплины "Моделирование" // Тулаинформ-2008 Проблемы информатизации образования Материалы Всероссийской научно-технической конференции. - Тула ТулГУ, 2008. - С 50-53

19. Берсенев Г.Б., Малинин Д.И. Инструментарий для анализа производительности масштабируемых программных систем И Известия Тульского государственного университета. Технические науки. Выпуск 3. - Тула: ТулГУ, 2008. - С. 110 -116.

Изд лиц ЛР № 020300 от 12 02 97 Подписано в печать/£.05 08 Формат бумаги 60x84 1/16 Бумага офсетная Усл-печ л Уч-изд л Тираж №<Ьло Заказ С 33 Тульский государственный университет 300600, г Тула, пр Ленина, 92 Отпечатано в издательстве ТулГУ 300600, г Тула, ул Болдина, 151

ВВЕДЕНИЕ.

РАЗДЕЛ 1. ИНСТРУМЕНТАРИЙ ДЛЯ АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ И МАСШТАБИРУЕМОСТИ СИСТЕМ ОБРАБОТКИ ДАННЫХ.

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

1.2 Анализ и создание программного обеспечения на основе языка UML.

1.3 Анализ производительности в жизненном цикле программного обеспечения.

1.4 Оценка масштабируемости систем обработки данных.

1.5 Классификация и анализ моделей производительности.

1.6 Постановка задачи исследования.

1.7 Выводы.

РАЗДЕЛ 2. ПРИБЛИЖЕНИЯ И МЕТОДЫ ДЛЯ АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ МАСШТАБИРУЕМЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ.

2.1 Приближения для многолинейных узлов обслуживания.

2.2 Получение оценки для G/G/c.

2.3 Методика анализа открытых СеМО с узлами GI/G/c.

2.4 Гиперболическое приближение и метод анализа СеМО.

2.5 Приближенный аналитический метод для замкнутых неоднородных СеМО.

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

2.7 Масштабирование с использованием открытых СеМО.

2.8 Выводы.

РАЗДЕЛ 3. АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ ДВУХУРОВНЕВЫХ ПРОЦЕССОВ ОБРАБОТКИ ДАННЫХ.

3.1 Формализация двухуровневых процессов обработки данных.

3.2 Двухуровневая модель ремонтника.

3.3 Анализ двухуровневой многоканальной модели.

3.4 Экспериментально-индуктивный метод анализа двухуровневых

СеМО.

3.5 Выводы.

РАЗДЕЛ 4. ИНСТРУМЕНТАЛЬНАЯ СРЕДА ДЛЯ АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ И МАСШТАБИРУЕМОСТИ ПРОГРАММНЫХ СИСТЕМ.

4.1 Описание моделей производительности.

4.2 Использование редактора MS Visio для подготовки визуальных моделей производительности.

4.3 Описание многоуровневых моделей производительности.

4.4 Синтаксический и семантический анализ моделей производительности

4.5 Инструментальные средства для анализа терминальных СеМО.

4.6 Интегрированная инструментальная система.

4.7 Выводы.

РАЗДЕЛ 5. ИССЛЕДОВАНИЕ ТОЧНОСТИ РАЗРАБОТАННЫХ ПРИБЛИЖЕНИЙ И МЕТОДОВ АНАЛИЗА.

5.1 Исследование погрешности приближений для СМО М/М/с.

5.2 Исследование точности анализа открытых СеМО.

5.3 Исследование точности методов анализа терминальных СеМО.

5.4 Исследование погрешности методов анализа двухуровневых СеМО.

5.5 Анализ производительности при масштабировании сервера MedRec.

5.6 Выводы.

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

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

Таким образом, объектом исследования диссертационной работы являются масштабируемые системы обработки данных (МСОД).

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

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

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

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

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

1. Исследование диапазонов работоспособности известных методов анализа производительности систем обработки данных, формализованных в виде одноуровневых и многоуровневых СеМО.

2. Разработка нелинейных приближений для характеристик производительности многоканальных узлов обслуживания и СеМО.

3. Разработка приближенных методов анализа открытых и замкнутых СеМО большой размерности, вычислительная сложность которых не должна зависеть от размерности СеМО.

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

5. Разработка общедоступного программного инструментария для анализа производительности МСОД.

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

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

1. Получены эффективные приближения в виде аналитических выражений для среднего времени пребывания в системах массового обслуживания (СМО) М/М/с и GI/G/c, где се[1:1013], вычислительная сложность которых не зависит от размерности моделей, а также предложена методика анализа открытых СеМО второго порядка с многолинейными узлами.

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

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

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

5. Предложено расширение системы обозначений Кендалла для кодирования моделей МСОД в виде двухуровневых СеМО и получены аналитические решения для двухуровневой модели ремонтника и двухуровневой СМО.

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

7. Предложено использование редактора Visio пакета Microsoft Office в качестве встроенного в инструментальную среду средства подготовки визуальных моделей производительности программных систем.

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

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

Реализация и внедрение результатов. Разработанные в диссертации методы и инструментальные средства были использованы в ЗАО «Тульские Ай-Ти Лаборатории» при создании и масштабировании программного обеспечения IP-телефонии на базе универсального коммуникационного сервера CommuniGate Pro.

Теоретические результаты работы и созданная инструментальная система используются в учебных курсах «Моделирование» и «Объектно-ориентированное программирование» на кафедре ЭВМ Тульского государственного университета, в курсовом проекте "Инструментальные средства для импорта/экспорта и семантического анализа моделей производительности программных систем", а также в дипломном проектировании по специальности «Вычислительные машины, комплексы, системы и сети».

Апробация работы. Основные положения диссертационной работы докладывались на следующих конференциях и семинарах: 1. Всероссийская конференция по проблемам математики, информатики, физики и химии (Москва, РУДН, 2006, 2007, 2008 гг.). 2. XIX Международная научная конференция «Математические методы в технике и технологиях» (Воронеж,

ВГТА, 2006 г.). 3. Всероссийская научно-практическая конференция "Системы управления электротехническими объектами" (Тула, ТулГУ, 2005, 2007 гг.). 4. 10-я Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, РГРТА, 2005 г.). 5. Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2004 г.). 6. Межрегиональная научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, ТулГУ, 2003, 2004, 2005, 2007 гг.). 7. Всероссийская научно-техническая конференция «Проблемы информатизации образования» (Тула, ТулГУ, 2008).

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

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

5.6 Выводы

1. Выполнены исследования точности полученных приближений для среднего времени пребывания Etu в СМО М/М/с, которые показали, что погрешность определения Etu с помощью предлагаемого приближения (2.9) не превышает (3-4)% в области больших значений р.

2. Аналитическое и имитационное исследование полученного выражения (2.14) для среднего времени пребывания в СМО G/G/c показало, что относительная погрешность не превышает 12%, что приемлемо для большинства инженерных расчетов.

3. Экспериментальные исследования зависимости относительной погрешности гиперболического приближения для модели M/M/c/N показали, что в большинстве случаев она не превышает нескольких процентов.

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

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

ЗАКЛЮЧЕНИЕ

1. Получены эффективные приближения в виде аналитических выражений для среднего времени пребывания в системах массового обслуживания (СМО) М/М/с и GI/G/c, где се[1:1013], вычислительная сложность которых не зависит от размерности моделей.

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

3. Получено гиперболическое приближение нагрузочной характеристики замкнутой терминальной СеМО с многолинейными узлами.

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

5. Получено приближенное аналитическое решение для итерационного метода расчета замкнутых неоднородных по маршрутам СеМО с многолинейными узлами.

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

7. Предложено расширение системы обозначений Кендалла для кодирования моделей МСОД в виде двухуровневых СеМО и получены аналитические решения для двухуровневой модели ремонтника и двухуровневой СМО.

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

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

1. Авен О.И. Оценка качества и оптимизация вычислительных систем / О. И. Авен, Н. Н. Турин, Я. А. Коган. -М.: Наука, 1982.-464 с.

2. Башарин Г.П. Анализ очередей в вычислительных сетях. Теория и методы расчета / Г.П. Башарин, П.П. Бочаров, Я.А. Коган. М.: Наука, 1989. -336 с.

3. Башарин Г.П. Лекции по математической теории телетрафика: Учеб. пособие / Г. П. Башарин. М., Изд-во РУДН, 2004. - 186 с.

4. Башарин Г.П. О приближенных методах расчета неэкспоненциальных сетей массового обслуживания / Г.П. Башарин и др. // Вопросы кибернетики. Проблемы теории вычислительных сетей. М.: ВИНИТИ, 1983. - С. 43-58.

5. Берсенев Г.Б. Анализ точности и работоспособности методов расчета терминальных сетей / Г.Б. Берсенев // Интеллектуальные и информационные системы: Материалы межрегиональной научно-технической конференции. — Тула, ТулГУ, 2004. С. 73 - 76.

6. Берсенев Г.Б. Инструментарий для анализа производительности масштабируемых программных систем / Г.Б. Берсенев, Д.И. Малинин // Известия Тульского государственного университета. Технические науки. Выпуск 3. Тула: ТулГУ, 2008. - С. 110 - 116.

7. Берсенев Г.Б. Обобщенная модель узла с ограниченной очередью / Г.Б. Берсенев // Вестник ТулГУ. Серия "Выч. техника". Вып. 1. Тула: ТулГУ, 2007. - С. 88 - 92.

8. Берсенев Г.Б. Построение и анализ моделей ВС аналитическими, имитационными и аналитико-имитационными методами / Г.Б. Берсенев, П.Н. Шкатов, А.А. Морозов // Алгоритмы и структуры специализир. вычисл. систем. Тула, ТПИ, 1981. - С. 3-17.

9. Берсенев Г.Б. Приближенный анализ многоуровневых моделей вычислительных процессов / Г.Б. Берсенев, И.А. Липатов // Алгоритмы и структуры специализир. вычисл. систем. Тула, ТПИ, 1984. - С. 3 - 9.

10. Берсенев Г.Б. Системное проектирование программного обеспечения. Модели и методы принятия решений: учеб. пособие / Г.Б. Берсенев. — Тула : ТулГУ, 2001. 115 с.

11. Брукс Ф. Мифический человеко-месяц или как создаются программные системы: Пер. с англ. / Ф. Брукс. СПб.: Символ-Плюс, 1999.

12. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. 2-е изд.: Пер. с англ. / Г. Буч. М.: Издательство Бином, СПб.: Невский диалект, 1999.

13. Буч Г. Язык UML. Руководство пользователя / Г. Буч, Дж. Рамбо, А. Джекобсон. М. LVR Пресс, 2001.

14. Бэкон Д. Операционные системы / Д. Бэкон, Т. Харрис. СПб.: Питер; Киев: Издательская группа BHV, 2004. - 800 с.

15. Вендров A.M. Современные технологии создания программного обеспечения. Обзор электронный ресурс. / A.M. Вендров // Jet Info Online. #4, 2004. Режим доступа: http://www.jetinfo.ru/

16. Вишневский В.М. Теоретические основы проектирования компьютерных сетей / В.М. Вишневский. — М.: Техносфера, 2003. 512 с.

17. Гома X. UML. Проектирование систем реального времени, параллельных и распределенных приложении: Пер. с англ. / X. Гома. М.: ДМК Пресс, 2002. -704 с.

18. Кватрани Т. Визуальное моделирование с помощью Rational Rose 2002 и UML / Т. Кватрани. М.: Издательский дом "Вильяме", 2003. - 192 с.

19. Кенинг Д. Методы теории массового обслуживания: Пер. с нем. / Д. Кенинг, Д. Штоян. ; под ред. Г.П. Климова. М.: Радио и связь, 1981. - 128 с.

20. Кертен Р. Введение в QNX Neutrino 2. Руководство по программированию приложений реального времени в QNX Realtime Platform / Р. Кертен. СПб.: Петрополис, 2001. - 479 с.

21. Киллелиа П. Тюнинг веб-сервера. 2-е изд. / П. Киллелиа. СПб.: Питер, 2003.-528 с.

22. Клейнрок JI. Вычислительные системы с очередями / JI. Клейнрок. -М.: Мир, 1979.-600 с.

23. Крачтен Ф. Введение в Rational Unified Process, 2-е изд. / Ф. Крачтен. М. : Издат. "Вильяме", 2000.

24. Кузовлев В.И. Разработка САПР: В 10 кн. Кн. 8. Математические методы анализа производительности и надежности САПР: Практ. пособие // В.И. Кузовлев, П.Н. Шкатов; под. ред. А.В. Петрова. М.: Высш. шк., 1990. -144 с.

25. Майоров С.А. Основы теории вычислительных систем : учеб. пособие // С.А. Майоров и др.. М. : Высш. шк., 1978. - 408 с.

26. Лав Р. Разработка ядра Linux, 2-е издание. : Пер. с англ. / Р. Лав. -ООО "И.Д. Вильяме", 2006. 448 с.

27. Липаев В.В. Системное проектирование сложных программных средств для информационных систем / В.В. Липаев. М.: СИНТЕГ, 1999.

28. Мартин Дж. Системный анализ передачи данных / Дж. Мартин. -М. : Мир, т. 2, 1975.-431 с.

29. Назаров С.В. Измерительные средства и оптимизация вычислительных систем / С.В. Назаров, А.Г. Барсуков. М.: Радио и связь, 1990. - 248 с.

30. Назаров С.В. Операционные системы специализированных информационно-вычислительных комплексов: Теория построения и системного проектирования / С.В. Назаров. М.: Машиностроение, 1989. - 400 с.

31. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов / И.П. Норенков М.: Изд-во МГТУ им. Н. Э. Баумана, 2000.- 360 с.

32. Олифер Н.А. Исследование сетей массового обслуживания методами вложенных процессов / Н.А. Олифер, А.С. Байкенов // Алгоритмы и структуры специализир. вычисл. систем. Тула: ТПИ. 1985. С. 35 - 48.

33. Орлов С. Технологии разработки программного обеспечения: Учебник / С. Орлов. СПб.: Питер, 2002. - 464 с.

34. Петров А.В. CTAM/KJIACC язык построения обобщенных статистических моделей / А.В. Петров, B.C. Федоров, В.М. Черненький // Вычисл. техника. Вып. 3. М.: МВТУ, 1977. - С. 5 - 29.

35. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии / Ю.И. Рыжиков. СПб.: Корона принт; М.: Альтекс-А, 2004. - 384 с.

36. Саати Т. JI. Элементы теории массового обслуживания и ее приложения / Т. JI. Саати. -М.: Сов. радио, 1971. 520 с.

37. Смит К.У. Эффективные решения: практическое руководство по созданию гибкого и масштабируемого программного обеспечения / К.У. Смит, Л.Дж. Уильяме. М.: Издательский дом "Вильяме", 2003. - 448 с.

38. Смит У. Эффективные решения: проектирование распределенных систем и систем реального времени / У. Смит. СПб., "Вильяме", 2003. - 540 с.

39. Соколик А.В. Использование системы моделирования СТАМ/КЛАСС в ППП ПАМВС / А.В. Соколик, Ю.В. Куликов // Алгоритмы и структуры специализир. вычисл. систем. Тула, ТПИ, 1981. - С. 100-106.

40. Таненбаум Э. Распределенные системы. Принципы и парадигмы / Э. Таненбаум, М. ван. Стеен. СПб.: Питер, 2003. - 877 с.

41. Уолрэнд Дж. Введение в теорию сетей массового обслуживания / Дж. Уолрэнд. М.: Мир, 1993. - 336 с.

42. Феррари Д. Оценка производительности вычислительных систем: Пер. с англ. / Д. Феррари М.: Мир, 1981. - 576 с.

43. Шерр А. Анализ вычислительных систем с разделением времени / А. Шерр. -М.: Мир, 1970. 136 с.

44. Шкатов П.Н. Методы построения математических моделей оценки характеристик производительности ИВС АСУ / П.Н. Шкатов. -М.: "Высш. школа.", 1984.-206 с.

45. Шнепс М.А. Системы распределения информации. Методы расчета: Справ, пособие / М.А. Шнепс. -М: Связь, 1979. -344 с.

46. Штоян Д. Качественные свойства и оценки стохастических моделей / Д. Штоян. М.: Мир, 1979. - 268 с.

47. Alba Е. Parallel Evolutionary Algorithms Can Achieve Super-Linear Performance / E. Alba // Information Processing Letters. 2002. -Vol. 82, - P. 713.

48. Boehm B.W. Software Risk Management: Principles and Practice / B.W. Boehm // IEEE Software. -1991. Vol. 8, N l.-P. 32-41.

49. Buzacott J.A. Stochastic models of manufacturing systems / J.A. Buzacott, J.G. Shanthikumar. -Prentice Hall, Englewood Cliffs. -1993.

50. Garcia D. Performance model interchange format: Semantic validation / D. Garcia, C. Llado, C. Smith, and R. Puigjaner. -Universitat de les Illes Balears, Tech. Rep. -2006.

51. Cortellessa V. Deriving a Queueing Network based Performance Model from UML Diagrams / R. Cortellessa, R. Mirandola // Proc. Workshop on Software and Performance. -Ottawa, ACM, -2000.

52. Cortellessa V. From UML to Execution Graphs and Queueing Networks: Design and Implementation of the XML-based tool XPRIMAT / V. Cortellessa // Personal Communication, February 2004.

53. Gelenbe E. The behaviour of a single queue in a general queueing network / E. Gelenbe, G. Pujolle // Acta Informatica. -1976. Vol. 7, N 2. - P. 123-136.

54. Gu G. XSLT Transformation from UML Models to LQN Performance Models / G. Gu, D. Petriu // In Proc. Workshop on Software and Performance. -Rome: ACM. -2002.

55. Ivo Adan. Stochastic Models for Design and Planning Электронный ресурс. /1. Adan.-2002 Режим доступа : http://www.win.tue.nl/~iadan/sdp/

56. OMG, XML Metadata Interchange (XMI) 2.0, OMG Full Specification, formal/03-05-02, 2002.

57. Jain R. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling / R. Jain. -New York: NY, John Wiley. -1990.

58. Kramer W. Approximation for the delay in the queueing systems GI/GI/1 / W. Kramer, M. Langenbach-Belz // Congressbook, 8-th Internat. Teletraf. Congr. -Melbourne. -1976.

59. Marchall K.T. Some inequalities in queueing / K.T. Marchall // Operations Research. -1968. Vol. 16. - P. 651-665.

60. Menasce D.A. Two-Level Iterative Queueing Model of Software Contention / D.A. Menasce // Modeling Analysis and Simulation of Computer and Telecommunications Systems (MASCOTS 2002). Fort Worth: TX, -2002. - P. 267-280.

61. Petriu D. Analyzing Software Performance Requirements Specification for Performance / D. Petriu, C.M. Woodside // Proc. Workshop on Software and Performance. -Rome: ACM. -2002.

62. Petriu D.B. Scenario-Based Performance Engineering with UCMNav / D.B. Petriu, D. Amyot, M. Woodside // 11th SDL Forum (SDL'03), Stuttgart. -Germany. -2003. LNCS 2708, P. 18-35.

63. Petriu D. Software Performance Models from System Scenarios in Use Case Maps / D. Petriu, C.M. Woodside // Proc. Performance TOOLS. London. -2002.

64. Ramesh S. A Multilayer Client-Server Queuing Network Model with Synchronous and Asynchronous Messages / S. Ramesh, H.G. Perros // IEEE Tr. Software Eng. -2000. -Vol. 26, N 11. P. 1086-1100.

65. Reiser M. Accuracy of the diffusion approximation method for open queueing systems / M. Reiser, H. Kobayashi // IBM J. Res. Develop. -1974. V. 18, N 2. -P. 110-124.

66. Rolia J.A. The Method of Layers / J.A. Rolia, K.C. Sevcik // IEEE Tr. Software Eng. -1995. -Vol. 21. N 8. -P. 689-700.

67. Smith C.U. A performance model inter-change format / C.U. Smith, L.G. Williams //Journal of Systems and Software. -1999. -Vol. 49. N. 1.

68. Smith C.U. From UML models to software performance results: An SPE process based on XML interchange formats / C.U. Smith, C. Llado // Proc. Workshop on Software and Performance. -2005.

69. Smith C.U. Performance model interchange format (PMIF 2.0): XML definition and implementation / C.U. Smith, C. Llado // Proc. of the First1.ternational Conference on the Quantitative Evaluation of Systems. -2004. P. 3847.

70. Wu X. Performance Modeling from Software Components / X. Wu, C.M. Woodside // In Proc. Workshop on Software and Performance. -Redwood Shores, CA: ACM 488043. -2004.

71. Williams L.G. PASASM: An Architectural Approach to Fixing Software Problems / L.G. Williams, C.U. Smith // Proceedings of the Computer Measurement Group, Reno. -2002.

72. Williams L.G. QSEMSM: Quantitative Scalability Evaluation Method / L.G. Williams, C.U. Smith // Proceedings of the Computer Measurement Group, Reno. -2002.

73. Williams L.G. Web Application Scalability: A Model-Based Approach / L.G. Williams, C.U. Smith // Proceedings of the Computer Measurement Group. -Las Vegas. -2004.