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

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

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

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

Сети Петри как средство формализации дискретно-событийных процессов управления
Преимущества сетей Петри
Высокий уровень формализации дискретно-событийных систем
Аналитическое исследование свойств модели
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 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теория временных сетей Петри
Классификация, исследование свойств
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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ООП и сети Петри
Блочная структура сети Петри
[Ямпольський Л.С., Лавров О.А. Штучний інтелект у плануванні та управлінні виробництвом. – К.:Вища шк., 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. ]
“При проектировании сложной программной системы необходимо составлять ее из небольших подсистем, каждую из которых можно отладить независимо от других.”
Гради Буч

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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