TVPS_posobie_13_06_2013

Пусть дана сеть С=(P, T, I, O) с начальной маркировкой 0. Требуется построить ординарную сеть С'=(Р', Т', I', О') с начальной маркировкой 0':

1) для рi	Р найти	n( pi ) max {#(t j , I ( pi )),# (t j ,O( pi ))};
		t j

2)каждой позиции рi Р в сети С' ставим в соответствие множество Р'(pi), состоящее из n(pi) позиций:

P' P'( pi ) , где P'( pi ) p1 , p 2 ,..., pn( pi )};

pi

3) в исходное множество переходов добавляются новые переходы

T ' T	T '( p		i	)	, где	. Переходы
	pi	P
r 1 , r 2 ,..., r n( pi )		добавляются в сеть, чтобы				объединить позиции
p 1 , p 2 ,...,	pn( pi ) в кольцевую подсеть;

4)|I(pi)|+|O(pi)| дуг для рi Р: n(pi)>1 распределяются между позициями p 1 , p 2 ,..., pn( pi ) произвольно, но таким образом, чтобы не было кратных дуг;

5)фишки, находящиеся в начальной маркировке в позиции pi,

произвольно распределяются в позициях p 1 , p 2 ,..., pn( pi ) :

n( pi )

( pi ) ( pl ) .

l 1

Замечание. Так как удаление Петли в общей сети Петри является LB-эквивалентным преобразованием, то при проведении преобразования Хэка можно рассматривать сети без петель.

111

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

Теорема о преобразовании Хэка. Приведение сети Петри к ординарному виду является LB-эквивалентным преобразованием.

Доказательство. Пусть имеется сеть С=(P, T, I, O). Сеть С'=(Р', Т', I', О') получена в результате преобразования Хэка.

Рассмотрим свойство «живость». Пусть некоторая произвольная последовательность запусков сети С. Последовательности можно сопоставить ~ множество последовательностей запусков: из ' ~ сети С' легко можно получить последовательность путем вычеркивания переходов

r 1 , r 2 ,..., r n( pi ) , добавленных в результате преобразования. Поэтому, если одна сеть жива, то жива и другая сеть.

Рассмотрим свойство «ограниченность». Ограниченность сети С' при условии ограниченности сети С легко вытекает из п.5 преобразования. Нетрудно видеть, что и обратное справедливо.

Замечания:

1) Общие сети, сети без петель и ординарные сети можно исследовать с помощью матричного подхода и деревьев достижимости. В табл. 6 представлена информация об использовании каждого из подходов при решении различных задач теории СП.

112

					Таблица 6
		Сравнение методов анализа СП
	Задача		Усеченное ДД	Матричный подход
Проверка	свойств безопасности		+		-
и ограниченности
Свойство	сохранения	(строгое
сохранение	и сохранение по		+		+
отношению	к	вектору
взвешивания)
Задача покрываемости			+
			Для ДД без		-
			символа
Задача достижимости					+
				Позволяет вычислить
				вектор f( ) запусков
				последовательности
				переходов	,
				приводящей к
			+	искомой маркировке
			Для ДД без	'.
			символа	Существование целого
				неотрицательного
				вектора f(	) является
				необходимым, но не
				достаточным
				условием для
				достижимости '.

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

113

Бесконфликтные сети. Персистентные сети

Определение. Сеть Петри называется бесконфликтной при выполнении следующих условий: либо все позиции имеют только один выход, либо, если выходов более одного, то из каждого перехода, являющегося выходным для этой позиции, ведет дуга в эту позицию (Рис. 73).

Рис. 73. Пример бесконфликтной сети Петри

Определение. Сеть Петри С=(P, T, I, O) с начальной маркировкой 0 называется персистентной, когда для R(C, 0) и любой позиции pi выполняется условие:

если (pi)≥#(pi, I(tj)) и (pi)≥#(pi, I(tk)), то ( , tjtk) определена.

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

Замечание. Свойство персистентности не подчиняется принципу монотонности: если сеть (C, 0) персистентна, то при 0'≥ 0 сеть может оказаться не персистентной. Например, сеть при 0 не имеет маркировок, в которых разрешено более одного перехода, а при 0'≥ 0 имеет, и может оказаться, что запуск одного из них лишает другой возможности запуска.

Пример 48. Рассмотрим сеть Петри (Рис. 74). Чтобы установить персистентность сети, определим множество достижимости сети и проверим для каждой маркировки из множества достижимости условие: если (pi)≥#(pi, I(tj)) и (pi)≥#(pi, I(tk)), то ( , tjtk) определена.

114

t1	p3
p1	t3	t4
t2		p5
p2	p4

Рис. 74. Пример персистентной сети Петри

Множество достижимости имеет вид: {(11000), (01100), (10010), (00110), (00001)}. Только в маркировке (11000) разрешено одновременно более одного перехода, а именно – t1 и t2. Проверим выполнение условие – запуск перехода t1 не влияет на возможность запуска перехода t2, для t2 аналогично. Таким образом, данная сеть Петри является персистентной.

Теорема о тупиковой маркировке персистентной сети.

Множество достижимости R(C, 0) персистентной сети С=(P, T, I, O) содержит не более одной тупиковой маркировки.

Доказательство. Проведем доказательство от противного.

Пусть сеть С имеет две тупиковых маркировки j и						k.
Тогда существуют некоторые последовательности запусков j и
k:
( 0, j)=		j и ( 0,		k)=	k.
Последовательностям	запусков			j	и	k соответствуют
последовательности маркировок:
~	:	0 ,	1 ,...,	,
~	:	0 ,	1 ,..., .

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

