'

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПЕТРИ-ОБЪЕКТНОГО МОДЕЛИРОВАНИЯ СИСТЕМ

Понравилась презентация – покажи это...





Слайд 0

Стеценко Инна Вячеславовна к.т.н., доцент кафедры системного анализа и методов принятия решений Черкасского государственного технологического университета, соискатель доктора технических наук Института проблем математических машин и систем Научный консультант д.т.н., проф. Литвинов В.В. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПЕТРИ-ОБЪЕКТНОГО МОДЕЛИРОВАНИЯ СИСТЕМ


Слайд 1

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


Слайд 2

Аналитические: Теория динамических систем (Mathcad, Matlab) Теория автоматического управления (Simulink) Системная динамика (Vensim, Powersim) Теория случайных процессов Логико-динамические системы Теория цифровых автоматов Теория базовых сетей Петри Имитационные: Имитационное моделирование (Simula, GPSS, Arena) Агентное моделирование (AnyLogic) Петри-имитаторы (CPN, POSES++) Технологии моделирования систем Непрерывные модели Дискретные модели


Слайд 3

Технологии моделирования Технологии аналитического моделирования Технологии имитационного моделирования Проблемно-ориен-тированные системы имитационного моделирования Объектно-ориентированный язык Simula Объектно-ориентированное программирование Системы компьютерной математики Технологии программирования Математические методы Численные методы


Слайд 4

Сети Петри как средство формализации дискретно-событийных процессов управления Преимущества сетей Петри Высокий уровень формализации дискретно-событийных систем Аналитическое исследование свойств модели Murata Т. Petri nets: Properties, Analysis and Applications // Proceedings of the IEEE. - April, 1989. - vol.77, No.44. – P. 541-580. Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Мир, 1984. – 264 с. Котов В.Е. Сети Петри. - М.: Наука, 1984. - 158 с. Зайцев Д.А. Инварианты временных сетей Петри // Кибернетика и системный анализ. – 2004. - №2. - С.92-106. Возможность применения к немарковским процессам функционирования Haas P. J. Stochastic Petri nets : modelling, stability, simulation / Peter J. Haas — Springer series in operations research. – 2002. -– 529p. Возможность быстрого конструирования алгоритма имитации системы с большим количеством событий Вычислимость алгоритма имитации сети Петри гарантируется эквивалентностью приоритетной сети Петри машине Тьюринга Котов В.Е. Сети Петри. - М.: Наука, 1984. - 158 с.


Слайд 5

Базовые сети Петри Правило запуска переходов. Конфликтные переходы


Слайд 6

Базовые сети Петри


Слайд 7

Базовые сети Петри


Слайд 8

Базовые сети Петри


Слайд 9

Базовые сети Петри


Слайд 10

Базовые сети Петри


Слайд 11

Базовые сети Петри


Слайд 12

Базовые сети Петри


Слайд 13

Базовые сети Петри


Слайд 14

Базовые сети Петри


Слайд 15

Совместное использование ресурсов


Слайд 16

Базовые сети Петри с многоканальными переходами


Слайд 17

Базовые сети Петри с многоканальными переходами


Слайд 18

Базовые сети Петри с кратными связями Кратность дуги


Слайд 19

Базовые сети Петри с кратными связями


Слайд 20

