TVPS_posobie_13_06_2013

Таким образом, функция следующего состояния это расширенная функция следующего состояния при | |=1.

Определение. Пусть имеются две маркировки некоторой сети. Отношение " ' истинно, если каждый элемент маркировки " не меньше соответствующего элемента маркировки '.

Замечание. Если для некоторых маркировок сети Петри выполняется соотношение " ' и в маркировке ' разрешен переход t, то справедливы следующие утверждения:

1)	переход t разрешен и в маркировке	";
2)	( ", t) ≥ ( ', t), причем ( ", t)i≥ (	', t)i для i , n .

Таким образом, все последовательности запусков, допустимые в маркированной сети (C, ') допустимы также в (C, ''), если ''≥ '. Данное утверждение называют принципом монотонности, так как оно показывает, что увеличение вектора маркировки влечет за собой увеличение числа допустимых последовательностей запусков.

2.8.Множество достижимости. Класс маркировок

сетей Петри

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

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

Определение. Для маркированной сети Петри С=(P, T, I, O, ) маркировка ' называется непосредственно достижимой из , если существует переход tj Т, такой, что ( , tj)= '.

Маркировка * достижима из маркировки , если существует последовательность маркировок с начальной маркировкой и конечной *, в которой каждая последующая маркировка непосредственно достижима из предыдущей.

Определение. Множество	достижимости R(C,	0)
маркированной сети Петри (С, 0)	это множество всех маркировок,
достижимых из 0.
	51

Маркировка	R(C,	0), если существует	какая-либо
последовательность запусков переходов, изменяющих 0 на .
Пример 23. Для сети Петри (Рис. 31) и маркировки			0=(1, 0, 0)
непосредственно достижимыми являются две маркировки:

Рис. 31. Сеть Петри для иллюстрации множества достижимости

I	II
(1, 0, 0) разрешены t1, t2: запуск t2	(1, 0, 0) разрешены t1, t2: запуск t1
(0, 1, 0) stop	(1, 0, 1) разрешены t1, t2: запуск t1
	(1, 0, 2) разрешены t1, t2: запуск t1
	(1, 0, 3) разрешены t1, t2: запуск t1
	…
	(1, 0, n) разрешены t1, t2: запуск t2
	(0, 1, n) stop

Из (0, 1, 0) нельзя достичь ни одной маркировки, так как ни один переход не разрешен. Из (1, 0, 1) можно получить (1, 0, 2) и (1, 0, 3) и т.д. Множество достижимости R(C, 0)={(1, 0, п), (0, 1, п) | п N0}.

Пусть имеется маркированная сеть Петри С=(Р, Т, I, О, 0). Множество достижимости R(C, 0) образует так называемый класс

прямых маркировок MП. Пусть сеть C =(Р, Т, O, I, 0) – инверсная к сети С=(Р, Т, I, О, 0). Множество достижимости R( C , 0) образует так называемый класс обратных маркировок MО. Тогда MП MО= M

– класс маркировок сети Петри C.

2.9.Сеть Петри как модельная интерпретация АП

Пусть имеется маркированная сеть Петри (Р, Т, I, О, 0). Перейдем от нее к асинхронному процессу P=<S, F, I, R>.

Состояние сети Петри описывается ее маркировкой . Множеством достижимости R(C, 0) сети Петри называется множеством ее состояний.

52

Поставим в соответствие каждой маркировке	R(C, 0)
ситуацию АП. Получим множество ситуаций АП S.

Для определения следующего состояния сети Петри используется функция следующего состояния ( , tj), где R(C, 0). Поставим в соответствие каждому такому преобразованию отношение непосредственного следования F между соответствующими ситуациями АП. Таким образом, отношение F определено.

	Начальной маркировке сети Петри			0 соответствует некоторая
ситуация АП. Она и образует множество инициаторов АП I.
	Введем понятие множества заключительных маркировок сети
Петри следующим образом:
а)	множество	маркировок	' R(C, 0),	для которых	( ', tj) не
определена для		tj T;
б)	множество	маркировок	специально	выделенных в	качестве

заключительных.

Каждой маркировке из множества заключительных маркировок сети Петри соответствует какая-либо ситуация АП. Вместе они образуют множество результантов АП R.

Пример 24. Рассмотрим Сеть Петри (Рис. 32) и сопоставим ей

АП.

p1

t1

p3

t2

p4

p2

Рис. 32. Пример сети Петри

R(C, 0)={(1100), (0010), (0001)}. Тогда S={(1100), (0010), (0001)}.

Функция следующего состояния сети Петри определена для двух маркировок: ((1100), t1)= (0010), ((0010), t2)= (0001). Тогда отношение непосредственного следования АП F будет иметь вид:

(1100) F (0010), (0010) F (0001).

53

Начальная маркировка сети Петри (1100). Тогда множество инициаторов АП I={(1100)}.

