Свойства сетей Петри

Кроме конкретных технических характеристик ВС сеть Петри позволяет оценивать общие системные свойства.

Основными свойствами сети Петри являются:

1. Ограниченность или K-ограниченность

2. Безопасность

3. Сохраняемость

4. Достижимость

5. Живость

1. Ограниченность (или K-ограниченность) имеет место, если число меток в любой позиции сети не может превысить значения К. При проектировании систем определение К позволяет обоснованно выбирать емкости накопителей. Возможность неограниченного роста числа меток свидетельствует об опасности неограниченного роста длин очередей.

Сеть Петри ограничена, если ограничены все ее позиции.

К – ограниченность - Это свойство систем характеризующее, что число ее состояний конечно. По сети Петри это характеризуется тем, что число маркеров в любой из позиции при функционировании системы не может превысить число К.

Если известны емкости всех позиций, и наибольшая из них kmax, то сеть называют kmax-ограниченной.

Ограниченная сеть Не ограниченная сеть

2. Безопасность — частный случай ограниченности, а именно это 1-ограниченность. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером.

3. Сохраняемость характеризуется постоянством загрузки ресурсов, т.е.

где — число маркеров в -й позиции, — весовой коэффициент.

Сеть Петри называют

сохраняющей, если

число циркулирующих

в ней объектов

постоянно.

Переход сети Петри называют тупиковым, если в процессе функционирования сеть может оказаться в состоянии, в котором этот переход заблокирован. Нетупиковый переход называют активным.

активность уровня 0, если он никогда не может быть активирован (пассивный переход);

активность уровня 1, если существует состояние (достижимое из начального), в котором он активирован;

активность уровня 2, если для всякого целого n существует последовательность срабатывания переходов, в которой данный переход присутствует по крайней мере n раз;

активность уровня 3, если существует бесконечная последовательность срабатывания переходов, в которой данный переход присутствует неограниченно часто;

активность уровня 4, если для любого достижимого состояния существует последовательность срабатываний, приводящая в такое состояние, в котором этот переход активирован (активный переход).

Пример сети всегда приходящей к тупиковой разметке.

Сеть никогда не "попадает в тупик "

Сеть, которая может остановиться, а может и нет

4. Достижимость. Состояние S достижимо в сети Петри, если существует цепочка срабатываний переходов, ведущая из начального состояния в S. Состояние S'=(P1'...Pn') покрывает состояние S"=(P1"...Pn"), если для каждого i=1,...,n имеет место Pi' Pi", т.е. имеет место S' S".

Задача достижимости (покрываемость) состоит в том, чтобы для данной сети и состояния S определить достижимо ли S (достижимо состояние, покрывающее S). Задачи достижимости и покрываемости можно рассматривать применительно к набору не всех, а лишь некоторых позиций, т.е. к подсостояниям сети Петри.

Достижимость -Множество маркировок в которой возможны переходы в процессе функционирования

Достижимость характеризуется возможностью достижения маркировки из состояния сети, характеризуемого маркировкой .

Достижимость – позволяет определить множество маркировок, в которые возможны переходы в процессе функционирования системы.

5. Живость сети Петри определяется возможностью срабатывания любого перехода при функционировании моделируемого объекта. Отсутствие живости означает либо избыточность аппаратуры в проектируемой системе, либо свидетельствует о возможности возникновения зацикливаний, тупиков, блокировок.

Живость системы -Это свойство системы характеризующее, что из любого состояния достижимого из начального возможен переход в любое другое достижимое состояние (или характеризует отсутствие в системе тупиков и зацикливаний).

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

В основе исследования перечисленных свойств сетей Петри лежит анализ достижимости.

Один из методов анализа достижимости любой маркировки из состояния — построение графа достижимости.

Начальная вершина графа отображает , а остальные вершины соответствуют маркировкам. Дуга из в означает событие и соответствует срабатыванию перехода.

В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построении графа можно не отображать все вершины, так как многие из них являются дублями.

Тупики обнаруживаются по отсутствию разрешенных переходов из какой-либо вершины, т.е. по наличию листьев — терминальных вершин. Неограниченный рост числа маркеров в какой-либо позиции свидетельствует о нарушениях ограниченности.

Пример 1

На рисунке вершины графа изображены в виде маркировок, дуги помечены срабатывающими

переходами. Сеть является

неограниченной и живой, так

как метки могут накапливаться

в позиции , срабатывают все

переходы, тупики отсутствуют.

Пример 2

Сеть, моделирующая

Двухпроцессорную

вычислительную систему

с общей памятью,

является безопасной,

живой, все разметки

достижимы.