- множество дуг - кратности дуг - множество переходов - множество позиций Математическое описание базовой сети Петри [Murata T. Petri Nets: Properties, Analysis and Applications. // Proceedings of IEEE. – 1989. - Vol.77, No.4. - P.541-580.] Базовая сеть Петри Условие запуска перехода Т сети Петри: Запуск перехода Т сети Петри:


Слайд 21

Матричные уравнения состояний базовой сети Петри Фундаментальное уравнение состояний базовой сети Петри: - вектор количества запусков переходов


Слайд 22

Теория базовых сетей Петри Классификация сетей Петри: безопасные, ординарные, автоматные и др. Аналитическое исследование свойств модели Murata Т. Petri nets: Properties, Analysis and Applications // Proceedings of the IEEE. - April, 1989. - vol.77, No.44. – P. 541-580. Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Мир, 1984. – 264 с. Матричные уравнения состояний, исследование свойств через исследование инвариантов поведения и инвариантов состояний Расширения сетей Петри: ингибиторные, приоритетные, синхронные, самомодифицирующиеся, раскрашенные сети Петри Вычислимость сети Петри гарантируется эквивалентностью приоритетной сети Петри и ингибиторной сети Петри машине Тьюринга Котов В.Е. Сети Петри. - М.: Наука, 1984. - 158 с.


Слайд 23

Временные сети Петри Переход с временной задержкой Занять ресурс 3 1 Освободить ресурс Ресурс свободен Обработать


Слайд 24

Временные сети Петри Переход с временной задержкой Занять ресурс 2 1 Освободить ресурс Ресурс свободен Обработать


Слайд 25

Временные сети Петри Переход с временной задержкой Занять ресурс 2 Освободить ресурс Ресурс свободен 1 Обработать


Слайд 26

Временные сети Петри Переход с временной задержкой Занять ресурс 2 1 Освободить ресурс Ресурс свободен 1 Обработать


Слайд 27

Временные сети Петри Переход с временной задержкой Обработать 30 1 Ресурс свободен t=2,5 Занять ресурс 30 1 Освободить ресурс Обработать Занять ресурс Освободить ресурс Обработать Ресурс свободен Обработать 30 t=10 30


Слайд 28

Временные сети Петри Переход с временной задержкой Обработать 14 16 Ресурс свободен t=2,5 Занять ресурс 14 Освободить ресурс 16 Обработать Занять ресурс 1 Освободить ресурс 14 Обработать Ресурс свободен Обработать 25 4 t=10 15


Слайд 29

Теория временных сетей Петри Классификация, исследование свойств Wang J. Timed Petri Nets: Theory and Application / J. Wang. - Kluwer Academic Publishers, USA Octоber, 1998. - 290p. Фундаментальные уравнения состояний детерминированной временной сети Петри, матричные уравнения состояний, исследование свойств через исследование инвариантов поведения и инвариантов состояний Зайцев Д.А. Инварианты временных сетей Петри // Кибернетика и системный анализ. – 2004. - №2. - С.92-106. Применения стохастической сети Петри к немарковским процессам функционирования Haas P. J. Stochastic Petri nets : modelling, stability, simulation / Peter J. Haas — Springer series in operations research. – 2002. -– 529p.


Слайд 30

Временные сети Петри с многоканальными переходами Многоканальный переход Обычный переход Обычный переход Обычный переход Обычный переход Обычный переход Многоканальный переход Ограничитель количества каналов Многоканальный переход


Слайд 31

Временные сети Петри с конфликтными переходами С равной вероятностью По значению приоритета С заданной вероятностью Принятие решения о допуске к пересдаче


Слайд 32

Временные сети Петри с информационными связями Количество задолженностей студента 3 Контроль задолженностей неуспешный Контроль задолженностей успешный 3 приоритет Прибытие авто Переезд перекрестка Есть зеленый свет в направлении движения Формализация процессов принятия решений Формализация процессов управления 1 1 1 1 Информационная связь t=0 t=0


Слайд 33

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


Слайд 34

Пример моделирования стохастической сетью Петри динамического управления распределением ресурсов Подсистема объекта управления 2 2 2 1 Общий ресурс 1 1 Очередь заданий А Количество выполненных заданий А Очередь заданий В Очередь заданий С Количество выполненных заданий В Количество выполненных заданий С


Слайд 35

Пример моделирования стохастической сетью Петри динамического управления распределением ресурсов Подсистема объекта управления Подсистема управления 2 2 2 1 Общий ресурс 1 1 Очередь заданий А Разница в количестве выполненных заданий А и других заданий Равное количество обработанных заданий А,В,С Очередь заданий В Очередь заданий С Разница в количестве выполненных заданий В и других заданий Сравнение количества выполненных заданий


Слайд 36

Пример моделирования стохастической сетью Петри динамического управления распределением ресурсов Подсистема объекта управления Подсистема управления 2 2 2 1 Общий ресурс 1 1 Р7 Р8 Очередь заданий А Разница в количестве выполненных заданий А и других заданий Равное количество обработанных заданий А,В,С 1 Очередь заданий В Очередь заданий С Разница в количестве выполненных заданий А и других заданий Сравнение количества выполненных заданий Принятие решения о блокировании задач А и С Принятие решения о снятии блокирования задач А и С


Слайд 37

Пример моделирования стохастической сетью Петри динамического управления распределением ресурсов Подсистема объекта управления Подсистема управления 2 2 2 1 Общий ресурс 1 1 Р7 Р8 Очередь заданий А Разница в количестве выполненных заданий А и других заданий Равное количество обработанных заданий А,В,С 1 Очередь заданий В Очередь заданий С Разница в количестве выполненных заданий В и других заданий Сравнение количества выполненных заданий Принятие решения о блокировании задач А и С Принятие решения о снятии блокирования задач А и С


Слайд 38

Уравнения состояний детерминированной временной сети Петри с конфликтными и многоканальными переходами [Зайцев Д.А. Инварианты временных сетей Петри // Кибернетика и системный анализ. – 2004. - №2. - С.92-106.] ,


Слайд 39

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


Слайд 40

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


Слайд 41

Преобразование сети Петри, соответствующее входу маркеров в переходы где


Слайд 42

Преобразование сети Петри, соответствующее m-кратному входу маркеров в переходы


Слайд 43

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


Слайд 44

Пример. Исследование параметров динамического управления распределением ресурсов Параметр «a» = кратность дуги, соединяющих позицию «Разница в количестве выполненных заданий А и других заданий» и переход «Сравнение количества выполненных заданий» = кратность дуги, соединяющих позицию «Разница в количестве выполненных заданий А и других заданий» и переход «Принятие решения о блокировании задач А и С» Параметр «b» = кратность дуги, соединяющих позицию «Разница в количестве выполненных заданий С и других заданий» и переход «Сравнение количества выполненных заданий» = кратность дуги, соединяющих позицию «Разница в количестве выполненных заданий С и других заданий» и переход «Принятие решения о блокировании задач А и С» Время выполнения задачи С = 1, задачи А =0,157, задачи В = 0,333.


Слайд 45

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


Слайд 46

Сравнение матричных уравнений состояний стохастической временной сети Петри с известными уравнениями состояний сети Петри ? Фундаментальное уравнение состояний детерминированной временной сети Петри ?


Слайд 47

Недостаток сети Петри


Слайд 48

ООП и сети Петри Блочная структура сети Петри [Ямпольський Л.С., Лавров О.А. Штучний інтелект у плануванні та управлінні виробництвом. – К.:Вища шк., 1995. - 255с. ] [Стеценко І.В., Бойко О.В. Система імітаційного моделювання засобами сіток Петрі // Математичні машини і системи. – Київ, 2009. – №1. – С.117-124. ] Функциональные подсети [Dmitriy A. Zaitsev Functional Petri net // Universite Paris Paris-Dauphine. - Cahier N 224. – mars 2005. – P.1-62.] Объектно-ориентированные сети Петри [Lakos C. Object Oriented Modeling with Object Petri Nets // Concurrent Object-Oriented Programming and Petri Nets. - 2001. - P. 1-37. ] [Lakos C., Keen C. LOOPN++: a new language for object-oriented Perti nets, Technical Report R94-4, Networking Research Group, Univesity of Tasmania,Australia, April 1994.] Иерархическая объектно-ориентированная сеть Петри [Hue Xu Timed Hierarchical object-oriented Petri net // Petri Net, Theory and Applications, Book edited by: Vedran Kordic. - I-Tech Education and Publishing, Vienna, Austria. - 2008. - P.253-280. ] Высокоуровневые сети Петри для описания ООП [Hong,J.E., Bae D.H. High-level Petri net for incremental specification of object-oriented system requirements // Institution of Engineering and Technology, IEEE Proceedings – Software. - 2001. - Vol. 148, No.1 - P.11-18. ] “При проектировании сложной программной системы необходимо составлять ее из небольших подсистем, каждую из которых можно отладить независимо от других.” Гради Буч


Слайд 49

Понятие Петри-объекта Поле Сеть Петри Поле Время моделирования Поле Текущий момент времени Метод Выполнить статистические вычисления Метод Выполнить событие: выход маркеров и вход маркеров в переходы, соответствующие текущему моменту времени Метод Вход маркеров в переходы Метод Выполнить специфические действия, соответствующие переходу Поле Момент времени ближайшего события Класс Петри-имитатор Петри-объект Метод Выполнить имитацию до момента времени time


Слайд 50

Понятие Петри-объектной модели Определение. Петри-объектной моделью называется модель, являющаяся результатом агрегирования Петри-объектов: Class C2 Class C1 Class С5 Class С7 Class С4 Class С6 PetriSim Class C3 Model Class С8 Class С9


Слайд 51

Связи между Петри-объектами


Слайд 52

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


Слайд 53

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


Слайд 54

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


Слайд 55

Следствие. Состояние Петри-объектной модели в каждый момент времени описывается состоянием ее Петри-объектов. Уравнения состояний Петри-объектной модели Уравнения состояний Петри-объектной модели


Слайд 56

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


Слайд 57

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


Слайд 58

Исследование эффективности алгоритма имитации Петри-объектной модели


Слайд 59

Исследование эффективности алгоритма имитации Петри-объектной модели при различной сложности объектов


Слайд 60

Петри-объектная модель - это средство формального описания систем, которое: имеет математическое описание, а следовательно, имеет большую степень абстракции и наиболее формализованное описание алгоритма имитации; 2) допускает не только имитационные методы исследования, но и аналитические методы; 3) позволяет создавать модели больших и сложных систем с наименьшими затратами времени и труда; 4) основывается на временной стохастической сети Петри, а значит, допускает наиболее детализированное описание дискретно-событийных процессов функционирования; 5) основывается на объектно-ориентированной технологии, а значит, допускает моделирование структуры больших систем и совместимость с другими информационными технологиями.


