没有合适的资源？快使用搜索试试~ 我知道了~
首页Petri nets Properties, analysis and applications
资源详情
资源评论
资源推荐
Petri Nets: Properties, Analysis and
Appl
kat
ions
TADAO MURATA,
FELLOW,
IEEE
Invited Paper
This is an invited tutorialreview paper on Petri netsa graphical
and mathematical modeling tool. Petri nets are a promising tool
for describing and studying information processing systems that
are characterized as being concurrent, asynchronous, distributed,
parallel, nondeterministic, and/or stochastic.
The paper starts with
a
brief review of the history and the appli
cation areas considered in the literature. It then proceeds with
introductory modeling examples, behavioral and structural prop
erties, three methods of analysis, subclasses of Petri nets and their
analysis. In particular, one section is devoted to marked graphs
the concurrent system model most amenable to analysis. In addi
tion, the paper presents introductory discussions on stochastic nets
with their application
to
performance modeling, and on highlevel
nets with their application
to
logic programming. Also included
are recent results on reachability criteria. Suggestions are provided
for further reading on many subject areas of Petri nets.
I.
INTRODUCTION
Petri netsareagraphical andmathematical modeling tool
applicable to many systems. They are a promising tool for
describing and studying information processing systems
that are characterized
as
being concurrent, asynchronous,
distributed, parallel, nondeterministic, and/or stochastic.
As a graphical tool, Petri nets can be used
as
a
visualcom
munication aid similar to flow charts, block diagrams, and
networks. In addition, tokens are used in these nets to sim
ulate the dynamic and concurrent activities of systems. As
a
mathematical tool, it
is
possible to set up state equations,
algebraic equations, and other mathematical models gov
erning the behavior of systems. Petri nets can be used by
both practitioners and theoreticians. Thus, they provide
a
powerful medium of communication between them: prac
titioners can learn from theoreticians how to make their
models more methodical, and theoreticians can learn from
practitioners how to make their models more realistic.
Historically speaking, the concept of the Petri net has its
origin in Carl Adam Petri’s dissertation
[I],
submitted in 1962
Manuscript received May
20,
1988; revised November
4,
1988.
This work was supported by the National Science Foundation under
Grant DMC8510208.
The author
is
with the Department
of
Electrical Engineering and
Computer Science, University
of
Illinois, Chicago,
IL
60680, USA.
IEEE
Log
Number 8926700.
to the faculty of Mathematics and Physics at the Technical
University of Darmstadt, West Germany. The dissertation
was prepared while
C.
A. Petri worked as a scientist at the
Universityof Bonn. Petri’swork[l], [2]came totheattention
of A. W. Holt, who later led the Information System Theory
Project of Applied Data Research, Inc., in the United States.
The early developments and applications of Petri nets (or
their predecessor)arefound in the reports [3][8] associated
with this project, and in the Record [9] of the 1970 Project
MAC Conference on Concurrent Systems and Parallel
Computation. From 1970 to 1975, the Computation Struc
ture Group at
MIT
was most active in conducting Petrinet
related research, and produced many reports and theses
on Petri nets. In July 1975, there was
a
conference on Petri
Nets and Related Methods at MIT, but no conference pro
ceedings were published. Most of the Petrinet related
papers written in English before 1980 are listed in the anno
tated bibliography of the first book [IO] on Petri nets. More
recent papers up until 1984 and those works done in Ger
many and other European countries are annotated in the
appendix of another book [Ill. Three tutorial articles [12]
[I41 provide
a
complemental, easytoread introduction to
Petri nets.
Sincethe lateI970‘s, the Europeans have been veryactive
in organizing workshops and publishing conference pro
ceedings on Petri nets. In October 1979, about
135
research
ers mostly from European countries assembled in Ham
burg, West Germany, for
a
twoweek advanced course on
General Net Theory of Processes and Systems. The 17 lec
turesgiven in thiscoursewere published in its proceedings
[15], which
is
currently out of print. The second advanced
course was held in Bad Honnef, West Germany, in Sep
tember 1986. The proceedings [16],
[I7
of this course con
tain
34
articles, including two recent articles by C. A. Petri;
one[l8] isconcerned with hisaxiomsof concurrencytheory
and the other [I91 with his suggestions for further research.
The first European Workshop on Applications and Theory
of Petri Nets was held in 1980 at Strasbourg, France. Since
then, this series of workshops has been held every year at
different locations in Europe: 1981, Bad Honnef, West Ger
many; 1982, Varenna, Italy; 1983, Toulouse, France; 1984,
Aarhus, Denmark; 1985, Espoo, Finland; 1986, Oxford, Great
00189219/89/04000541$01.00
0
1989
IEEE
PROCEEDINGS
OF
THE IEEE, VOL.
77,
NO.
4,
APRIL
1989
541
Britain; 1987, Zaragoza, Spain; 1988, Venice, Italy; and 1989,
Bad Honnef, West Germany (planned). The distribution of
the proceedings of theseworkshops is limited to mostly the
workshop participants. However, selected papers from
these workshops and other articles have been published
by SpringerVerlag as Advances
in
Petri Nets [20][25]. The
1987 volume [24] contains the most comprehensive bibli
ographyof Petri nets[26] listing2074entries published from
1962 to early1987. The”recent publications” section of Petri
Net Newsletter [27l lists short abstracts of recent publica
tions three times ayear, and
is
agood sourceof information
about the most recent Petri net literature.
In
July 1985, another series of international workshops
was initiated. This series places emphasis on timed and sto
chastic nets and their applications
to
performance evalu
ation. The first internationl workshop on timed Petri nets
was held in Torino, Italy, in July 1985; the second was held
in
Madison, Wisconsin, in August 1987; the third
is
to be
held in Kyoto, Japan,
in
December
1989;
and the fourth
is
planned in Australia
in
1991. The proceedings of the first
two workshops [28], [29] are available from the
IEEE
Com
puter Society Press.
The above
is
a brief history of Petri nets. Now, we
look
at some application areas considered in the literature. Petri
nets have been proposed for a very wide variety of appli
cations. This
is
due
to
the generality and permissiveness
inherent in Petri nets. They can beapplied informallyto any
area or system that can be described graphically like flow
charts and that needs some means of representing parallel
or concurrent activities. However, careful attention must
be paid
to
a tradeoff between modeling generalityand anal
ysis capability. That
is,
the more general the model, the less
amenable
it
is
to analysis.
In
fact, a major weakness of Petri
nets
is
the complexity problem, i.e., Petrinetbased models
tend to become
too
large for analysis even for a modestsize
system.
In
applying Petri nets, it
is
often necessary to add
special modifications
or
restrictions suited to the particular
application. Two successful application areas are perfor
mance evaluation [28][50] and communication protocols
[51][62]. Promising areas of applications include modeling
and analysis of distributedsoftware systems [63][71], dis
tributeddatabase systems [72][75], concurrent and par
allel programs [76][92], flexible
manufacturing/industrial
control systems [93][IOO], discreteevent systems
[loll
[103], multiprocessor memorysystems [30], [104], [105], data
flow computing systems [106][108], faulttolerant systems
[log][114], programmable logic and VLSl arrays [115][120],
asynchronous circuits and structures [121][129], compiler
and operating systems [130], [131], officeinformation sys
tems [132][135], formal languages [136][142], and logic pro
grams [143][150]. Other interesting applications consid
ered in the literature are localarea networks [151][153],
legal systems [154], human factors [155], [156], neural net
works [157], [158], digital filters [159][161], and decision
models [162].
The use of computeraided tools
is
a necessity for prac
tical applications of Petri nets. Most Petrinet research
groups have their own software packages and
tools
to assist
the drawing, analysis, and/or simulation of various appli
cations. A recent article [I631 provides a good overview of
typical Petrinet tools existing as of 1986. Some of these
tools
and their applications are discussed
in
details in references
[I641 through [170].
The rest of this paper consists of the following topics.
Section
I I
discusses informally the transition enabling and
firing rule with and without capacity constraints. Several
introductory modeling examples are given in Section
Ill
to
illustrate modeling capabilities and concepts such as con
flict (choice or decision), concurrency, synchronization, etc.
Section IV describes behavioral or markingdependent
properties that can be studied using Petri nets. Section V
presents three methods of analysis: the coverability tree,
matrix equations, and reduction techniques. Section
VI
is
concerned with subclasses of Petri nets and their analysis.
Indepth analysis and synthesis methods are given
in
Sec
tion VI
I
for one of the subclasses known as marked graphs.
Structural or markingindependent properties are
dis
cussed
in
Section VIII. Section
IX
presents an introduction
to timed nets, stochastic nets, and highlevel nets, together
with their applications. Concluding remarks are given
in
Section
X.
II.
TRANSITION
ENABLING
AND
FIRING
In this section,wegivetheonly ruleone hastolearn about
Petrinet theory: the rule for transition enabling and firing.
Although this rule appears very simple, its implication in
Petrinet theory
is
very deep and complex.
A Petrinet
is
a particular kind of directed graph, together
with an initial state called the initialmarking,
MO.
The under
lying graph
N
of a Petri net
is
a directed, weighted, bipartite
graph consisting of two kinds of nodes, called places and
transitions, where arcs are either from a place toa transition
or from a transition
to
a place.
In
graphical representation,
places are drawn as circles, transitions as bars or boxes. Arcs
are labeled with their weights (positive integers), where a
kweighted arc can be interpreted as the set of
k
parallel
arcs. Labels for unity weight are usually omitted. A marking
(state)assignstoeach placeanonnegative integer. If amark
ing assigns to place
p
a nonnegative integer
k,
we say that
p
is
marked with
k
tokens. Pictorially, we place
k
black dots
(tokens)
in
placep. A marking
is
denoted by
M,
an mvector,
where
m
is
the total number of places. Thepth component
of
M,
denoted by
M(p),
is
the number of tokens
in
placep.
In modeling, using the concept of conditions and events,
places represent conditions, and transitions represent
events. A transition (an event) has acertain number of input
and outputplaces representing the preconditions and post
conditions of the event, respectively. The presence of a
token
in
a place
is
interpreted as holding the truth of the
condition associated with the place. In another interpre
tation,
k
tokens are put
in
a place
to
indicate that
k
data
items or resources are available. Some typical interpreta
tions of transitions and their input places and output places
are shown
in
Table
1.
A formal definition of a Petri net
is
given
in
Table 2.
Table
1
Some Typical Interpretations
of
Transitions and
Places
Input Places Transition Output Places
Preconditions
Event Postconditions
Input data computation step
Output data
Input signals
Signal processor Output signals
Resources needed
Task or
job
Resources released
Conditions
Clause in logic Conclusion(s)
Buffers
Processor Buffers
542
PROCEEDINGS
OF
THE
IEEE,
VOL.
77,
NO.
4,
APRIL
1989
Table
2
Formal Definition of a Petri Net
A Petri net is a 5tuple,
PN
=
(P,
T,
F,
W,
MO)
where:
P
=
{
p,,
p2,
. . .
,
p,}
is a finite set of places,
T
=
{t,,
tZ,
.
.
.
,
t,}
is a finite set of transitions,
F
c
(P
x
T)
U
(T
x
P)
is a set of arcs (flow relation),
W:
f
t
(1,
2,
3,
.
.
.}
is a weight function,
MO:
P
+
(0,
1,
2,
3,
.
.
.}
is the initial marking,
P
n
T=
0andP
U
Tf
0.
A Petri net structure
N
=
(P,
T,
F,
W)
without any specific initial
marking is denoted by
N.
A Petri net with the given initial marking is denoted by
(N,
MO).
The behavior of many systems can be described in terms
of system states and their changes. In order to simulate the
dynamic behavior of a system,
a
state or marking in a Petri
nets
is
changed according to the following transition (firing)
rule:
1)
A transition tis said to be enabled if each input place
pof
tismarkedwithatleastw(p,t)tokens,wherew(p,
t)
is
the weight of the arc from
p
to
t.
2)
An enabled transition mayor may not fire(depending
on whether or not the event actually takes place).
3)
A firing of an enabled transition
t
removes w(p,
t)
tokens from each input place
p
of
t,
and adds w(t,
p)
tokens to each output placep of
t,
where w(t,
p)
is
the
weight of the arc from
t
to
p.
A transition without any input place
is
called a source
transition, and one without any output place
is
called
a
sink
transition. Note that a source transition
is
unconditionally
enabled, and that the firing of a sink transition consumes
tokens, but does not produce any.
A pair of
a
place
p
and a transition
t
is
called a selfloop
if
p
is
both an input and output place of
t.
A Petri net
is
said
to be pure if it has no selfloops. A Petri net
is
said to be
ordinary
if
all
of its arc weights are
1’s.
€xample
7:
The above transition rule
is
illustrated in Fig.
1
using the wellknown chemical reaction: 2H2
+
0,
+
2H20.
Two tokens in each input place in Fig.
l(a)
show that
two units of
H2
and
0,
are available, and the transition
t
is
enabled. After firing
t,
the marking will change to the one
shown in Fig. l(b), where the transition
t
is
no longer
enabled.
0
O2
0‘
H2>
O2
(b)
Fig.
1.
Example
1:
An illustration of a transition (firing) rule:
(a)The marking before firingtheenabled transition
t.
(b)The
marking after firing
t,
where tis disabled.
For the above rule of transition enabling, it
is
assumed
that each place can accommodate an unlimited number of
tokens. Such
a
Petri net
is
referred to
as
an infinite capacity
net. For modeling many physical systems, it
is
natural to
consider an upper limit to the number of tokens that each
place can hold. Such
a
Petri net
is
referred to as a finite
capacity net. For a finite capacity net
(N,
MO), each place
p
has an associated capacity
K(p),
the maximum number of
tokens that
p
can hold at any time. For finite capacity nets,
for a transition
t
to be enabled, there
is
an additional con
dition that the number of tokens in each output place
p
of
t
cannot exceed its capacity
K(p)
after firing
t.
This rule with the capacity constraint
is
called the strict
transition rule, whereas the rule without the capacity con
straint
is
called the (weak) transition rule. Given
a
finite
capacity net (N,
MO),
it
is
possible to apply either the strict
transition rule to the given net
(N,
MO)
or, equivalently, the
weak transition rule to
a
transformed net
(N’,
M;),
the net
obtained from (N, MO)
bythefollowingcomplementaryplace
transformation, where it
is
assumed that
N
is
pure.
Step
I:
Add
a
complementary place
p’
for each place
p,
where the initial marking of
p’
is
given by
M@‘)
Step2: Between each transition
t
and some comple
mentary places
p’,
draw new arcs
(t,
p’)
or
(p’,
t)
where w(t,
p’)
=
w(p,
t)
and w(p’,
t)
=
w(t,
p),
so
that the sum of tokens in place
p
and its com
plementary place
p’
equals its capacity
K(p)
for
each place
p,
before and after firing the tran
sition
t.
=
K(p)

Mo(p).
Example 2: Let
us
apply the strict transition rule to the
finitecapacity net
(N,
MO)
shown in Fig. 2(a). At the initial
marking
MO
=
(1
0),
the only enabled transition
is
tl.
After
firing
t,,
we have
M,
=
(2
0),
where only
t2
and
t3
are
enabled.
M1
changes to
M,
=
(0
0)
after firing
t2,
or to M3
=
(0
1)
after firing
t3.
Continuing this process, it
is
easy to
drawthe(reachabi1ity)graph
shown in Fig. 2(c), which shows
all
possible markings and all possible firings at each mark
ing. Now, let
us
see how the net (N,
MO)
shown in Fig.
2(a)
is
transformed by the complementaryplace transformation
into the net
(N’,
Mi)
shown in Fig. 2(b). The first step
is
to
add the two complementary places
p;
and
p;
with their ini
tial markings
Mi@;)
=
K(pl)

Mo(pl)
=
2

1
=
1,
and
Mh(p;)
=
K(p,)

Mo(p2)
=
1

0
=
1.
The next step
is
to
add new arcs between each transition
t
and some comple
mentary places,
so
as to keep the sum of tokens in each pair
of
placespiandp;thesameandequal
toK(pi),i
=
1,2,
before
and after firing
t.
For example, since w(tl,
pl)
=
1,
we have
w(p;,
tl)
=
1.
Similarly, w(t,,
p;)
=
w(pl,
t3)
=
2 and w(p;,
t3)
=
w(t3,
p2)
=
1,
since firing
t3
removes two tokens from
p1
and adds one token in
p2
(we draw the twoweight arc from
t3
top; and the unitweight arc from
pi
to
t3).
Likewise, two
additional arcs
(
t,,
pi)
and
(t4,
p;)
are drawn to obtain the
net
(A”,
M@
shown in Fig. 2(b). In
a
similar manner, as illus
trated for
(N,
MO),
it
is
easy to draw the reachability graph
forthe net(N‘,M& It isalsoeasytoverifythatthetwo reach
ability graphs are isomorphic, and that the two nets
(N,
MO)
and (N’,
Mi)
are equivalent with respect to the behavior of
The above discussions may be summarized in the fol
all
possible firing sequences.
0
lowing theorem.
MURATA:
PETRI
NETS
543
p1
‘3
p2
‘4
(0
Fig.
2.
Example
2:
An illustration of the complementary
place transformation: (a) A finitecapacity net
(N,
MO).
(b) The
net
(N’,
M’,,)
after the transformation. (c) The reachability
graph for the net
(N,
MO)
shown in
(a).
Theorem
I:
Let
(N,
MO) be
a
pure finitecapacity net, where
the strict transition rule
is
to be applied. Let
(N’,
Mi)
be the
net obtained from
(N,
MO)
by the complementaryplace
transformation, where the weak transition rule
is
appli
cable to
(N’,
Mi).
Then the two nets
(N,
MO)
and (N’,
M;)
are
equivalent in the sense that both have the same set of all
In view of Theorem
1,
every pure finitecapacity net
(N,
MO)
can be transformed into an equivalent net
(N’,
Mi),
where the weak transition rule
is
applicable, and thus we
only need consider the weaktransition rule. Therefore,
unless otherwise stated, we consider only infinitecapacity
nets with the weaktransition rule in the rest of this paper.
The reason
is
that
all
properties associated with a finite
capacity net can be discussed in terms of thosewith an infi
nitecapacity net using the complementaryplace transfor
mation.
In Theorem
1,
it
is
assumed that
a
Petri net be pure to
avoid confusion since there are many different interpre
tations of the enabling condition for
a
selfloop in a finite
capacity net
[171].
But this
is
not
a
real restriction, because
a selfloop can be “refined” or transformed into a loop by
introducing
a
dummy pair of a transition and
a
place,
as
is
illustrated in Fig.
3.
possible firing sequences.
0
Ill. INTRODUCTORY
MODELING
EXAMPLES
In this section, several
simpleexamplesaregivento
intro
duce the reader to some basic concepts of Petri nets that
are useful in modeling.
Fig.
3.
Transformation of a selfloop to a loop.
A. FiniteState Machines
Finitestate machines or their state diagrams can be
equivalently represented by a subclass of Petri nets. As an
example of a finitestate machine, consider
a
vending
machinewhich acceptseither nickelsordimesand sells156
or
206
candy bars. For simplicity, suppose the vending
machine can hold up to
206.
Then, the state diagram of the
machine can be represented by the Petri net shown in Fig.
4,
where the five states are represented by the five places
Ge~15
candy
I
log
Deposit
10
ct
Get
20
Q
candy
Fig.
4.
A Petri net (a state machine) representing the state
diagram of
a
vending machine, where coin return transi
tions are omitted.
labeled with
OF,
56,
IOC,
156, and
206,
and transformations
from one state to another state are shown by transitions
labeled with input conditions, such as “deposit
56.’’
The
initial state
is
indicated by initially putting a token in the
placep,, with a06 label in this example. Note that each tran
sition in this net has exactly one incoming arc and exactly
one outgoing arc. The subclass of Petri nets with this prop
erty
is
known as state machines. Any finitestate machine
(or its state diagram) can be modeled with a state machine.
The structure of the place
p,
having two (or more) output
transitions t, and t2, as shown in Fig.
5,
is
referred to
as
a
conflict, decision, or choice, depending on applications.
State machines allow the representation of decisions, but
not the synchronization of parallel activities.
B.
Parallel Activities
Parallel activities
or
concurrency can be easily expressed
in terms of Petri nets. For example, in the Petri net shown
in Fig.
6,
the parallel or concurrent activities represented
544
PROCEEDINGS
OF
THE
IEEE,
VOL.
77,
NO.
4,
APRIL
1989
n
‘1
‘3
‘2
(a)
Fig.
5.
A Petrinet structure called a conflict, choice, or
decision. It is a structure exhibiting nondeterminism.
by transitions
t2
and
t3
begin at the firing of transition
tl
and
end with the firing of transition
t4.
In general, two transi
tions are said to be concurrent
if
they are causally inde
pendent, i.e., one transition may fire before or after or in
parallel with the other,
as
in the case of
t2
and
t3
in Fig.
6.
Fig.
6.
A
Petri net (a marked graph) representing deter
ministic parallel activities.
It has been pointed out [I721 that concurrency can be
regarded as a binary relation (denoted by
CO
on the set of
eventsA
=
{el,e2,.
.
.~jwhichislj~~iexive@,
CO
e,jard
2)
symmetric (e,
CO
e2 implies e,
CO
e,),
3)
but not tran
sitive (e,
CO
e2 and
e2
CO
e3 do not necessarily imply
e,
CO
e& For example, one may drive
a
car (event e,) or
walk(event e3)whilesinging(event e2), but onecannot drive
and walk concurrently.
Note that each place in the net shown in Fig.
6
has exactly
one incoming arc and exactly one outgoing arc. The sub
class of Petri nets with this property
is
known as marked
graphs.
Marked graphs allow representation of concur
rency but not decisions (conflicts).
Two events e, and e2 are in conflict if either e, or e2 can
occur but not both, and they are concurrent if both events
can occur in any order without conflicts.
A
situation where
conflict and concurrency are mixed
is
called
a
confusion.
Two types of confusion are shown in Fig. 7. Fig. 7(a) shows
a
symmetric confusion, since
two
events
t,
and
t,
are con
current while each of
tl
and
t2
is
in conflict with event
t3.
Fig. 7(b) shows an asymmetric confusion, where
tl
is
con
current with
t2
but will be in conflict with
t3
if
t2
fires first.
C. Dataflow Computation
Petri nets call be used to represent not only the flow of
control but also the flow of data. The net shown in Fig.
8
is
a Petrinet representation of
a
dataflow computation.
A
dataflow computer
is
one in which instructions are enabled
for execution by the arrival of their operands, and may be
g/&$
‘3
Fig.
7.
Two types of a confusion.
(a)
Symmetric confusion:
t,
and
t,
are concurrent as well as in conflict with
t3.
(b) Asym
metric confusion:
t,
is concurrent with
t2
but will be in con
flict with
t3,
if
t,
fires before t,.
executed concurrently. In the Petrinet representation of
a
dataflow computation, tokens denote the values of cur
rent data
as
well
as
the availability of data. In the net shown
in Fig.
8,
the instructions represented by transitions
tl
and
U
a+b
Divide

ab
?
v
b

w
If
a

b
=
0
x
is undefined
/
Subtract
a
b
\
Fig.
8.
A Petri net showing a dataflow computation for
x
=
(a
+
b)/(a

b).
t2
can be executed concurrently and deposit the resulting
data (a
+
b)
or (a

b)
in
the respective output places.
D. Communication Protocols
Communication protocols are another area where Petri
nets can be used to represent and specify essential features
of a system. The liveness and safeness properties (see Sec
tion
V)
of a Petri net are often used as correctness criteria
in communication protocols. The Petri net shown in Fig.
9
is
a
very simple model of
a
communication protocol
between two processes. Figure
10
shows the Petrinet rep
resentation of
a
nondeterministic wait process where
trl,
tr2,
or
tout
fires if response
1,
response 2, or no response
is
received before a specified time
(tout
),
respectively.
E.
Synchronization Control
In
a
multiprocessor or distributedprocessing system,
resources and information are shared among several pro
cessors. This sharing must be controlled or synchronized
to insure the correct operation
of
the overall system. Petri
nets have been used to model
a
variety of synchronization
MURATA:
PETRI
NETS
545
剩余39页未读，继续阅读
安全验证
文档复制为VIP权益，开通VIP直接复制
信息提交成功
评论0