Моделирование систем / lec10
.pdfОсобенности сетей Петри и систем, моделируемых с их помощью:
параллелизм, или одновременность (сети Петри удобны для моделирования систем с распределенным управлением).
асинхронность (в сети Петри отсутствует измерение времени или течение времени. Сеть Петри содержит необходимую информацию для определения возможных последовательностей событий).
недетерминированность выполнения сети Петри (порядок появления событий один из возможных, выбор запускаемого перехода при нескольких разрешенных осуществляется недетерминировано, то есть случайно).
Запуск перехода и соответствующего события рассматривается как мгновенное событие, и возникновение двух событий одновременно невозможно.
Основными свойствами сети Петри являются:
ограниченность — число меток в любой позиции сети не может превысить некоторого значения K;
безопасность — частный случай ограниченности, K=1;
сохраняемость — постоянство загрузки ресурсов,
Ai i постоянна, где i — число маркеров
в i-ой позиции, Ai — весовой коэффициент;
достижимость — возможность перехода сети из одного заданного состояния (характеризуемого маркировкой) в другое;
живость — возможность срабатывания любого перехода при функционировании моделируемого объекта.
Воснове исследования перечисленных свойств лежит анализ достижимости.
Анализ достижимости. Дерево достижимости
Дерево достижимых разметок представляет собой ориентированный граф, множество вершин которого образовано множеством R(C, µ), причем из вершины в вершину
' ведет дуга, если существует переход tj T, такой, что δ (µ, tj) = µ’.
В общем случае дерево достижимых разметок может иметь бесконечное число вершин.
П р и м е р 1
Маркированная сеть Петри, для которой строится дерево достижимости
Первый шаг построения дерева достижимости
Начальная маркировка (1, 0, 0). При этой маркировке разрешены два перехода t1 и t2.
Второй шаг построения дерева достижимости
Третий шаг построения дерева достижимости
И т. д.
Алгоритм построения конечного дерева достижимости.
Каждая i-я вершина дерева связывается с расширенной разметкой (i). В расширенной разметке число меток в позиции может быть либо неотрицательным целым, либо бесконечно большим. Бесконечное число меток обозна-
чим символом . ( 1 , 1 )
Вершины классифицируются на 4 вида:
граничная, терминальная, дублирующая, внутренняя.
Граничными являются вершины, которые еще не обработаны алгоритмом.
Алгоритм начинает свою работу с задания начальной разметки. До тех пор, пока имеются граничные вершины, они обрабатываются алгоритмом.
Пусть x - граничная вершина, которую необходимо обработать, и с которой связана разметка (x).
1.Если для разметки (x) на один из переходов неразрешeн, т.е. (x) тупиковая разметка, то x терминальная вершина.
2.Если в дереве имеется другая вершина y, не являющаяся граничной, и с ней связана разметка (y)= (x), то вершина x дублирующая.
3.Для любого перехода tj, из множества T, разрешенных в разметке (x), создать новую вершину z дерева достижимости. Разметка (z), связанная с этой вершиной, определяется для каждой позиции рi следующим образом:
i.если (x)i= , то (z)i = ;
ii.если на пути из корня дерева в z есть вершина y такая, что
( y) ( (x),tj) и ( y)i ( (x)i,tj)
то (z)i= ;
iii. в в противном случае
(z)i ( (x)i,tj)