Презентация "Сети Петри"


Подписи к слайдам:
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ СИСТЕМ

ТЕМА 4. СЕТИ ПЕТРИ

  • Особенности сетей Петри и области их применения
  • Основные определения. Способы задания сетей Петри
  • Функционирование сетей Петри
  • Свойства сетей Петри
  • Анализ сетей Петри
  • Подклассы и расширения сетей Петри

1 Особенности сетей Петри и области их применения

  • Теория сетей Петри зародилась в 1962 году.
  • Сети Петри разрабатывались специально для моделирования тех систем, которые содержат взаимодействующие параллельные компоненты. Впервые сети Петри предложил Карл Адам Петри. В своей докторской диссертации "Kommunikation mit Automaten" ("Связь автоматов") Петри сформулировал основные понятия теории связи асинхронных компонент вычислительной системы. В частности, он подробно рассмотрел описание причинных связей между событиями. Его диссертация посвящена главным образом теоретической разработке основных понятий, с которых начали развитие сети Петри.

  • Работа Петри привлекла внимание сотрудников из проекта Information System Theory (Теория информационных систем) фирмы Applied Data Research (ADR). Ими была развита большая часть начал теории, предложены обозначения и представления сетей Петри; показали, как сети Петри можно применить к анализу и моделированию систем, включающих параллельные компоненты.
  • В настоящее время сети Петри являются распространенной моделью, позволяющей описывать структуру и взаимодействие параллельно действующих объектов и процессов.
  • Достоинства аппарата сетей Петри:
  • 1) Сети Петри позволяют моделировать асинхронность и недетерминизм параллельных, независимых событий, параллелизм конвейерного типа, конфликтные ситуации между процессами.

  • 2) Сети Петри позволяют описывать как типовые ситуации в дискретных подсистемах, так и общую динамику работы сложной асинхронной системы.
  • 3) Сети Петри позволяют производить иерархическую детализацию программных и аппаратных подсистем модели, производить совместное отображение структуры управления и потоков данных.
  • 4) В последние годы появился ряда классов сетей, ориентированных на моделирование сложных систем с учетом таких факторов, как приоритетность процессов (сети с проверкой на нуль, приоритетные сети), временные параметры событий (сети Мерлина, временные сети), совместного отображения структуры управления и потоков данных (Е-сети).

2 Основные определения. Способы задания сетей Петри

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

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

  • Графическое представление сети Петри
  • Множество позиций P = {p1, p2, p3, p4}
  • Множество переходов T = {t1, t2, t3 }
  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3

  • Начальная маркировка сети обозначается вектором
  • - определяют для каждой позиции pi количество фишек в этой позиции.
  • Начальная маркировка сети μ0 = [3 1 3 2].
  • Как и любой граф, сеть Петри может быть задана графическим, аналитическим и матричным способами.
  • При аналитическом способе сеть Петри задается как C = (P,T,F,H,μ0), где, кроме множеств позиций Р и переходов Т, задаются входная F и выходная Н функции.
  • Через F(tj) обозначается множество входных позиций, а через H(tj) – множество выходных позиций перехода tj; μ0 – начальная маркировка сети.

  • F(t1) = {p1, p2}, H(t1) = {p1, p3 },
  • F(t2) = {p4}, H(t2) = {p2, p2, p3},
  • F(t3) = {p3}, H(t3) = {p4 }.
  • μ0 [3 1 3 2]
  • Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = (P,T,D–,D+,μ0). Здесь D– и D+матрицы входных и выходных инциденций соответственно размером m × n, где m – число переходов и n – число позиций.
  • Элемент dij– матрицы D– равен кратности дуг, входящих в i-й переход из j-й позиции.
  • Элемент dij+ матрицы D+ равен кратности дуг, выходящих из i-ro перехода в j-ю позицию.

  • Для рассматриваемой сети Петри
  • Матрица D = D+ – D - - матрица инцидентности сети Петри

3 Функционирование сетей Петри

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

  • Необходимое условие срабатывания перехода ti:
  • Каждая из его входных позиций должна иметь не меньше фишек, чем число дуг из этой позиции в переход, т. е.
  • Переход ti, для которого выполняется данное условие, называется разрешенным.
  • В результате срабатывания перехода ti из всякой входной позиции pj перехода ti удаляется столько фишек, сколько дуг ведет из pj в ti, а в каждую выходную позицию pk помещается столько фишек, сколько дуг ведет из ti в pk.
  • Переходы ti могут срабатывать в любом порядке, возникающий порядок появления событий не однозначен. Разрешенные переходы не влияют друг на друга.

  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3

  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3

При начальной маркировке μ0 =[3 1 3 2] сети Петри разрешенными являются все переходы t1, t2, и t3.

  • При начальной маркировке μ0 =[3 1 3 2] сети Петри разрешенными являются все переходы t1, t2, и t3.
  • Условие срабатывания перехода t1 в имеющейся маркировке μ записывается следующим образом:
  • где eT[i] – вектор-строка, компоненты которого соответствуют переходам и все равны нулю, за исключением i-й, которая равна единице.
  • Срабатывание перехода рассматривается как мгновенное событие, занимающее нулевое время.
  • Проверим условие срабатывания перехода t1, t2, и t3.

Переход t1

  • Переход t1
  • [μ0] ≥ [100]* D– = [100] ·
  • [3 1 3 2][1100]условие выполняется, переход разрешен.
  • Векторы сравниваются по каждой из составляющих.
  • В результате срабатывания ti возникает новая маркировка

  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • Начальная маркировка
  • Срабатывание перехода t1

Переход t2

  • Переход t2
  • [μ0] ≥ [010]* D– = [010] ·
  • [3132][0001]условие выполняется, переход разрешен.
  •  
  • Новая маркировка при срабатывании перехода t2 равна:

  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • Начальная маркировка
  • Срабатывание перехода t2

