Graphics Programs Reference
In-Depth Information
Here the SME relation represents the mutual exclusion in enabling due to
structural properties. The notation t
i
SME t
j
(structural mutual exclusion)
is used as a synonym of t
i
HME t
j
∨
t
i
MME t
j
∨
t
i
ΠME t
j
where
HME indicates the structural mutual exclusion due to inhibitor arcs, MME
indicates the structural mutual exclusion due to invariants (see Chapter
2)
,
and ΠME is defined as follows:
Definition 4.4.5 Structural mutual exclusion due to priority (denoted ΠME)
is: t
l
ΠME t
m
iff
∃
t
k
:
•
π
k
> π
l
∧
π
k
> π
m
and
•∀
p
j
∈
P,
•
I(t
k
,p
j
)
≤
max(I(t
l
,p
j
),I(t
m
,p
j
)) and
•
(H(t
k
,p
j
) = 0
∨
H(t
k
,p
j
)
≥
min(H(t
l
,p
j
),H(t
m
,p
j
)) > 0)
Informally, two transitions (at the same priority level) are ΠME if, in or-
der for them to have concession at the same time, a third higher priority
transition must also have concession; an example is shown in Fig.
4.7
where
transitions t
l
and t
m
can have concession together in a given marking M
only if M(p
1
)
≥
2, M(p
2
)
≥
1 and M(p
3
)
≥
1; however in this situation also
t
k
has concession, and since π
k
> π
l
= π
m
, then t
l
and t
m
are not enabled
together in this marking.
Any one of the three structural mutual exclusion conditions can be checked
without computing the actual transition sequences, and is su
cient for the
mutually exclusive enabling of two transitions.
4.5
Reachability Analysis Techniques
The analysis of the reachability graph in the case of PN models with priority
is similar to that for PN models without priority. The only difference is in
the enabling rule that in the case of a priority structure may produce a
smaller reachability graph (in terms of both numbers of arcs and nodes).
Reachability graph of PN models with priority — Fig.
4.8
and
Fig.
4.9
depict the reachability set and reachability graph of the readers
& writers PN system with two processes, and with the following priority
definition: π
1
= π
6
= π
7
= 0, π
2
= π
3
= 2, π
4
= π
5
= 1. The reader may
wish to compare this RG with the one of the PN system without priority
shown in Fig.
2.4.
The total number of markings in the RS is reduced from
19 to 13. Moreover, markings can be partitioned in classes, according to
the priority level of enabled transitions. In our example, markings can be
partitioned in three classes, corresponding to the enabling of transitions at
Search WWH ::
Custom Search