Использование сетей Петри в математическом моделировании (стр. 3 из 5)
Состояние сети в данный момент времени определяется ее текущей маркировкой. Важная характеристика сети Петри - граф достижимости, с помощью которого описываются возможные варианты функционирования сети. Такой граф имеет вершины, которые являются возможными маркировками. Маркировки μ и μ' соединяются в направлении t дугой, помеченной символами перехода t
T или μt 
μ'. Маркировка μ' такая последовательность переходов: τ = t1, t2,..., tk является достижимой из маркировки μ, если существует, что μt1 μ't2 ... μ tk μ.N = (Р, Т, F, Н, μ0), где Р = {Р1, Р2, Р3, Р4, Р5},
T = {t1, t2, t3, t4, t5}, μ0 = (1, 1, 0, 0, 0).
Функции F и Н заданы матрицами
| P1 | P2 | P3 | P4 | P5 | ||
| H = | t1 | 0 | 0 | 1 | 2 | 0 |
| t2 | 1 | 0 | 0 | 0 | 1 | |
| t3 | 1 | 1 | 0 | 0 | 0 | |
| t4 | 0 | 0 | 0 | 1 | 0 | |
| t1 | t2 | t3 | t4 | |||
| F = | P1 | 1 | 0 | 0 | 0 | |
| P2 | 1 | 0 | 0 | 0 | ||
| P3 | 0 | 1 | 0 | 0 | ||
| P4 | 0 | 0 | 1 | 0 | ||
| P5 | 0 | 0 | 0 | 1 |
Фрагмент графа достижимости для сети Петри приведен на рис3.
[6]рис. 3
§4. Построение динамической модели на основе сети Петри
1. Проверка синтаксиса функциональной модели и вывод динамической модели.
Динамическая модель строится на основании функциональной модели и синтезируется пакетом Design/IDEF автоматически во время проверки синтаксиса функциональной модели. Для того, чтобы проверка стала возможной, необходимо разрешить эмуляцию CPN-моделей. Это делается путем установки метки CPN в окне Edit-Set Options-Methodology-Simulations. После установки метки в строке меню главного окна появляется новое меню CPN.
Для проверки синтаксиса необходимо вызвать команду "Check CPN Syntax" в данном меню и в появившемся окне указать параметры проверки. По окончании проверки появляется окно с отчетом, где указываются ошибки (если есть), а на функциональной модели появляются элементы сети Петри.
2. Краткие теоретические сведения о сетях Петри.
Сети Петри являются мощным инструментом исследования моделируемых систем благодаря их возможности описания многих классов дискретных, асинхронных, параллельных, распределенных, недетерминированных систем, благодаря наглядности представления их работы, развитому математическому и программному аппарату анализа.
Она представляет собой разновидность ориентированного графа, включающего в себя вершины двух типов: позиции и переходы. Позиции символизируют состояния и обозначаются как pi, а переходы обозначают собой действия (переходы из одного состояния в другое) и обозначаются как tj. Позиции и переходы соединены направленными дугами fk, каждая из которых имеет свой вес wk. Дуги также можно разделить на два типа: дуги, направленные от позиции к переходам, (p-t) и дуги, направленные от переходов к позициям (t-p). Исходя из этого, сеть Петри может быть формально представлена как совокупность множеств:
N = (P, T, F, W),
где P = {p1, p2… pn} - множество всех позиций (n - количество позиций),
T = {t1, t2… tm} - множество переходов (m - количество переходов),
F = (Fp-t, Ft-p) - множество дуг сети:
Fp-t = (pґt), Ft-p = (tґp) - множества дуг, ведущих соответственно от переходов к по-зициям и от позиций к переходам.
W = {w1, w2… wk} - множество весов дуг (k - количество дуг).
Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции pi, как mi, то маркировка всей сети: M = {m1, m2… mn}. Тогда полное определение сети Петри, включая данные о началь-ной маркировке, можно записать в виде:
PN = (N, M0), где М0 - начальная маркировка сети.
3. Отладка динамической модели.
Если в результате проверки синтаксиса функциональной модели были обнаружены ошибки, то их список будет выведен в окне отчета. В процессе устранения ошибок удобно переходить от одной ошибки к другой с помощью команды "Next Reference"/"Previous Ref-erence" меню Select. Все ошибки показываются выделением.
4. Надписывание позиций.
Для надписывания какой-либо позиции сети Петри необходимо сначала создать метку (команда Create Label), затем ее выделить и вызвать команду "Place Name" меню CPN. После этого достаточно указать надписываемый объект.
5. Надписывание переходов.
Роль переходов сети Петри играют функциональные блоки. По умолчанию в качестве имени перехода используется название блока. Однако, имеется возможность дать ему другое имя. Надписывание перехода производится так же, как и надписывание позиции.
После того, как переход подписан в левом нижнем углу блока появляется квадрат, который подтверждает, что блок подписан.
Аналогичным образом устанавливаются для перехода защита, кодовый сегмент и задержка.
Защита запрещает переход в соответствии с условиями на переменные, указанные в выражениях смежных дуг. Для ее установки требуется создать метку, содержащую выражение для защиты, затем командой "Guard" меню CPN она привязывается к переходу.
Кодовый сегмент определяет сегмент в коде Standard ML, который выполняется в эмуляторе Design/CPN всякий раз, когда будет срабатывать переход.
Задержка определяет время, которое характеризует продолжительность срабатывания перехода.
6. Надписывание дуг.
Каждая дуга может иметь свое имя и выражение, которые задаются как присоединяемые метки.
Для указания имени дуги необходимо создать новую метку, затем вызвать команду "Place Name" меню CPN и указать на маленький невидимый квадратик, принадлежащий функциональному блоку и расположенный в месте соединения блока и дуги.
Выражение дуги характеризует мультинабор фишек, которые двигаются по дуге при любом срабатывании перехода, являющегося входным для дуги. Присоединение осуществляется аналогично вызовом пункта "Arc Expression" меню CPN.
7. Удаление и скрытие динамической модели.
§5. Применение сетевых моделей для описания параллельных процессов
При анализе сети Петри основное внимание уделяется, как правило, трем направлениям.
Проблема достижимости. В сети Петри с начальной разметкой М0 требуется определить, достижима ли принципиально некоторая разметка М' из М0. С точки зрения исследования моделируемой системы, эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы.
Оценка живости переходов сети. Под живостью перехода понимают возможность его срабатывания в данной сети при начальной разметке М0. Анализ модели на свойство живости позволяет выявить невозможные состояния в моделируемой системе (например, неисполняемые ветви в программе).
Оценка безопасности сети. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одной метки в каждой из позиций. Для исследуемой системы это означает возможность функционирования ее в стационарном режиме. На основе анализа данного свойства могут быть определены требования к буферным накопителям в системе.
Итак, достоинства сетей Петри заключаются в следующем:
позволяют моделировать ПП всех возможных типов с учетом возможных конфликтов между ними;
обладают наглядностью и обеспечивают возможность автоматизированного анализа;
позволяют переходить от одного уровня детализации описания системы к другому (за счет раскрытия/закрытия переходов).
Вместе с тем, сети Петри имеют ряд недостатков, ограничивающих их возможности. Основной из них - время срабатывания перехода считается равным нулю, что не позволяет исследовать с помощью сетей Петри временные характеристики моделируемых систем. [8]
Е - сети. В результате развития аппарата сетей Петри был разработан ряд расширений. Одно из наиболее мощных - так называемые Е-сети (evaluation - "вычисления", "оценка") - "оценочные сети". В отличие от сетей Петри, в Е-сетях:
имеются несколько типов вершин-позиций: простые позиции, позиции-очереди, разрешающие позиции;
фишки (метки) могут снабжаться набором признаков (атрибутов);
с каждым переходом может быть связана ненулевая задержка и функция преобразования атрибутов фишек;
введены дополнительные виды вершин-переходов;
в любую позицию может входить не более одной дуги и выходить также не более одной.
В связи с этим любой переход может быть описан тройкой параметров:
dj= (S,t (dj),p (dj)).
Здесь S - тип перехода, t (dj) - функция задержки, отражающая длительность срабатывания перехода, р (dj) - функция преобразования атрибутов меток. Еще одно важное отличие Е-сетей от сетей Петри состоит в том, что метки интерпретируются как транзакты, перемещающиеся по сети, а вершины-переходы трактуются как устройства, выполняющие ту или иную обработку транзактов. Следствием такого подхода является требование: ни одна вершина-позиция Е-сети не может содержать более одной метки (то есть, любая Е-сеть изначально является безопасной). Базовые переходы Е-сети описаны ниже.