Graphics Programs Reference
In-Depth Information
1. The CTMC state space S =
{
s
i
}
corresponds to the reachability set
RS(M
0
) of the PN associated with the SPN (M
i
↔
s
i
).
2. The transition rate from state s
i
(corresponding to marking M
i
) to
state s
j
(M
j
) is obtained as the sum of the firing rates of the transitions
that are enabled in M
i
and whose firings generate marking M
j
.
To keep the discussion simple, the transitions of a SPN are assumed to be
associated with a single-server semantics and with a marking-independent
speed. This restriction will be relaxed later on in this chapter, when the
modelling implications of this generalization will be discussed. The race
policy that we assume for the model is irrelevant for the construction of the
stochastic process associated with the SPN, as we observed in Chapter
5.
A
race policy with resampling is thus used to simplify the explanation of the
expressions derived in the rest of the chapter.
Based on the simple rules listed before, it is possible to devise algorithms
for the automatic construction of the infinitesimal generator (also called the
state transition rate matrix) of the isomorphic CTMC, starting from the
SPN description. Denoting this matrix by Q, with w
k
the firing rate of
T
k
, and with E
j
(M
i
) =
{
h : T
h
∈
E(M
i
)
∧
M
i
[T
h
i
M
j
}
the set of transitions
whose firings bring the net from marking M
i
to marking M
j
, the components
of the infinitesimal generator are:
P
T
k
∈E
j
(M
i
)
w
k
8
<
i
6
= j
q
ij
=
(6.1)
:
−
q
i
i = j
where
X
q
i
=
w
k
(6.2)
T
k
∈E(M
i
)
In this topic we consider only SPNs originating ergodic CTMC. A k-bounded
SPN system is said to be ergodic if it generates an ergodic CTMC; it is
possible to show that a SPN system is ergodic if M
0
, the initial marking, is
a home state (see Section
2.4)
. A presentation of the most important results
of the theory of ergodic CTMCs is contained in Appendix
A;
this must be
considered as a reference for all the discussion contained in this chapter.
Let the row vector η represent the steady-state probability distribution on
markings of the SPN. If the SPN is ergodic, it is possible to compute the
steady-state probability distribution vector solving the usual linear system
of matrix equations:
8
<
:
η Q = 0
η 1
T
(6.3)
= 1
where 0 is a row vector of the same size as η and with all its components
equal to zero and 1
T
is a column vector (again of the same size as η) with
Search WWH ::
Custom Search