Переход t3

  • Переход t3
  • [μ0] ≥ [001]* D– = [001] ·
  • [3132][0010]условие выполняется, переход разрешен.
  • Новая маркировка при срабатывании перехода t3 равна:

  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • P1
  • P2
  • P3
  • P4
  • t1
  • t2
  • t3
  • Начальная маркировка
  • Срабатывание перехода t3

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

  • После срабатывания перехода, имеющего несколько выходных позиций, все позиции получают метки, т.e. происходит распараллеливание процесса, и активизированные параллельные участки могут выполняться независимо.
  • Сети Петри предусматривают также конфликтные состояния, когда необходимо запретить одновременное развитие нескольких процессов.
  • Переходы t1 и t2 находятся в конфликте: запуск одного из них удаляет фишку из pi и тем самым запрещает другой.

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

  • Ограниченность. Это свойство связано с введением ограничений на число меток в позициях.
  • Позиция pi называется k-ограниченной, если количество фишек в ней не может превышать целого числа k, т. е.
  • Сеть Петри называется ограниченной, если все ее позиции ограничены.
  • Безопасность. Позиция сети Петри называется безопасной, если число фишек в ней никогда не превышает единицы. Сеть Петри безопасна, если безопасны все ее позиции. Это свойство важно при интерпретации позиций как простых условий: если в позиции есть фишка, то условие выполняется, если нет, то не выполняется. Безопасную позицию можно реализовать одним триггером.

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

  • Сохраняемость.
  • Сеть Петри С = (P, T, F, H, μ0) называется строго сохраняющей, если сумма фишек по всем позициям остается строго постоянной в процессе выполнения сети, т. е. для всех возможных маркировок μ'
  • Живость.
  • Под живостью перехода ti понимают принципиальную возможность его срабатывания при функционировании сети Петри. Тупик в сети Петри – это переход (или множество переходов), который в имеющейся маркировке μ' и в последующих достижимых из μ' маркировках не разрешен.

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

  • Достижимость.
  • Свойство достижимости используется при установлении возможности возникновения некоторой ситуации в системе.
  • Пусть проверяемая ситуация описывается разметкой μ'. Возникает задача: достижима ли маркировка μ' из начальной маркировки μ0 данной сети Петри.
  • Задача достижимости является одной из наиболее важных задач анализа сетей Петри.

5 Анализ сетей Петри

  • Основная задача анализа сетей Петри – задача достижимости: достижима ли маркировка μ' из начальной маркировки μ0 данной сети Петри.
  • Первый основан на построении дерева достижимости. Дерево достижимости – это ориентированное корневое дерево, вершинам которого, соответствуют возможные маркировки, а дугам – переходы.
  • Начальная маркировка соответствует корню дерева. Из него исходят дуги, соответствующие разрешенным переходам.
  • На каждом шаге строится очередной ярус дерева. Дерево представляет все возможные последовательности запусков переходов. Всякий путь, начинающийся в корне, соответствует допустимой последовательности переходов.

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

  • Другой подход к анализу сетей Петри называется матричным и основан на их матричном представлении.
  • Пусть осуществляется последовательность срабатываний переходов
  • В результате получится маркировка
  • – вектор целых положительных чисел, r-й элемент которого показывает сколько раз сработал переход tir в цепочке срабатываний, переводящей из μ0 в μ‘.

Для того чтобы существовала последовательность срабатываний σ, которая приводит из μ0 в μ', необходимо, чтобы вектор f(σ) являлся неотрицательным целым решением матричного уравнения

  • Для того чтобы существовала последовательность срабатываний σ, которая приводит из μ0 в μ', необходимо, чтобы вектор f(σ) являлся неотрицательным целым решением матричного уравнения
  • Если это уравнение не имеет решений, разметка μ' является недостижимой на данной сети из μ0.
  • Недоcтатки матричного анализа в том, что вектор срабатывания f(σ) не дает информации о порядке срабатывания переходов, кроме того, возможны недействительные решения уравнения, т. е. получаем некоторую последовательность переходов, которая не возможна.

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

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

  • Система имеет решение x1 = 2; x2 = 1; x3 = 2.
  • Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переход t1 срабатывает два раза, переход t2 срабатывает один раз, переход t3 - два раза.

6 Подклассы и расширения сетей Петри

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

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

  • К подклассу устойчивых сетей Петри относятся сети, которые обладают следующим свойством: если при любой маркировке μ два любых перехода ti и tj оказываются разрешенными, то срабатывание одного из них не исключает возможности срабатывания другого перехода.
  • Временные сети Петри позволяют отразить в модели временные параметры системы. Если моделируемое событие имеет отличную от нуля длительность, как например, событие «задание обрабатывается», то оно представляется в виде двух мгновенных событий типа «начало события», «конец события» и условия «событие происходит» .
  • Считается, что события происходят неодновременно. Позиции во временных сетях взвешиваются временем выполнения.

  • Раскрашенные сети Петри характеризуются тем, что каждой фишке в позициях сети сопоставляется определенный признак (цвет). Это позволяет задавать различные типы условий, объектов или ресурсов, которые характеризуют состояние системы.
  • Для срабатывания перехода ti его входная позиция должна содержать метки определенного цвета, которым помечается дуга, направленная от позиции к переходу ti.
  • Раскрашенные сети Петри позволяют уменьшить размерность графа при моделировании сложных систем.
  • Е-сети, или оценочные сети – наиболее мощное расширение сетей Петри, являющееся средством описания моделей функционирования вычислительных систем. В Е-сетях учитывается фактор времени, усложнена логика работы переходов, введены различные операции над метками.