Содержание к диссертации
Введение
1. Обзор моделей и методов анализа производительности программного обеспечения 11
1.1. Жизненный цикл программного продукта 11
1.2. Типовые модели процессов разработки программных продуктов 12
1.2.1. Каскадная модель 12
1.2.2. Итеративная модель 13
1.2.3. Инкрементальная модель 14
1.2.4. Эволюция модели 15
1.3. Возможность и актуальность анализа производительности 16
1.4. Методы анализа производительности 17
1.4.1. Измерительный метод 18
1.4.2. Аналитический метод 18
1.4.3. Имитационный метод... 19
1.4.4. Гибридные методы 20
1.5. Краткая характеристика моделей описания программ 21
1.5.1. Сети Петри 21
1.5.2. Конечные автоматы 24
1.5.3. Маркированные графы 24
1.5.4. P/V системы 25
1.5.5. Системы с сообщениями 25
1.5.6. Графы UCLA 26
1.5.7. Марковские модели 26
1.5.8. Модели взаимодействующих последовательных процессов 27
1.6. Понятие стохастической сети Петри 28
1.6.1. Методы образования подклассов сетей Петри 28
1.6.2. Стохастические сети Петри 29
1.6.3. Основные расширения стохастических сетей Петри 31
1.7. Обзор основных работ по моделированию на основе сетей Петри 36
1.7.1. Зарубежные авторы 36
1.7.2. Российские авторы 37
1.7.3. Источники информации о сетях Петри 38
1.8. Выводы по главе 1 39
2. Методы анализа программ с использованием Сетей Петри 40
2.1. Анализ программ на основе сетей Петри 40
2.1.1 Структурный анализ 41
2.1.2. Имитационное (событийное) моделирование 43
2.1.3. Анализ по пространству достижимых состояний 43
2.2. Операционные модели программ на основе стохастических сетей Петри 44
2.2.1. Задание нагрузки в ССП-модели 46
2.2.2. Моделирование программных конструкций с помощью ССП 49
2.3. Методика количественного анализа ССП на основе аппарата Марковских цепей 53
2.3.1. Переход от ССП модели к ЭМЦ модели 55
2.3.2. Переход от ЭМЦ модели к ПМЦ модели 62
2.4. Выводы по главе 2 72
3. Иерархическая система моделей на основе ССП .. 74
3.1. Требования к модели на основе ССП... 74
3.2. Формальное описание строго иерархической стохастической сети Петри 75
3.3. Преимущества строго иерархической модели 80
3.4. Недостатки строго иерархической модели 80
3.5. Обоснование корректности 81
3.6. Иерархическое моделирование 81
3.7. Методика проведения анализа 86
3.8. Проверка адекватности модели объекту анализа 87
3.9. Интеграция анализа производительности ПО в типовые процессы разработки 88
3.9.1. Каскадная модель 89
3.9.2. Итеративная модель 89
3.9.3. Инкрементальная модель 90
3.10. Выводы по главе 3 91
4. Программное обеспечение автоматизации анализа производительности 92
4.1. Описание пакета автоматизации анализа производительности программ CSA 1 92
4.1.1. Моделирование последовательных и параллельных процессов 92
4.1.2. Представление входных моделей 93
4.1.3. Описание программных компонент пакета анализа 97
4.1.4. Технические особенности пакета анализа 101
4.1.5. Недостатки пакета анализа 102
4.1.6. Пример использования пакета анализа 102
4.2. Требования к развитию средств автоматизации анализа моделей программ на основе СИССП 108
4.2.1. Область применения и ограничения 108
4.2.2. Поддержка описания модели 111
4.2.3. Интерпретация результатов 113
4.3. Проектирование средств автоматизации анализа моделей сиссп 113
4.3.1. Особенности проекта 113
4.3.2. Язык описания моделей 115
4.3.3. Общая концепция и технология разработки 115
4.3.4. Структурная схема проекта 117
4.4. Выводы по главе 4 118
5. Экспериментальное подтверждение моделей и методов ... 119
5.1. Модель информационного сервера системы биржевых новостей 119
5.1.1. Постановка задачи моделирования 120
5.1.2. Использование стохастической сети Петри 121
5.1.3. Использование строго иерархической стохастической сети Петри 123
5.1.4. Выводы, рекомендации и результаты 125
5.1.5. Модернизация программного обеспечения по результатам анализа 126
5.2. Модель неблокирующей системы управления свободной памятью 129
5.2.1. Постановка задачи моделирования 129
5.2.3. Описание и анализ модели 131
5.3. Выводы по главе 5 138
6. Заключение по работе 139
6.1. Выводы об эффективности анализа с использованием СИССП моделей 140
6.2. Практическое внедрение результатов работы 141
6.3. Направления развития анализа производительности программного обеспечения на основе СИССП 141
7. Список сокращений
8. Список литературы
- Возможность и актуальность анализа производительности
- Операционные модели программ на основе стохастических сетей Петри
- Формальное описание строго иерархической стохастической сети Петри
- Описание программных компонент пакета анализа
Возможность и актуальность анализа производительности
Гибридные методы являются совокупностью нескольких других методов. Наиболее распространены имитационно-аналитический и измерительно-аналитический подходы. Чаще всего гибридные методы применяются для прогноза (экстраполяции) параметров системы. В отличие от предыдущих методов, достоинства и недостатки гибридных методов очень индивидуальны.
Как правило, гибридные методы сочетают основные достоинства положенных в их основу базовых методов. Например, имитационно-аналитические методы дают неплохую точность моделирования при сохранении приемлемого времени анализа. Если мы имеем дело с вероятностной моделью, то она также является более компактной за счет статистического подхода к описанию нагрузки.
Основной недостаток гибридных методов это сужение области применения. Например, вероятностные модели накладывают ограничения на распределения параметров переходов между состояниями имитационной модели, что может приводить к отличию поведения модели от поведения реальной системы.
Существуют различия во мнениях исследователей по вопросам о том, какие модели должны сравниваться и как их сравнивать. Будем говорить [20], что класс моделей А является меньшим или равным по мощности моделирования (или включается в) классу В, если для любого данного экземпляра а класса А существует алгоритм построения экземпляра Ъ класса В, для которого верно, что:
1) каждая структурная компонента модели а представляется различимым (небольшим) множеством компонент модели Ь. Размер модели b (число элементов) отличается в худшем случае на мультипликативную константу САВ от размера модели а, причем константа определяется классами моделей А и В, а не конкретными экземплярами а и Ь.
2) любая последовательность действий в а может быть промоделирована последовательностью действий в Ь, с длиной последовательности в Ь, отличающейся не более чем на САв от длины последовательности в а.
3) модель b заходит в тупик только тогда, когда заходит в тупик модель а. Модель заходит в тупик, если все ее действия становятся невозможны.
Сети Петри являются удобным аппаратом, специально созданным для моделирования параллельных асинхронных процессов в дискретных системах. Эти модели отображают функционирование сложной системы в терминах "условие" и "событие". Каждому событию ставятся в соответствие две группы условий: условия готовности - условия, которые должны быть выполнены, чтобы событие могло произойти; условия завершения события - условия, которые возникают в результате того, что событие произошло. Поскольку многие процессы, реализуемые программами, относятся к данному виду процессов, то использование сетей Петри для моделирования поведения программ вполне целесообразно.
Формально сеть Петри представляется как набор из двух множеств Р и Т, двух двуместных функций F и Н и одноместной функции [1о
Графовым представлением сети Петри является ориентированный двудольный мультиграф с двумя типами вершин: вершины-позиции pj из Р и вершины-переходы t,-из Т. Вершины-позиции на графе изображаются кружками, вершины-переходы изображаются черточками. Дуги орграфа соответствуют входным и выходным функциям инциденций F и Н. Кратность дуги из позиции р в переход t равна F(p,t), кратность дуги из перехода t в позицию р равна H(t, р). Если F(p,t) = 0, или H(t, р) = 0, то дуги не существует. На графе маркеры (фишки) обозначаются точками в соответствующих позициях. Матричное представление сети Петри - это две матрицы инциденций F и І \ Н — \h..\ , элементами которых служат значения функций F и Н. Эта форма представления удобна для формального и машинного анализа сети. Среди достоинств аппарата сетей Петри можно указать следующие:
1) сети Петри позволяют моделировать асинхронность и недетерминизм независимых параллельных событий, параллелизм конвейерного типа, конфликтные взаимодействия между процессами.
2) как математическая модель сети Петри занимают промежуточное положение между конечными автоматами и машинами Тьюринга. При этом по выразительной мощности они значительно богаче автоматов и приближаются к машинам Тьюринга.
3) сети Петри включают возможности ряда других моделей, предложенных для параллельных систем, позволяя описывать как важные события в системах (распределение ресурсов, взаимные блокировки), так и общую динамику работы сложной асинхронной системы.
4) сети Петри допускают произвольную интерпретацию элементов модели как в смысле типа выполняемого фрагмента (выражения, операторы, подпрограммы, аппаратные преобразования информации), так и по уровню абстракции.
Весьма интересен взгляд [8] на сети Петри как на расширение моделей систем с очередями, которое включает возможность использования механизмов синхронизации, к чему теория очередей плохо приспособлена. Наиболее значительной проблемой для сетей Петри является экспоненциальный рост пространства достижимых состояний, что приводит к недостатку памяти моделирующей системы или приводит к бесконечно долгому решению.
Операционные модели программ на основе стохастических сетей Петри
Поведение модели, представленной в виде сети Петри, может быть проанализировано качественно или оценено количественно. Качественный анализ применим для любых моделей на основе сетей Петри, а количественный возможен только для некоторых вариантов расширенных сетей. В данной работе количественный анализ рассматривается только применительно к стохастическим сетям Петри [69,70,71]. Стохастическая сеть Петри определяет как структуру модели, так и ее нагрузку. Поскольку точность задания нагрузки в большой степени определяет точность модели в целом, то этой проблеме в главе уделено большое внимание. Предложены два подхода к построению ССП моделей программ: поведенческий и алгоритмический и для них рассмотрены основные варианты определения нагрузки. Далее представлены методики перехода от ССП модели к изоморфным моделям на основе эргодической и поглощающей цепей Маркова и методы расчета характеристик производительности на их основе.
При качественном анализе исследуются общие характеристики поведения модели, как правило, путем изучения пространства достижимых состояний данной модели для указанной начальной маркировки. Качественный анализ является незаменимым средством обнаружения конфликтных ситуаций для параллельных взаимодействующих процессов. В последнее время наблюдается распространение методов анализа от классических (достижимость, активность, безопасность) в сторону экспресс-анализа по исходной модели: линейные инварианты; поиск взаимных исключений, причинных, косвенных и структурных конфликтов. Большие надежды исследователи возлагают на различные методы редукции пространства состояний без потери сведений о поведении модели, что зачастую требует снижения модельной мощности сети.
В классической интерпретации функционирования сети Петри при существовании нескольких возбужденных переходов выбор перехода, который в данной разметке должен сработать, никак не регламентируется, что приводит к недетерминированному характеру поведения сети и отражению лишь причинно-следственных связей между событиями. Для расширения возможностей моделирования, учитывающих реальный характер процессов, в практику моделирования были введены так называемые временные сети Петри, в которых отдельным переходам было приписано время срабатывания в той или иной форме. Это позволило перейти к количественному анализу поведения моделей и расчету характеристик моделируемых систем.
Особую роль для количественного анализа играют временные стохастические сети Петри (ВССП), применение которых целесообразно для моделирования объектов, временные процессы который являются в общем случае стохастическими с известными законами распределения. Как правило, в существующих разновидностях ВССП принимается экспоненциальный закон распределения времени срабатывания переходов, что связано в первую очередь с простотой анализа таких ВССП и возможностью проверки результатов при использовании аппарата систем массового обслуживания. Подмена истинных законов распределения экспоненциальным может приводить к недопустимым погрешностям моделирования, а в ряде случаев - к качественно несостоятельным моделям, траектории которых не соответствуют реальным процессам в моделируемых объектах. Существуют также подходы [38], позволяющие применять ВССП с неэкспоненциальными временными переходами, однако, при этом накладываются некоторые ограничения на структурные свойства сетей с целью облегчения задач их анализа.
При описании объекта сетью Петри без учета ее начальной маркировки мы определяем структурный или статический компонент модели. За последние годы исследователями было проделано много попыток получить свойства сети Петри прямо из ее структуры. Интерес подогревается тем, что свойства, доказанные по структуре сети, являются корректными для любой маркировки. Данные методы структурного анализа делятся на два класса: методы линейной алгебры, которые работают с матричным описанием сети Петри, называемым матрицей инциденций;
В [39] рассмотрены некоторые шаблоны структурного анализа, в частности конфликты, путаницы, причинность и так далее. Сам конфликт представляет собой совместный доступ к ограниченному ресурсу, недостаточному для удовлетворения нужд одновременно двух или более потребителей данного ресурса. Срабатывание перехода, моделирующего одного потребителя, исключает срабатывание другого перехода. Конфликты бывают различных типов. Самый обычный - симметричный конфликт, когда срабатывание любого перехода исключает возможность срабатывания другого. Существует другой тип конфликтов - асимметричный, когда зависимость переходов неоднозначна [см. рис.2.1].
Это так называемые структурные конфликты. Есть также эффективный конфликт, когда зависимость выражается по количеству срабатываний переходов в маркировке при условиях срабатывания одного либо другого перехода.
Развитием структурного анализа является редукция сетей Петри [67,72] -эффективный метод структурных преобразований, направленных на уменьшение числа вершин сети Петри при сохранении ее поведенческих свойств. Основная идея метода редукции заключается в следующем: предложен набор правил, разрешающих уменьшить число вершин в сети Петри, если влияние исключенных из сети вершин на поведенческие свойства передается другим вершинам. Редукция позволяет упростить модель без потери ею своих свойств, и соответственно упростить проведение анализа. В качестве примера можно привести правило подстановки позиции, позволяющее уменьшить число позиций (условий) в модели и правило удаления эквивалентных переходов.
Как уже говорилось, событийная имитация позволяет получить параметры поведения системы настолько детально, насколько требуется экспериментатору, но за счет увеличения длительности эксперимент. Сети Петри не являются исключением и подтверждают это правило при больших размерах модели. Поэтому событийное моделирование имеет смысл применять в моделях небольшой топологической сложности [39] для получения оценок с приемлемой точностью. Но с другой стороны, событийное моделирование это единственный способ получения информации о поведении модели в случае невозможности ее аналитического решения из-за большого пространства достижимых состояний или специфики модели, но вопрос о моменте завершения событийного эксперимента и качестве результатов моделирования зачастую остается открытым.
Формальное описание строго иерархической стохастической сети Петри
При формировании модели на основе алгоритмического подхода предполагается, что программа представлена как псевдокод, SDL или UML схема. Представление программы на языке программирования также возможно, но приводит к сложной зависимости «платформа - транслятор - параметры» при определении параметров производительности отдельных конструкций. Так как псевдокод часто близок к используемому при реализации языку программирования, то и предлагаемые «алгоритмические» модели на основе сетей Петри находятся в сильной зависимости от вида используемых в языке конструкций. Согласно [73,74] можно выделить следующие классы языков программирования:
Декларативные и логические языки являются наиболее тяжелым вариантом для построения алгоритмических моделей, так как в общем случае взаимосвязь между программной конструкцией и временем ее выполнения очень неявная и зависит от многих факторов, включая размер программы или реализацию машины вывода. Поэтому для них целесообразнее использовать создание и анализ «поведенческой» модели, которая не зависит от языка программирования. Объектные и объектно-ориентированные языки несколько проще, но позднее (динамическое) связывание может значительно увеличивает модель для сложных иерархий классов. Представление функциональных языков также имеет свои особенности: например, рекурсия в LISP или возможность отложенных вычислений в Haskell приводят к дополнительным искусственным преобразованиям модели. Процедурные языки представляют наибольший практический интерес, так как эта группа состоит из так называемых «промышленных» языков (FORTRAN, COBOL, С и так далее) и они будут подробно рассмотрены далее.
Нагрузка или параметры потребления ресурсов (в нашем случае - время) есть составляющая часть модели, представленной стохастической сетью Петри. Именно задание значений [95] нагрузки для программного обеспечения и определяют специфику анализа программной составляющей по сравнению с аппаратной.
Предлагается нагрузку в модели можно делить на два вида: абсолютную и относительную. Абсолютная А нагрузка определяется количеством потребляемого ресурса при выполнении некоторого действия в моделируемой программе. Относительная R нагрузка определяется значениями абсолютной нагрузки, взвешенными вероятностями выбора ветвей выполнения программы.
Адекватные поведению программы значения параметров нагрузки в модели могут быть получены следующими методами:
1) Измерительным. Этот вариант является наиболее точным и наиболее трудоемким с практической точки зрения. Он основан на использовании программных или аппаратных мониторов для определения времени выполнения участков программы и частот их повторения, последующей статистической обработки данных.
2) Аналитическим. Это также достаточно точный вариант, предполагающий построение аналитической модели для определения нагрузки некоторого участка программы. Как правило, это узкоспециализированные модели, их сложность зависит от конечной цели анализа. В качестве примера можно привести модели на основе цепей Маркова, выполняемые по объектному коду низкого уровня и спецификации времени выполнения инструкций для данного процессора.
3) Имитационным. Как и в случае аналитического метода, данный подход основан на применении некоторой модели, но основным его преимуществом является возможность оценивать не только нагрузочные характеристики участка, но и вероятность выбора ветвей выполнения. 4) Экспертным оцениванием. В общем случае это самый неточный, но самый быстрый метод, может проводиться разными способами, чаще применяется для достаточно крупных подсистем или определения вероятности ветвлений, например, в случае возникновения ошибки.
Модели программ ввиду своей сложности редко строятся на основе только одного подхода. Время обработки критических для модели событий определяется с использованием измерений или аналитических моделей, остальная нагрузка может определяться экспертом. Отладка модели позволяет уточнить значения абсолютной или относительной нагрузки. Очень ценным источником информации является протокол (журнал) выполнения программы, анализ которого позволяет судить об возникающих ошибках и продолжительности выполнения участков программы.
Для определенности здесь и далее в качестве потребляемого программой ресурса будем рассматривать время. Тогда абсолютная нагрузка некоторого компонента модели определяется временем выполнения моделируемого им действия. Пусть действие выполняется за время Т, тогда моделирующий его переход необходимо нагрузить интенсивностью срабатывания
При моделировании операций с малой продолжительностью удобно задавать интервалы времени в долях секунды. Например, в [71] при моделировании выполнения программы на уровне инструкций RISC процессора, все интервалы считались в наносекундах, что давало весьма удобные значения нагрузки.
С другой стороны, до построения модели не всегда известно точное время выполнения той или иной инструкции. Тогда продолжительность выполнения операций можно оценивать в условных единицах относительно некоторой базовой продолжительности.
Описание программных компонент пакета анализа
Здесь и далее будут даны рекомендации и перечислены некоторые требования к средствам автоматизации анализа производительности при использовании моделей на основе СИССП. Это проделано в декларативной форме ввиду того, что раздел не является техническим заданием на разработку пакета анализа.
Как и первая версия программного пакета CSAI, проектируемая система будет применяться в обучении и экспериментальном моделировании [70,87]. Основные отличия этих двух областей состоят в следующем:
1) Применение для обучения требует возможности эксплуатации на наиболее распространенных операционных системах, что не является обязательным в случае экспериментального моделирования;
2) Применение для обучения требует простого в эксплуатации инструмента, желательно с развитыми графическими средствами, что не требуется во втором случае;
3) Экспериментальное моделирование требует надежной работы с большими моделями, что не так важно в обучении, где размеры модели редко превышают трехсот состояний в ПДС.
Операционные системы обладают различными ограничениями, известными или скрытыми, техническими или административными (например, лицензирование систем и средств разработки).
Для пакета CSA I пришлось обходить ограничение по объему памяти в 640К, используя транслятор WATCOM C/C++. Но такое простое решение возможно не во всех случаях. Например, созданная специально для обучения А. Танненбаумом операционная система MINIX плохо поддерживает современное аппаратное обеспечение и в целом обладает невысокой производительностью и ограниченным набором ПО. ОС Windows имеет как технические, так и административные ограничения, и, несомненно, является чемпионом по подводным камням, вероятно ввиду своей чрезмерной сложности. С одной стороны в ней нет многих механизмов взаимодействия между процессами, доступных в UNIX системах, а с другой - очень неприятные моменты, возникающие при работе с памятью, налагающие ограничения на размеры обрабатываемых матриц.
Ограничения по средствам обмена данными Потенциально высокая вычислительная сложность анализа моделей порождает необходимость разнесения различных фаз анализа на физически разные узлы сети обработки данных или даже распараллеливание процесса анализа. Одним из вопросов, решаемых при построении таких систем, является определение характеристик потоков данных и изучение возможных способов обмена данными между различными приложениями.
После проведенных исследований [91] удалось выяснить необходимость минимизации обмена данными между различными приложениями, так как ни один их изученных способов не обеспечивает обмена, сравнимого по порядку скорости с разделяемой памятью. Из приведенных на рис. 4.1 и 4.2 диаграмм видно, что при локальном обмене для малых объемов данных лучше всего подходит механизм очередей, а при больших порциях данных - совместно используемая память. С другой стороны, в случае физически разных узлов обработки данных, имеется возможность использовать только сокеты TCP/IP, а скорость обмена можно повысить, используя частные решения типа некопирующего обмена (zero copy TCP) и так далее.
После анализа применения серии программных пакетов был выбран один из наиболее удачных и доступных в виде исходных текстов The Reference Net Workshop - ReNew (http://www.renew.de). Это пакет является примером продуманного и достаточно удачного подхода, к реализации интерфейса. Но с другой стороны, при разработке и на начальных этапах эксплуатации графический интерфейс не является необходимостью, что было выяснено в процессе эксплуатации пакета CSAI.
Если стохастические сети Петри позволяют проводить описание только нисходящим методом, через осознание поведения программы как единого целого и последующую детализацию, то иерархические сети Петри по своей природе имеют некоторые преимущества. Поэтому в случае СИССП появляется возможность строить модель согласно поставленной задаче. Ниже мы рассмотрим два типовых случая и условия их применения, которые следует учитывать и поддерживать при разработке пакета автоматизации анализа.
Восходящий метод имеет смысл применять в следующих случаях: 1) Анализ низкого уровня, начиная от инструкций процессора [71]; 2) Построение максимально детальной модели для заданной архитектуры. Ввиду независимости уровней строго иерархической стохастической сети Петри высокая детализация не оказывает пагубного влияние на время оценки параметров модели и не скрывает структуры модели. Это предотвращает большое число возможных ошибок, так как в простых стохастических сетях бывает достаточно сложно обозначить части модели и сопоставить их с соответствующими частями моделируемой программы.
Пошаговая детализация особенно удачно подходит при анализе еще не существующего объекта, например оценивание проектных решений [7]. Постепенно, проект детализируется и развивается, согласно этой детализации переходы сети Петри верхнего уровня преобразуются в макропереходы, увеличивается сложность и точность модели. Полезной рекомендацией может служить введение масштабирующих коэффициентов, что позволяет значительно сократить по времени этап отладки и калибровки (отладки) модели, который можно начинать уже с получением первых данных от реальной программы.
Текущая версия пакета анализа CSA I поддерживает минимальный набор отчетов по результатам анализа, к тому же с фиксированным представлением. Наряду с возможностями получения времени и дисперсии потребления ресурса, пакет CSAII должен допускать создание отчетов с дополнительными качественными и количественными данными о модели как: живость; достижимость маркировок; частоты срабатывания того или иного перехода в конкретной маркировке; анализ модели на наличие конфликтов и блокировок и так далее.
В качестве рекомендации предлагается использовать реляционную базу данных [92] для хранения описаний моделей, их графов достижимости и других промежуточных результатов анализа. Это позволит использовать системы автоматической генерации отчетов для создания дополнительных данных об анализе модели.
