Интеллектуальный анализ выполнения бизнес-процессов в системе электронного документооборота. Матвейкин В.Г - 33 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

35
ло фишек, равное кратности дуги, соединяющей его с переходом. Однако при работе сети Петри общего вида некоторые ее
места могут накапливать неограниченное число фишек (например, место
2
p
в сети на рис. 9). Если интерпретировать места
как накопители (буферы) данных, сигналов или деталей в моделируемых системах, то естественно потребовать. Что при лю-
бом варианте функционирования этих систем не происходило бы переполнение накопителей, которые в реальных ситуациях
имеют конечную, фиксированную емкость. Следующие понятия формализуют такие требования.
Место
p
в сети Петри
),,,,(
0
MWFTPN =
называется ограниченным, если существует число
n
такое, что для любой
достижимой в сети разметки
M
справедливо неравенство
npM ≤)(
. Сеть
N
называется ограниченной сетью, если любое
ее место ограничено. Ясно, что множество достижимых разметок
)(NR
конечно, если и только если
N
– ограниченная сеть.
В сети на рис. 9 места
1
p
и
3
p
ограничены, так как каждое из них может содержать не более одной фишки. В то же время
место
2
p
не ограничено, и поэтому эта сеть не является ограниченной. Сеть на рис. 8 ограничена: любое место в ней не мо-
жет содержать более двух фишек. Место
p
называется безопасным, если
1)(:)( ≤∈∀ pMNRM
; соответственно сеть безо-
пасна, если все ее места безопасны. Любая достижимая в безопасной сети разметка представляет собой вектор из 0 и 1. Сети
на рис. 8 и рис. 9 не являются безопасными. Ограниченность и безопасность характеризует емкость условий: в дискретной
информационной системе, моделируемой соответствующими сетями, можно ограничить емкость накопителей, необходимых
для хранения условий наступления событий. Родственным этим понятиям является понятие консервативной сети, в которой
сумма фишек во всех ее местах остается постоянной при работе сети, т.е.
.
В консервативной сети каждый переход консервативен в том смысле, что его срабатывание не меняет число фишек в
сети, т.е.
|||| •=• tt
.
Переход в сети может сработать при определенных условиях, связанных с разметкой его входных мест. В общем случае
может оказаться, что для некоторого перехода условие его срабатывания никогда не выполняется, как бы ни функциониро-
вала сеть. Такой переход – лишний в сети, его можно исключить без ущерба для работы сети. Может случиться также, что
после некоторой последовательности срабатываний переходов сети и соответствующих изменений ее разметки некоторые
переходы, в том числе те, которые уже срабатывали, больше никогда не сработают, какие бы варианты достижимых в сети
разметок не возникали. Это означает, что в моделируемых системах могут появляться ситуации, тупиковые для некоторых
событий, "исключающие их из дальнейшей игры". Например, в операционных системах подобные случаи имеют место при
взаимных блокировках процессов (deadlocks). Следующие определения связаны с выявлением таких ситуаций в сетях Петри.
Переход
t
в сети Петри
),,,,(
0
MWFTPN =
называется потенциально живым при разметке
)(NRM ∈
, если
)(:),( tFMMNRM •≥
′
∈
′
∃
,
т.е. существует достижимая от
M
разметка
M
′
, при которой переход
t
может сработать. Если
0
MM =
, то
t
называется
потенциально живым в сети
N
. Переход
t
– мертвый при
M
, если он не является потенциально живым при
M
. Переход
t
– мертвый, если он мертв при любой достижимой в сети разметке.
Переход
t
в сети Петри
N
называется живым, если
,
т.е. переход
t
является потенциально живым при любой достижимой в сети
N
разметке. Переход
t
– потенциально мерт-
вый, если существует
)(NRM ∈
такая, что при любой разметке
),( MNRM =
′
переход
t
не может сработать. Разметка
M
в этом случае называется
t
– тупиковой; если она
t
– тупиковая для всех
Tt ∈
, то она является тупиковой. Если
M
– тупи-
ковая разметка, то
}{),( MMNR =
. Сеть называется живой, если все ее переходы живы.
В сети на рис. 8 все переход потенциально живы и все переходы потенциально мертвы, так как в ней достижима тупико-
вая разметка (рис. 8, г). Эта сеть не может быть живой, так как содержит потенциально мертвые переходы. Сеть на рис. 9
также не является живой, так как в ней достижимы тупиковые разметки вида
0),0,,0( ≥
nn
.
Переход
t
называется устойчивым в сети
N
, если
)(},{\ NRMtTt ∈∀∈
′
∀
;
)),()(())(())(( tFtFMtFMtFM
′
•+•≥⇒
′
•≥∧•≥
т.е. если переход
t
может сработать, то никакой другой переход не может, сработав, лишить его этой возможности. Сеть
N
устойчива, если все ее переходы устойчивы.
В сети на рис. 8 устойчивы переходы
1
t
,
2
t
,
3
t
,
4
t
, в сети на рис. 9 устойчив только переход
2
t
. Однако обе сети не ус-
тойчивы, так как в первой сети не устойчивы переходы
5
t
,
6
t
, во второй –
1
t
,
3
t
,
4
t
.
Конечная цель специальной теории сетей Петри – автоматический анализ свойств сетей, их автоматические синтез и
преобразования, на основании чего могут быть построены практические алгоритмы анализа, синтеза и преобразований дис-
кретных систем, моделируемых сетями. В частности, полезно найти алгоритмы, с помощью которых для любой предъявлен-
ной сети можно установить, обладает ли она интересующим нас свойством – является ли она ограниченной, живой, устойчи-

Страницы