Задачи анализа СП: сохранение, активность, уровни активности.

 

 

22. Деревья достижимости и их построение, пример построения.

• Дерево достижимости представляет множество достижимости сети Петри

• Начальная маркировка сети Петри на рисунке – (1,0,0)

• В этой начальной маркировке разрешены два перехода: t₁ и t₂

• Поскольку мы хотим рассмотреть все множества достижимости, определим новые вершины в дереве достижимости для маркировок, получающихся в результате запуска каждого из этих двух переходов

• Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок

• Это (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки

 

 

• Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок.

• Из маркировки (1,1,0) можно снова запустить t₁ (получая (1,2,0)) и t₂

• (получая (0,2,1)); из (0,1,1) можно запустить t₃ (получая (0,0,1)).

• Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево.

• Заметим, что маркировка (0,0,1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут.

• Кроме того, необходимо отметить, что маркировка (0,1,1), порождаемая запуском t₂ в (0,2,1), была уже порождена непосредственно из начальной маркировки запуском t₂.

 

 

Ординарные сети Петри

• В определении сети Петри есть понятие кратности. Это функция W, которая и задает кратность дуг.

• В общем случае кратность дуги может быть любым неотрицательным числом, но если всё дуги имеют одну и ту же кратность 1, то сеть относится к подклассу ординарных сетей.

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

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

 

• Существует определенный алгоритм, который позволяет преобразовать классическую сеть Петри в ординарную.

• При преобразовании сохраняются все основные свойства сети Петри.

 

Ингибиторные сети Петри.

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

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

Ингибиторная сеть представляет собой сети Петри, в которой применяются ингибиторные дуги.

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

Кратность ингибиторных дуг всегда равна единице

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

 

Правило срабатывания переходов в ингибиторной сети модифицирует следующим образом:

Переход t может сработать при разметке μ, если каждая его входная позиция р, соединения с t «обычной» дугой с кратностью w, содержит не менее w фишек, а каждая входная позиция, соединённая с t ингибиторной дугой, имеет нулевую разметку.

В приведённом примере ингибиторной сети Петри имеется три ингибиторные дуги: из р₂ в t₀, из р₃ в t₁, и из р₆ в t₃. В соответствии с правилами срабатывания ингибиторных сетей Петри разрешены переходы в t₀, t₁, t₃, t₄.

 

Сети Петри с приоритетами

1) В сетях Петри если несколько переходов могут сработать, то срабатывает любой из них.

2) В реальных дискретных системах имеют место ситуации, когда из двух готовых работать устройств требуется запустить сначала одно, а затем второе.

3) Эти ситуации не моделируется в сетях Петри в силу принятого в них правила срабатывания нескольких готовых к срабатыванию переходов.

4) Введем множество приоритетов PR, элементы которого частично упорядочены некоторым отношением «меньше или равно». С каждым переходом t сети Петри свяжем его приоритет pr(t)? PR. Правило срабатывания перехода модифицируем, дополнив его условием:

 а) Переход t может сработать, если для любого другого перехода t’ этой сети, который может сработать по стандартному условию, pr(t’)≤pr(t)

 Другими словами, если несколько переходов готовы сработать, то срабатывает любой такой переход, приоритет которого не меньше приоритетов остальных готовых к срабатыванию переходов. Такую модификацию сети Петри называют «сетью с приоритетами».

В примере приоритеты расставлены следующим образом: pr(t0)=α, pr(t1) = β

Допустим, что α>β. Таким образом, переход t0 будет иметь более высокий приоритет, и пока он разрешен, переход t1 (который также разрешен) срабатывать не будет.

Срабатывает t1 только после того, как в p0 останется одна фишка, т.е. t0 разрешен не будет.

 

Временные сети Петри

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

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

Поэтому ввели временные сети Петри, отличие которых от обычной сети Петри состоит в ограничении перехода дополнительным временным условием.

При этом время рассматривается не как абсолютная величина, а как временные единицы, т.е. часы, секунды, наносекунды и т.д. (в зависимости от моделируемого процесса).

В основном они могут быть представлены двумя типами: сети Петри с жестким и мягким временем.

А) Сети Петри с жестким временем:

Для сети Петри с жестким временем временное ограничение представляет собой задержку λ при срабатывании перехода после того как переход станет доступным для срабатывания.

Кроме того, для модели сетей Петри с жестким временем переход должен срабатывать в указанный интервал времени (α,β), где α – нижний, а β – верхний предел срабатывания перехода, т.е. минимальное и максимальное время срабатывания перехода после того, как он стал доступным для выполнения.

В примере, каждый переход сети Петри обладает интервалом срабатывания. Например: [2,3] для t0 и задержкой λ_n. Множество, содержащее задержки переходов может выглядеть следующим образом: λ(t) = {3,1,1,0,2}

Б) Сети Петри с мягким временем:

Для сети Петри с мягким временем временное ограничение состоит в том, что срабатывание перехода осуществляется за определенное время.

Для этого каждому переходу сети Петри при его выполнении присваивается конкретное значение задержки λ. При этом интервал срабатывания во времени не задается.

Сети Петри с мягким и жестким временем – не единственные типы временных сетей Петри.
Во временных сетях Петри могут быть введены, кроме того, дополнительные условия: задержки могут быть присвоены дугам, позициям или даже фишкам, может быть добавлена временная синхронизация и т.п.

Стохастические сети Петри

 

Сети Петри с очередями.

Сети Петри с очередями отличаются от обычных сетей Петри введения позиции с очередями.

Позиции с очередями состоят из очереди и хранилища фишек, которые уже эту очередь простояли

Очередь работает так, в неё попадают фишки, которые приходят в позицию и какое-то время они «Обрабатываются» и не доступны. После завершения обслуживания, они переносятся в хранилище и снова доступны для совершения переходов

 

Раскрашенные сети Петри