Пусть = jh= ks – маркировка, одинаковая для обеих последовательностей и находящаяся ближе всего к своей тупиковой маркировке (самая правая среди одинаковых маркировок).

115

Тогда существуют переходы tj и tk:

( , tj) определена и ( , tk) определена.

Так как сеть персистентна, то определены:

( , tjtk) и ( , tjtk).

Обозначим tjtk= ', tktj= ''. Характеристические векторы для ' и '' одинаковые. В соответствии с утверждением 3 имеем: при запуске ' и '' получается одна и та же маркировка, но это противоречит

тому, что самая правая маркировка. Данное противоречие доказывает справедливость теоремы.

Теорема о бесконфликтных сетях. Сеть Петри персистентна при любой маркировке 0 тогда и только тогда, когда она бесконфликтна.

Доказательство. Проведем доказательство необходимости от противного. Пусть сеть не является бесконфликтной. Тогда в ней существует позиция pi I(tj) и pi I(tk), но pi O(tk) (Рис. 75).

			pi
tj						tk

Рис. 75. Фрагмент сети Петри для доказательства теоремы о бесконфликтных сетях

Выберем начальную маркировку 0 таким образом, что

0(pi)≥max{#(pi, I(tj)), #( pi, I(tk))}.

Тогда после запуска tk (возможно неоднократного) получим некоторую маркировку (pi)≤#(pi, I(tj)), то есть переход tj не разрешен. Но это противоречит условию персистентности данной сети Петри. Достаточность вытекает из определения класса бесконфликтных сетей и персистентных сетей.

Замечание. Свойство бесконфликтности относится только к структуре СП, а свойство персистентности привязано к маркировке сети.

116

В связи с этим можно показать, что существуют персистентные СП при определенной начальной маркировке, которые бесконфликтными не являются (Рис. 76). Однако если сеть является персистентной при любой маркировке, то она обязательно бесконфликтная (теорема о бесконфликтных сетях).

	t1	t3
		p2
p1	t2	t4	p4

p3

						t7
p5			t5
					p7
p6			t6

Рис. 76. Пример персистентной СП, которая не является бесконфликтной

Автоматные сети

Определение. Автоматная сеть Петри – это такая сеть Петри

С=(P, T, I, O), что для tj T:

|I(tj)|=|O(tj)|=1.

Другими словами, в автоматной сети Петри (АСП) каждый переход имеет точно один вход и один выход (Рис. 77).

		t2	t4
			p3
	t1
p1	p2	t3	t5	p5
			p4
	Рис. 77. Пример автоматной сети Петри

117

Некоторые свойства автоматных сетей очевидны:

1)Каждая строка матрицы инцидентности D, содержит один элемент, равный, -1 и один элемент, равный, +1.

2)АСП является строго сохраняющей. Это означает, что число фишек в такой сети никогда не изменяется, фишки в позициях не

накапливаются. Дерево достижимости АСП не содержит символа , а, значит, все задачи анализа успешно решаются.

3) Если в начальной маркировке АСП имеет только одну фишку, то с ее помощью нельзя описать разделение процесса на параллельные ветви (Рис. 77). Но если в начальной маркировке сеть содержит несколько фишек, то она способна отображать параллельное функционирование, т.е. одновременно возможен запуск нескольких последовательностей, независимых между собой

(Рис. 78).

		t2	t4
			p3
	t1
p1	p2	t3	t5	p5
			p4

Рис. 78. Пример автоматной сети Петри, которая отображает параллельное функционирование

Если запустить переход t1, то позиция p2 будет содержать две фишки. Тогда станет возможен параллельный запуск переходов t2 и t3, а затем и t4 и t5.

4)Сеть может моделировать конфликтные ситуации с помощью позиции, являющейся входной одновременно для нескольких переходов.

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

118

Сети Петри со свободным выбором

Определение. Сеть Петри со свободным выбором – это такая

сеть Петри С=(P, T, I, O), что если рi I(tj) и рi I(tk) (j k), то

I(tj)=I(tk)={рi}.

Заметим, что в СП со свободным выбором ограничен конфликт: если некоторая позиция является входной одновременно для нескольких переходов, то она является единственной входной позицией каждого из этих переходов (Рис. 79), поэтому все эти переходы разрешены одновременно. Запуск любого из них не зависит от маркировки каких-либо других позиций и осуществляется свободный выбор запускаемого перехода.

		p1				t2		p3
		t1						t4
		p2		t3						p4
		t5

Рис. 79. Сеть Петри со свободным выбором

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

119

Маркированные графы

Определение. Маркированный граф – это такая сеть Петри

С=(P, T, I, O) со свободным выбором, что для рi Р: |I(pi)|=|O(pi)|=1.

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

		t1		t2
		p5	p3	p4
	p1	p2
		p6

t4	t3

Рис. 80. Маркированный граф

ВМГ не удается как а АСП представить конфликтные ситуации

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

Каждый столбец матрицы инцидентности D, содержит ровно один положительный (+1) и ровно один отрицательный (-1) элемент.

Особенностью МГ является то, что они, как правило, содержат циклы.

Определение. Циклом в

последовательность переходов tj1, tj2,

соседних переходов tjr, tjr+1 pi:pi последний переход связан с первым.

сети Петри называется …, tjk, такая что для любых

O(tjr) и pi I(tjr+1), причем

Пример 49. Рассмотрим МГ (Рис. 80). В данной СП имеются следующие циклы: t1t4t1, t2t3t2, t1t2t3 t4t1.

120