Множество заключительных маркировок сети Петри состоит из одной маркировки (0001). Тогда множество результантов АП

R={(0001)}.

Таким образом, АП P=<S, F, I, R> полностью определен

(Рис. 33).

1100 0010 0001

Рис. 33. Полученный АП

54

2.10.Свойства сетей Петри

Асинхронность

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

Безопасность

Безопасность есть одно из важнейших свойств сети,

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

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

Определение. Маркированная сеть Петри безопасна, если безопасны все ее позиции.

Если позиция безопасна, то в вычислительном устройстве ее можно реализовать триггером.

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

	Для безопасности позиции pi Р в маркированной сети Петри
С=(P, T, I, O, 0) необходимо, но недостаточно выполнение условий:
1)	0(pi) 1;
2)	кратные выходные дуги отсутствуют: tj #(pi, O(tj)) 1.

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

55

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

Пример 25. Рассмотрим сеть (Рис. 34), не являющуюся безопасной, и превратим ее в безопасную.

Рис. 34. Пример сети, не являющейся безопасной

В этой сети переход t1 всегда разрешен, поэтому в p1, p2 – неограниченно накапливаются фишки. Следовательно, сеть не является безопасной.

Добавим для p1 и p2 в сеть две позиции p1' и p2', тогда сеть преобразуется в безопасную (Рис. 35).

Рис. 35. Пример безопасной сети

56

Ограниченность

А) k-ограниченность (k-безопасность). Требование безопасности является очень жестким. Безопасность позволяет реализовать позицию триггером, но в более общем случае для реализации позиции можно использовать и счетчик. В этом случае аппаратно реализуемый счетчик ограничен по максимальному числу, которое он может представить.

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

Другими словами, позиция является k-безопасной или k-ограниченной, если число фишек в ней в процессе функционирования сети Петри не превышает k.

При k=1 получаем 1-ограниченность (безопасность), то есть свойство безопасности есть частный случай свойства k-ограниченности.

Определение. Если сеть имеет n позиций (|P|=n), причем

позиция p	i	k -ограниченна ( i ,n ), то сеть называется
		i

k-ограниченной, где k max ki .

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

Сохранение

А) Строгое сохранение. Сети Петри можно использовать для моделирования систем распределения ресурсов. Например, сеть Петри может моделировать запросы на распределение и освобождение устройств ввода/вывода в вычислительной системе. В этих системах некоторые фишки могут представлять ресурсы.

57

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

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

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

Замечание. Строгое сохранение – это очень сильное ограничение. Например, из него следует, что число входов в каждый переход должно равняться числу выходов, |I(tj)|=|O(tj)|. Если бы это было не так, запуск перехода изменил бы число фишек в сети.

Б) Сохранение
Определение. Маркированная сеть Петри		С=(P,	T, I, O, 0)
называется сохраняющей по	отношению к вектору		взвешивания
w=(w1, w2,..., wn), n=|Р|, wi>0 для	i, если для всех	' R(C, 0)
			(2)

Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1, 1, ..., 1).

58

Пример 26. Рассмотрим сеть Петри (Рис. 36).

Рис. 36. Пример сети Петри, которая не является строго сохраняющей

Сеть Петри не является строго сохраняющей, поскольку запуск перехода t1 или t2 уменьшит число фишек на 1, а запуск перехода t3 или t4 в процессе функционирования добавит фишку к маркировке. Добавлением дуг эту сеть Петри можно сделать строго сохраняющей

(Рис. 37).

Рис. 37. Пример сети Петри, которая является строго сохраняющей

59

Вернемся к сети, изображенной на Рис. 36. Рассмотрим множество достижимости:

R(C, )={(1, 1, 0, 0, 1), (0, 1, 1, 0, 0), (1, 0, 0, 1, 0)}.

Для данного множества достижимости можно сформировать вектор взвешивания w, для которого условие (2) будет выполняться. Например, w=(1, 1, 2, 2, 1) или w=(2, 2, 4, 4, 2). Таким образом, данная сеть будет сохраняющей по отношению к вектору w.

Активность. Живость

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

Определение. Пассивный (мертвый) переход – это переход маркированной сети Петри (C, μ0), который не является разрешенным ни в одной из достижимых маркировок.

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

Определение. Переход t маркированной сети Петри (C, μ0) называется потенциально мертвым, если в процессе функционирования сети он может стать пассивным, т.е. может быть достигнута маркировка μ' R(C, μ0) такая, что ни в одной из маркировок μ'' R(C, μ') переход t не разрешен.

Определение. t-тупиковая маркировка – это маркировка, в

которой переход t является пассивным.

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

Определение. Переход t маркированной сети Петри (C, μ0) называется потенциально живым, если в процессе функционирования сети он может быть запущен, т.е. может быть достигнута маркировка μ' R(C, μ0), в которой он разрешен.

60