Слайд 61

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


Слайд 62

Петри-объектная модель системы управления распределенными вычислительными ресурсами Метапланировщик Локальный планировщик Локальный планировщик Локальный планировщик Архитектура двухуровневой грид-системы Часть доступного ресурса:


Слайд 63

Петри-объектная модель системы управления распределенными вычислительными ресурсами Количество активных пользователей ПОЛЬЗОВАТЕЛЬ А Потребность задания в ВР Задание, которое выполняется 1 Нет задания, которое выполняется


Слайд 64

Петри-объектная модель системы управления распределенными вычислительными ресурсами ЗАДАНИЕ Количество свободного виртуального ВР Количество активных пользователей ПОЛЬЗОВАТЕЛЬ Информация о доступном количестве виртуального ВР пользователя Потребность задания в ВР Задание, которое выполняется 1 Нет задания, которое выполняется Информация о доступном количестве виртуального ВР узла


Слайд 65

Петри-объектная модель системы управления распределенными вычислительными ресурсами ЗАДАНИЕ Количество свободного виртуального ВР Количество активных пользователей ПЛАНИРОВЩИК ПОЛЬЗОВАТЕЛЬ Информация о доступном количестве виртуального ВР пользователя Потребность задания в ВР Задание, которое выполняется 1 Нет задания, которое выполняется Информация о доступном количестве виртуального ВР узла


Слайд 66

Петри-объектная модель системы управления распределенными вычислительными ресурсами


Слайд 67

Сеть Петри-объекта «Планировщик»


Слайд 68

Java-реализация модели системы управления распределенными вычислительными ресурсами


Слайд 69

Результаты исследования влияния типа управления на эффективность функционирования системы


Слайд 70

Заключение Разработаны теоретические основы новой технологии моделирования систем, объединяющей в себе объектно-ориентированную технологию и технологию имитационного моделирования стохастической сетью Петри. Эффективность Петри-объектной технологии обеспечивается сокращением затрат труда на алгоритмическую реализацию модели системы и значительным повышением скорости вычислений модели. Формализация средствами Петри-объектного моделирования является мощным инструментом исследования сложных дискретно-событийных систем Дальнейшие исследования связаны с усовершенствованием библиотеки Java-классов Петри-объектного моделирования; разработкой графического интерфейса ввода сетей Петри-объектов; разработкой WEB-версии библиотеки java-классов Петри-объектного моделирования поиском эффективных инструментов исследования аналитических свойств модели на основе матричных уравнений; разработкой библиотеки Петри-объектного моделирования распределенных систем.


Слайд 71

Спасибо за внимание!


×

HTML:





Ссылка: