Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Функционирование CPN






Рассмотрим работу раскрашенных сетей Петри. Как и вслучае обыкновенных СП. функционирование сети состоит в срабатывании переходов и происходящих вследствие этого изменениях маркировок.

Мы будем говорить, что переход t Є T может сработать, если выполняется условие

(2.13)

 

\/ p Є P: (m(p)≥ Σ E(a))^(G(t)=true).

\/ a Є AP

 

В первой скобке выражения (2.17) происходит поэлементное сравнение мультимножества, являющегося маркировкой позиции р с мультимножеством, которым помечены дуги, ведущие от р к t. Суммирование мультимножеств Е{а) связано с тем, что, как отмечалось в п. 5, два узла могут быть соединены несколькими дугами, и суммирование производится по всем таким дугам.

Во второй скобке записано условие отсутствия блокировки перехода t (см. п. 8 определения).

Если условие срабатывания перехода t выполняется, то он может сработать, при этом говорят, что выполнится шаг работы CPN. Отсчет шагов производится в дискретном времени θ = 0, 1, 2, …. Поэтому маркировку отдельных позиций т(р) и сети в целом М мы будем также привязывать ко времени и записывать соответственно в виде т(р, θ) и М(θ).

Изменение маркировки узла р €Т при осуществлении шага работы CPN рассчитывается по формуле

m(p, θ + 1) = m(p, θ)- ∑ Е(а)+ ∑ Е (а). (2.18)

VaeAP VaeАТ

В выражении (2.18) все слагаемые являются мультимножествами, и вычисления производятся в соответствии с правилами сложения и вычитания мультимножеств. Знаки суммирования мультимножеств используются в формуле по причине, которая уже пояснена выше: каждая пара узлов может быть связана несколькими дугами, а каждая дуга а€ А помечена отдельным выражением Е{а).

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

Пример. Приведем описание простой CPN, схема которой и начальная маркировка приведены на рисунке 2.5 а.

 
 

 

 


•Множества цветов:

type color С = (r, g, b); colorE = (е).

•Переменные:

Var x: color С; Var у: colorE.

•Множество позиций:

typeP = (pI, p2, p3).

•Множество переходов:

typeT = (t).

•Множество дуг А = Ар U А1, Ар = {а„ а2 }, А' = {а3},
a1 = p1 to t, а2 = p2 to t, a3=t to p3

type AP = (al, a2); type AT = (a3);

var a1. a2: ap; var a3: at;

•Цветовая функция

colorC if p € { p2, p3 }.

C(p) = colorE if p € { p1 }.

 

•Блокировочная функция всегда истинна:
G{t) = true.

• Функция Е(а), задающая выражения на дугах:

Е(а,)=1’е;

Е(а2) = if x = r then 1’е else

if x = g then 1’g else 1’b;

E{a,)-if(x = r and y = e)then 1’r

else if [x = g and у = e) then 1’g

else if(x = b and y = e) then 1’b.

• Функция инициализации I(p), задающая начальную маркировку т0 (pt) = (З'е); т02) = (1’r, 1’g, 1’b); т03) = (Ø).

Ниже приведено полное дерево маркировок рассмотренной сети.

θ =0 θ =1 θ =2 θ =3 Мо={3’е; 1’r; 1’8; 1’b; Ø }

t: x = r, y = e {2’e; 1‘g; 1’b; 1’r}

t: x = g, y = e {1’е; 1’b; 1’г; 1’g}

t: x = b, y = e {Ø; Ø; 1’r; 1’g; 1’b)

t: x = b, y = e {1’e; 1’g; 1’r; 1’b}

t: x = g, y = e {Ø; Ø; 1’r; 1’b; 1’g}

t: x = g, y = e {2’e; 1’r; 1’b; 1’g}

t; x = r, y = e {1’е; 1’b; 1’g; 1’r}

t: x = b, y = e {Ø; Ø; 1’ g; 1’r; 1’b}

t: x = b, y = e {1’е; 1’r; 1’g; -1’b}

t: x = r, y = e {Ø; Ø; 1’g; 1’b; 1’r}

t: x = b, y = e {2’e; 1’r; 1’g; 1’b}

t: x = r, y = e {1’e; 1’g; 1’b; 1’r}

t: x = g, y = e {Ø; Ø ; 1’b; 1’r; 1’g}

t: x = g, y = e {1’e; 1’r; 1’b; 1’g}

t: x = r, у = е {Ø; Ø: 1’b: 1’g; 1’r}

 

Поясним описание сети. Для позиции р1 разрешен цвет e, для позиций р2, р2 разрешены цвета r, g, b. Переход t может сработать, если в позиции р, находится хотя бы одна фишка цвета e и в позиции р2 находится хотя бы одна фишка цветов r, g, b.

В позицию р3 при срабатывании перехода пересылается та фишка, которая была извлечена из р2 при срабатывании перехода. Начальная маркировка - 3 фишки цвета е в позиции р1, по одной фишке всех цветов в позиции р2.

При работе сети переменная х принимает поочередно (в произвольном порядке) значения r, g, b, а переменная y -значение е. Работа сети продолжается до тех пор, пока все фишки из р2 не будут пересланы в р3. При этом позиции р1 и р2 оказываются пустыми. Дерево маркировок описывает все возможные варианты последовательности пересылки фишек.

Эквивалентная рассмотренной CPN обыкновенная сеть Петри приведена на рисунке 2.5 б.

Построив дерево маркировок этой сети, нетрудно убедиться, что оно структурно совпадает с рассмотренным выше деревом CPN. Однако раскрашенная сеть содержит больше

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

2.2.4. Расширения CPN

Как уже отмечалось в п. 2.1.5., использование сетей Петри в различных прикладных задачах может потребовать придания им дополнительных возможностей, что приводит к созданию расширений этих сетей. Некоторые расширения аналогичны рассмотренным в п 2.1.5, (например иерархические СРN), потребность в ряде других отсутствует, т.к. формализм СРN позволяет их описать (CPN с приоритетами, ингибиторные сети, самомодифицируемые сети).

Ниже мы рассмотрим одно важное расширение СРN, значительно расширяющее их моделирующие возможности.

CPN с временным механизмом

Существует ряд задач моделирования, в которых необходимо учитывать не только последовательность событий, но и время их наступления, а также продолжительность. Для этой цели предусмотрено расширение возможностей раскрашенных сетей Петри путем введения временного механизма (так называемых timed CPN [10]). В несколько упрощенном виде сущность такого расширения описана ниже.

А. В модель системы вводятся часы, показывающие глобальное время t. Обычно это время считается дискретным, т.е. означает номер такта, выдаваемого тактовым генератором системы моделирования. Глобальное время t отличается от времени θ, которое содержится в определении (2.10), поскольку θ есть номер шага работы CPN, а t изменяется независимо от работы сети.

Б. Ресурсы, перемещаемые в сети (фишки), могут получить временные метки. Такие ресурсы в общем виде задаются мультимножествами с временными метками (timed multi-sets), однако мы эту теорию не рассматриваем. Отметим лишь, что при описании множества цветов добавляются пометки timed, а переменные соответствующего типа снабжаются знаками @ (по-английски читается at, т.е. «во время»). Это означает, что переменная привязана к глобальному времени. После значка @ в квадратных скобках указывается значение глобального времени, в течение которого возможно использование данных фишек для срабатывания переходов, для которых они являются входными. При этом запись вида @[500] говорит о том, что фишка «включается» в момент t = 500 и далее готова для работы в сети, а запись @[500, 600] означает, что фишка может использоваться в диапазоне глобального времени 500 < t < 600.

Приведем пример.

type colorU = (p, q, r);

type color I — Integer;

type colorP = product U*I timed;

var x: colorP.

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

2'(р, 4)@[543].

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

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

Пусть в сети (рисунок 2.7) начальная маркировка такова: m1 =2'(p4)@[543], т2 =0. Выражения на дугах показаны на схеме. Глобальное время т = 543. Переход t может сработать, при этом он осуществит задержку передачи фишек в р2 на 12 единиц времени в соответствии с выражением на t. Таким образом, после срабатывания t получим маркировку

m1, m2 =2'(p, 4)@[555].

Пример CPN с временным механизмом приведен в п. 2.3.3.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.