Тема 2.1. Сетевая объектная модель – сеть Петри

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

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

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

Кружки (позиции, места) - соответствуют условиям, барьеры (переходы) - соответствуют событиям.

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

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

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

Условие может быть одновременно и входным и выходным для некоторого события.

Условие имеет емкость:

- условие не выполнено (емкость = 0)

- условие выполнено (емкость = 1)

- условие выполнено с n-кратным запасом (емкость = n, n – целое, n > 0).

Примеры условий:

- наличие данного для операции в программе;

- состояние некоторого регистра в устройстве ЭВМ;

- наличие деталей в конвейере и т.п.

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

Емкость условия указывается точками или числами в кружках. В этом случае говорят, что условие маркировано (размечено).

Пример графического представления сети Петри приведен на рис.2.1.

Рис.2.1. Пример графического представления сети Петри

Формально сеть Петри можно определить следующим образом:

Определение 2.1. Сетью Петри называется пятерка

À = <P, T, F, W, M₀>, где

Р = {p₁,..., p_n} – конечное непустое множество условий;

T = {t₁,..., t_m} – конечное непустое множество событий;

F Í P ´ T È T ´ P - отношение инцидентности;

W – функция кратности дуг: F ® N, N – множество натуральных чисел;

М₀ - функция начальной разметки: Р ® N È {0}.

Функция кратности дуг W сопоставляет каждой дуге число n>0 (кратность дуги). Если n>1, то в графическом представлении сети число n выписывается рядом с короткой чертой, пересекающей дугу. Часто такая дуга может заменяться пучком из n дуг, соединяющих соответствующие элементы сети. Принято дугу, кратность которой равна 1, никак не помечать.

Сеть, в которой имеют место только дуги кратности 1, называют ординарной (см. рис.2.1).

Функция начальной разметки M₀ сопоставляет каждому месту p Î P некоторое число M(p) Î N È {0} (разметка места).

Разметкой сети À называется функция М: Р ® N È {0}.

Если все места сети À считать строго упорядоченными, то разметку сети (в том числе и начальную) можно задать как вектор чисел M = (m₁, m₂,…, m_n) такой, что для любого i, 1£ i £ n, m_i =M(p_i).

На основе отношения инцидентности F и функции кратности дуг W можно ввести функцию инцидентности F: P ´ T È T ´ P ® N È {0}, которая определяется как

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

Обозначим:

I(t) = {pÎP | F(p,t) = n}- множество условий, влияющих на события;

O(t) = {pÎP | F(t,p) = n}- множество условий, зависящих от события;

I(p) = {tÎT | F(t,p) = n}- множество событий, влияющих на условия;

O(p) = {tÎT | F(p,t) = n}- множество событий, зависящих от условия.

Определение 2.2. Событие t_i возможно при разметке М, если для любого p_j Î I(t_i) (условия, влияющего на событие) M(p_j) ³ F(p_j, t_i).

Определение 2.3. Реализация (срабатывание) события t_i есть смена разметки М, при которой оно возможно, разметкой М’ по следующему правилу:

M’(p_j) = M(p_j) - F(p_j, t_i) + F(t_i, p_j), p_jÎP.

Будем говорить, что разметка М’ следует за разметкой М и записывать этот факт М М’.

Определение 2.4. Множество событий T’ Í T совместно возможно при разметке М, если для любого p_j Î I(t_i):

M(p_j) ³ F(p_j, t_i), t_i Î T’,

M (p_j) - (F (p_j, t_i) - F (t_i, p_j)) ³ 0, p_jÎP.

Определение 2.5. Реализацией множества событий Т’ Í T будем называть смену разметки М, при которой Т’ совместно возможны, разметкой М’ по следующему правилу:

M’(p_j) = M(p_j) - F (p_j, t_i) + F (t_i, p_j), p_j Î P

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

Рис.2.2. Пример функционирования сети Петри

Пояснение.

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

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

Невозможное событие наступить не может.

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

В приведенном выше примере события t₁ и t₂ являются возможными, но после реализации одного из них, например t₂, другое t₁ становится невозможным.

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

Конец пояснения.

Обозначим через R(À) множество всех разметок сети À, достижимых от разметки М₀ (включая М₀).

Возможные изменения разметок в сети, происходящие в результате срабатывания ее переходов, удобно изображать в виде графа разметок. Граф разметок – это ориентированный граф, множество вершин которого образовано множеством R(À) –достижимых в À разметок.

Пример 2.1. Рассмотрим сеть, заданную графически на рис.2.3, и построим для нее граф разметок (рис.2.4).

Рис. 2.3. Сеть Петри для примера 2.1.

t₁ t₂

t₁ t₂

t₁ t₂ t₃

t₁ t₂ t₃

t₁ t₂ t₃ t₃

t₁ t₃ t₃

0,3,1,1

.....

t₃ t₃

.....

Рис.2.4. Граф разметок сети Петри в примере 2.1.

Конец примера.

Определение 2.6. Разметку М, при которой ни одно из событий сети À невозможно, будем называть тупиковой.

Определение 2.7. Разметка М* достижима в сети À от разметки М, если существует последовательность следующих друг за другом маркировок (разметок) от М к М*.