Applications of non-Markovian stochastic Petri nets.
nets represent a powerful paradigm for modeling parallel and distributed systems. Parallelism and resource contention can easily be captured and time can be included for the analysis of system dynamic behavior. Most popular stochastic Petri nets assume that all firing times are exponentially distributed. This is found to be a severe limitation in many circumstances that require deterministic and generally distributed firing times. This has led to a considerable interest in studying non-Markovian models. In this paper we specifically focus on non-Markovian Petri nets. The analytical approach through the solution of the underlying Markov regenerative process is dealt with and numerical analysis techniques are discussed. Several examples are presented and solved to highlight the potentiality of the proposed approaches.
Introduction
Over the past decade, stochastic and timed Petri
nets of several kinds have been proposed to overcome
limitations on the modeling capabilities of
Petri nets (PNs). Although very powerful in capturing
synchronization of events and contention for
R.M. Fricks is with the SIMEPAR Laboratory and
Ponticia Universidade Catolica do Parana, Curitiba/PR,
Brazil. A. Puliato is with the Istituto di Informatica, Uni-
versita di Catania, Catania, Italy. M. Telek is with the
Department of Telecommunications, Technical University of
Budapest, Budapest, Hungary. K.S. Trivedi is with the
Department of Electrical and Computer Engineering, Duke
University, Durham/NC, USA. E-mails: fricks@simepar.br,
ap@iit.unict.it, telek@hit.bme.hu, and kst@ee.duke.edu.
system resources, the original paradigm was not
complete enough to capture other elements indispensable
for dependability and performance modeling
of systems. Thus, new extensions allowing
for time and randomness abstractions became nec-
essary. Despite the consensus on which elements
to add, a certain uncertainty existed on where to
aggregate the proposed extensions. From among
several alternatives, a dominant one was soon established
where the Petri nets could have transitions
that once enabled would re according to exponential
distributions with dierent rates (EXP
transitions). This led to well known net types:
Generalized Stochastic Petri Nets (GSPNs) [1] and
Stochastic Reward Nets (SRNs) [2].
The resulting modeling framework allowed the
denition and solution of stochastic problems enjoying
the Markov property [3]: the probability
of any particular future behavior of the process,
when its current state is known exactly, is not altered
by additional knowledge concerning its past
behavior. These Markovian stochastic Petri nets
(MSPNs) were very well accepted by the modeling
community since a wide range of real dependability
and performance models fall in the class of
Markov models. Besides the ability to capture various
types of system dependencies intrinsic to the
underlying Markov models, other advantages of the
Petri net framework also contributed to the popularity
of the MSPNs. Among these reasons, we
point out the power of concisely specifying very
large Markov models, and the equal ease with which
steady-state, transient, cummulative transient and
sensitivity measures could be computed. One of the
restrictions, however, is that only exponentially
distributed ring times are captured. This led to
the development of non-Markovian stochastic Petri
nets.
Non-Markovian stochastic Petri nets (NMSPNs)
were then proposed to allow for the high level description
of non-Markovian models. Likewise in
the original evolutive chain, several alternative approaches
to extend the Markovian Petri nets were
proposed. Their distinctive feature was the underlying
analytical technique used to solve the non-Markovian
models. Candidate solution methods
considered included the deployment of supplementary
variables [4], the use of phase-type expansions
approximations [5, 6], and the application of
Markov renewal theory [7, 8]. Representative non-Markovian
Petri nets proposed, listed according
to the underlying solution techniques, are the Extended
Stochastic Petri Nets (ESPNs) [9], the Deterministic
and Stochastic Petri Nets (DSPNs) [10],
the Stochastic Petri Nets with Phase-Type Distributed
Transitions (ESPs) [11], and the Markov
Regenerative Stochastic Petri Nets (MRSPNs) [12].
As a consequence of these evolutive steps, we observe
that the restriction imposed on the distribution
functions regulating the ring of timed transitions
was progressively relaxed from exponential
distributions to a combination of exponential and
deterministic distributions, then to any distribution
represented by phase type approximations,
and nally to any general distribution function
(GEN transitions).
However, this
exibility also brought a new requirement
with it. If an enabled GEN transition is
disabled before ring, a scheduling policy is needed
to complete the model denition. Consider the
generic client/server NMSPN model in Fig. 1 for
instance. Requests from clients arrive according to
a Poisson process (EXP transition t 1 ). Tokens in
place clients already in the system. In
a single server conguration only one of the queued
requests will be serviced at a given time. The service
requirement
g of each request is sampled from
a general distribution function G g (t) that coordinates
the ring of the GEN transition t 2 . An age
variables a g associated with a request keeps track
of the amount of service actually received by the
request. Service will be completed (i.e., transition
will re) as soon as the age variable a g of the active
request (the one receiving server's attention)
reaches the value of its service requirement
. After
that, the request leaves the system and its associated
age variable is destroyed.
Furthermore, suppose that the server is failure-

Figure

1: Fault-tolerant client/server model.
prone with constant failure and repair rates. A
token in place P 2 represents the active state of the
server while a token in place P 3 indicates server
being down (undergoing repair). Consequently, r-
ing of the EXP transitions t 3 and t 4 correspond
to the failure and end-of-repair events associated
with the server. Whenever down, the server cannot
service new clients or complete the service requirement
of the current request, as shown by the
inhibitor arc from place P 3 to transition t 2 . Clearly
a scheduling policy is then necessary to precisely
dene how the server must proceed when brought
up again. In MSPNs with EXP transitions this was
not a problem because of the memoryless property
of the exponential distributions [3] 1 . The remaining
processing time of an nterrupted request is also
represented by the EXP transition t 2 .
In the favorable case, the server is able to completely
service the current request before a failure
occurs (as shown in Fig. 2a). Otherwise the system
behavior depends on the amount of remaining service
at the time of the interruption, and whether
the service already received by the request will be
discarded. The service requirement
may increase
or decrease as an indirect consequence of system
events responsible by the server interruption. For
instance, the failure of the server in Fig. 1 may
render certain activities of the client unnecessary,
which would then reduce its service requirement
to a lower
value. Likewise, the age variable
a g related to the active request may also be affected
by the server interruption since the amount
of service already provided to the request may be
1 If the scheduling policy is non-work-conserving and the
service requirement of the client needs to be preserved then
even the EXP transition has to be dealt with like a GEN
transition.
preserved or lost. We distinguish both situations
calling the rst a work conserving scheme, and the
second non-work-conserving. With these four conditions
we constructed the table in Fig. 2b. Note
that, although the service requirement is shown to
be increasing after the interruption in the illustration
in the bottom row of the table, the situation
where
g is also possible 2 .
a)
a g
a g
work conserving
service
preserved
service
modified
a
a
a g
task
service started
service completed
prd
pri
prs
non-working-conserving

Figure

2: Dierent scheduling policies.
Fig. 2b can be interpreted from two distinct per-
spectives. From the clients' perspective, all curves
correspond to the same client whose service is momentarily
interrupted between times  2 and  3 .
From the server's perpective, clients requests live
only from interruption-to-interruption. There is a
single age variable associated with the server, and
what happens after interruptions is dened by the
scheduling policy which may be preemptive or non-
preemptive, depending on if the server swaps clients
before nishing service or not. Preemptive policies
are usually based on a hierarchical organization of
requests (e.g., priority scheduling) or on an allocation
of service based on time quotas (e.g., round-robin
scheduling). In this case, system behavior
is strongly aected by the preemptive policy and
Naturally,
ag at the time of the interruption needs
to be always imposed.
the overall performance will depend on the strategy
adopted to deal with the preempted requests,
as described in the following:
The work done on the request prior to interruption
is discarded so that the amount of
work a g is lost. The server starts processing
a new request which has a work requirement
0; i.e., a new sample is drawn from the service
time distribution of the client. The server then
starts serving this new request from the beginning
(i.e., a shown in the bottom-right
sketch in Fig. 2b.
The server returns back to the preempted request
with the original service requirement
.
No work is lost so that the age variable retains
its value a g prior to the interruption. The request
is resumed from the point of interruption
as shown in the top-left sketch in Fig. 2b.
The server also returns to the same request
with the original service requirement
. But
the work done prior to the interruption is lost
and the age variable a g is set to zero. The
request processing starts from the beginning
as shown in the top-right sketch in Fig. 2b.
As in [13], the above policies are referred to as
preemptive repeat dierent (prd), preemptive resume
(prs) and preemptive repeat identical (pri),
respectively 3 . The case shown in the bottom-left
sketch in Fig. 2b is not considered in the literature
as it is unrealistic. Note that in [15], the authors
indicated the prd and prs type policies as enabling
and age type. The pri policy of Petri net transitions
was introduced for the rst time in [16]. The prd
and prs (with phase-type distributed ring times)
policies are the only ones considered in the available
tools modeling NMSPNs [17, 11, 18, 19].
Note that when the scheduling is preemptive: (i)
the prs and prd policies produce the same results
with EXP transitions, but pri is dierent; (ii) The
prd and pri policies have the same eect for transitions
ring according to a deterministic random
variable, but prs is dierent; and (iii) otherwise,
all three policies will produce distinct results for
otherwise same NMSPNs [14].
3 The prd, prs and pri names were borrowed from queueing
theory [14].
In this paper, we deal with the general class of
non-Markovian Petri nets using examples of MR-
SPNs, which can be analyzed by means of Markov
regenerative processes. The remaining sections of
the paper are organized as follows. The next section
introduces Markov Regenerative Petri nets and
describes how to deal with the underlying Markov
Regenerative Process. Section 3 shows how to
model a failure/repair process in a parallel machine
through MRSPN. Section 4 further extends
this model by adopting a dierent repair facility
scheduling scheme. Preemption in a multi-tasking
environment is analyzed in Section 5 through the
WebSPN tool; the resulting model contains several
concurrently enabled general transitions and
dierent memory policies. Conclusions are nally
presented in Section 6.
Regenerative Petri
Nets
MRSPNs allow transitions with zero ring times
(immediate transitions), exponentially distributed
or generally distributed ring times. The dynamic
behavior of an MRSPN is modeled by the execution
of the underlying net, which is controlled by the position
and movement of tokens. At any given time,
the state of an MRSPN is dened by the number
of tokens in each of its places, and is represented
by a vector called its marking. The set of markings
reachable from a given initial marking (i.e., the initial
state of the system) by means of a sequence of
transition rings denes the reachability set of the
Petri net. This set together with arcs joining its
markings and indicating the transition that cause
the state transitions is called reachability graph.
Two types of markings can be distinguished in
the reachability graph. In a vanishing marking at
least one immediate transition is enabled to re,
while in a tangible marking no immediate transitions
are enabled. Vanishing markings are eliminated
before analysis of the MRSPN using elementary
probability theory [12]. The resultant
reduced reachability graph is a right-continuous,
piecewise constant, continuous-time stochastic process
represents the tangible
marking of the MRSPN at time t. Choi, Kulkarni,
and Trivedi [12] showed that this marking process
is a Markov Regenerative Process (MRGP) (if the
GEN transitions are of prd type and at most one
GEN transition is enabled at a time), a member of
a powerful paradigm generally grouped under the
name Markov renewal theory [7, 8]. Mathematical
denition and solution techniques for MRGP are
summarized next.
2.1 Markov Renewal Sequence
Assume a given system we are modeling is described
by a stochastic process Z d
taking values in a countable set . Suppose we
are interested in a single event related with the
system (e.g., when all system components fail).
Additionally, assume the times between successive
occurrences of this type of event are independent
and identically distributed (i:i:d:) random
variables. be the
time instants of successive events to occur. The
sequence of non-negative i:i:d: random variables,
:::gg is a renewal
process [20, 21]. Otherwise, if we do not start observing
the system at the exact moment an event
has occurred (i.e., S 0 6= 0) the stochastic process S
is a delayed renewal process.
However, suppose instead of a single event, we
observe that certain transitions between identi-
able system states Xn of a
subset
of
,
also resemble the behavior just described, when
considered in isolation. Successive times Sn at
which a xed state Xn is entered form a (possi-
bly delayed) renewal process 4 . Additionally, when
studying the system evolution we observe that at
these particular times the stochastic process Z exhibits
the Markov property, i.e., at any given moment
Sn , n 2 N , we can forget the past history of
the process. The future evolution of the process depends
only on the current state at these embedded
time points. In this scenario we are dealing with a
countable collection of renewal processes progressing
simultaneously such that successive states visited
form an embedded discrete-time Markov chain
(EMC) with state
space
The superposition of
all the identied renewal processes gives the points
known as Markov regeneration epochs
(also called Markov renewal moments 5 ), and to-
4 We are assuming Xn is the system state at time Sn .
5 Note that these instants Sn are not renewal moments
gether with the states of the EMC dene a Markov
renewal sequence.
In mathematical terms, the bivariate stochastic
process (X; S) d
is a Markov renewal
sequence (MRS) provided that
for all n 2 N ,
and t  0. We will always
assume time-homogeneous MRS's; that is, the conditional
transition probabilities
are independent of n for any
fore, we can always write
The matrix of transition probabilities K(t) d
is called the kernel of the MRS.
2.2 Markov Regenerative Processes
A stochastic process fZ t ; t  0g is a Markov regenerative
process i it exhibits an embedded MRS
(X,S) with the additional property that all conditional
nite distributions of fZSn+t ; t  0g given
are the same as
those of fZ As a special
case, the denition implies that [8]
This means that the MRGP fZ
does not have the Markov property in gen-
eral, but there is a sequence of embedded time
points such that the states
respectively of the process at
these points satisfy the Markov property. It also
implies that the future of the process Z from
onwards depends on the past fZ
only through
The stochastic process between consecutive
Markov regeneration epochs, usually refered to
as described in renewal theory, since the distributions of the
time interval between consecutive moments are not necessarily
i.i.d.
as subordinated process, can be any continuous-time
discrete-state stochastic process over the same
probability space. Recently published examples
considered subordinated homogeneous CTMCs [12,
22], non-homogeneous CTMCs [23], semi-Markov
processes (SMPs) [24], and MRGPs [25].
2.3 Solution of Problems
0g be a stochastic process with
discrete state space  and embedded MRS
K(t). For such
a process we can dene a matrix of conditional transition
probabilities as:
In many problems involving Markov renewal pro-
cesses, our primary concern is nding ways to effectively
since several measures of
interest (e.g., reliability and availability) are related
to the conditional transition probabilities of
the stochastic process.
At any instant t, the conditional transition probabilities
of Z can be written as [7, 8]:
for all i 2
we construct a
then the set of integral equations V ij (t) denes a
Markov renewal equation, and can be expressed in
matrix form as
Z tdK(u)V(t u); (1)
where the Lebesgue-Stieltjes integral 6 is taken term
by term.
To better distinguish the roles of matrices E(t)
and K(t) in the description of the MRGP we callR tdK(u)V (t
a density function
dt .
the matrix E(t) as the local kernel of the MRGP,
since it describes the state probabilities of the subordinated
process during the interval between successive
Markov regeneration epochs. Since matrix
K(t) describes the evolution of the process from
the Markov regeneration epoch perspective, without
describing what happens in between these moments
we call it the global kernel of the MRGP.
In the special case when the stochastic process Z
does not experience state transitions between successive
Markov regeneration epochs; i.e.,
Z is called a semi-Markov process and E(t) is a
diagonal matrix with elements
where
is the sojourn time distribution in state i. Hence,
the global kernel matrix alone (which in this case is
usually denoted as Q(t)) completely describes the
stochastic behavior of the SMP.
The Markov renewal equation represents a set
of coupled Volterra integral equations of the second
kind [26] and can be solved in time-domain
or in Laplace-Stieltjes domain. One possible time
domain solution is based on a discretization approach
to numerically evaluate the integrals presented
in the Markov renewal equation. The integrals
in Eqn. 1 are solved using some approximation
rule such as trapezoidal rule, Simpson's rule
or other higher order quadrature methods. Another
time domain alternative is to construct a system
of partial dierential equations (PDEs), using
the method of supplementary variables [4]. This
method has been considered for steady-state analysis
of DSPNs in [22] and subsequently extended to
the transient case in [27].
An alternative to the direct solution of the
Markov renewal equation in time-domain is the
use of transform methods. In particular, if we
st dE(t) and V
st dV(t), the Markov renewal equation become

After solving the linear system for V  (s), transform
inversion is required 7 . In very simple cases,
a closed-form inversion might be possible but in
most cases of interest, numerical inversion will be
necessary. The transform inversion however can
encounter numerical di-culties especially if V
has poles in the positive half of the complex plane.
For a thorough discussion of Markov renewal
equation solution techniques see [28, 29], and for
generic Volterra integral equations numerical methods
see [30, 31]. References for the application
of Markov renewal theory in the solution of
performance and reliability/availability models see
[16, 32, 23, 28, 33, 34, 35, 36, 37].
Modeling Failure/Repair
Activities in a Parallel Machine
Conguration
The use and analysis of MRSPNs is initially demonstrated
using a computer system performability
model. Two machines (a and b) are working in a
parallel conguration sharing a single repair facility
with a First-Come First-Served scheduling
discipline. Due to the non-preemptive nature
of this discipline, we do not need age variables in
this case (once enabled all GEN transitions in the
model will never be disabled until ring). We assume
that both machines have exponential lifetime
distributions with constant parameters  a and  b
respectively. Whenever one of the machines fails it
immediately requests repair. When the single repair
facility is busy and a second failure occurs, the
second machine to fail waits in a repair queue until
the rst machine is put back into service. The
repair-time of the machines is dened by the general
distribution functions G a (t) and G b (t).
The overall behavior of the system can be understood
from the MRSPN illustrated in Fig. 3a.
Machine a is working whenever there is a token in
place P 1 . The EXP transition f a with rate  a represents
the failure of machine a. When machine a
fails, a token is deposited in place P 6 and its repair
is requested. If the repair facility is available (i.e.,
7 This being the approach addopted in the solution of all
examples presented in this paper.
a
f a
f a f b
a
r
f a f b
f a
f bc)
a
a
r
a b
a
f
f
r
b a
2: 3:
4: 5:
7:
a)
b)r
rb
a

Figure

3: Parallel system model: a) MRSPN; b)
reachability graph; and c) state transition diagram.
there is a token in place P 5 ), it is appropriated with
the ring of immediate transition i a . The GEN
transition r a , ring according to the distribution
function G a (t), represents the random duration of
repair. A token in place P 3 means that machine a
is queued waiting for the availability of the single
repair facility while machine b is undergoing repair
(there is a token in place P 7 ). A symmetrical set
of places and transitions describes the behavior of
machine b. The system is down whenever there are
no tokens in both the places P 1 and P 2 .
The reachability graph corresponding to the
Petri net is shown in Fig. 3b. Each marking in
the graph is a 7-tuple keeping track of the number
of tokens in places P 1 through P 7 . In the
graph, solid arcs represent state changes due to
the ring of immediate transitions or EXP tran-
sitions, while dotted arcs denote the ring of GEN
transitions. The vanishing markings (enclosed by
dashed ellipses in the diagram) are eliminated when
the reduced reachability graph is constructed (not
shown), and based on the reduced version we constructed
the state transition diagram of Fig. 3c.
Dene the stochastic process to
represent the system state at any instant, where
both machines are working at t
machine a is under repair while
machine b is working at t
3 if machine b is under repair while
machine a is working at t
4 if machine a is under repair while
machine b is waiting for repair at t
5 if machine b is under repair while
machine a is waiting for repair at t
Note that possible values of Z t are the labels corresponding
tangible markings in Fig. 3b. We are interested
in computing performability measures associated
with the system. To do so, we need to
determine the conditional probabilities PrfZ
5g. Analysis of the
resultant (reduced) reachability graph shows that
Z is an MRGP with an EMC dened by the states
1, 2, and 3;
i.e.,
3g. We can observe that
transitions to states 4 and 5 do not correspond to
Markov renewal epochs because they occur while
GEN transitions are enabled. An additional step
adopted before starting the synthesis of the kernel
matrices was the construction of a simplied state
transition diagram. Fig. 3c shows a simplied version
of the reduced reachability graph where the
markings were replaced by the corresponding state
indices. We preserved the convention for the arcs
and extended the notation by representing states
of the EMC by circles, and other states by squares.
The construction of kernel matrices can proceed
with the analysis of possible state transitions. The
only non-zero elements in global kernel matrix K(t)
correspond to the possible single-step transitions
between states of the EMC. Consequently, we have
the following structure of the matrix (identied directly
from Fig. 3c):
Let the random variables L a and L b be the respective
time-to-failure of the two machines, we can
determine K 1;2 (t) in the following way:
is the first one to failg
d

Z te  b   a e a d
Similarly,
is the first one to failg
Determination of the elements K 2;1 (t) and
K 2;3 (t) is quite alike, so we only show how K 2;1 (t) is
determined. The third row is completelly symmetrical
to the second, so it can be easily undestood
once K 2;1 (t) is understood. We need some auxiliary
variables to help in the explanation of the constructive
process of K 2;1 (t). Hence, we dene the
random variables R a and R b to respectively represent
times necessary to repair machines a and b.
The distribution function of R a (R b ) is G a (G b ).
Using this new variables we can compute K 2;1 (t):
of a is finished by time t
and b has not failed during the
repair of ag
Z tP rfL b > gdG a ()
dG a ()
Z te  b  dG a ():
To summarize, the elements of the global kernel
matrix are:
Z te  b  dG a ();
Z t1 e  b
dG a ();
Z te a dG b (); and
Z t1 e a
Note that the global kernel will always be a
square matrix. In this case with dimensions 3  3,
since we have 3 states in the embedded Markov
chain. However, the local kernel matrix is not necessarily
a square matrix, since the cardinality of the
state space of Z can be larger than the cardinality
of the state space of the embedded Markov chain.
This can be seen, for instance, in this system since
the embedded Markov chain has only 3 states while
the MRGP has 5 possible states.
We construct the local kernel matrix E(t) following
a similar inductive procedure. In this case we
are looking for the probability that the MRGP will
move to a given state before the next Markov renewal
moment. Careful analysis of Fig. 3c reveals
the structure of the local kernel matrix E(t):4 E 1;1 (t)
Since in a single step the system can only go from
state 1 to the other two states of the EMC then E 1;1
should be the complementary sojourn time distribution
function in state 1, that is,
The di-culty comes with the induction of E 2;2 (t)
(complement of E 2;2 (t)). Once we solve
for these, we have the solution for the remaining
components of the matrix due to the symetry of
the problem. Therefore, we explain the induction
process that leads to E 2;2 (t):
of a is not finished up to t
and b has not failed until tg
of a is not finished up to t
P rfb has not failed until tg
We can now express the remaining non-zero elements
of the local kernel matrix as
G c
a (t)
G c
with
G c
a
G c
We can always verify our answers by summing the
elements in each row of both kernel matrices. Corresponding
row-sums of the two matrices must add
to unity, condition that is easily veried to hold in
the example.
time (hours)0.9981.000
availability
instantaneous
interval
time (hours)1.921.962.00
interval
power
time (hours)0.9981.000
availability
instantaneous
interval
time (hours)1.921.962.00
interval
power
results:
results:

Figure

4: Numerical results for the parallel system
with non-premptive repair.
The kernel matrices determined can then be substituted
in Equation (1) and the resultant system
of coupled integral equations solved using one of
the approaches described in [28, 29]. The resultant
plots, labelled LST in Fig. 4, report system availability
and performability computed when time to
repair is deterministic; i.e.,
G a
where U(t) is the unit step function; the failure
rates (parameters  a and  b ) are identical  b ) takes
5 hours. The interval availability is the expected
proportion of time the system is operational during
the period [0; t]:
Z tE[X()]d;
when the discrete random variable X represents the
operational status of the system; i.e.,
the system is operatinal at time t, and 0 if it is not.
The performability measure plotted in the gure
corresponds to the interval processing capacity of
the system, with the convention that a unit of computing
capacity corresponds to that of one active
machine.
Following the approach used in [34], we also plotted
corresponding Markovian system results, where
each DET transition was replaced by an equivalent
25-stage Erlang subnet. The Markovian models
were solved using the Stochastic Petri Net Package
(SPNP) introduced in [38].
4 Preemptive LCFS repair
Fig. 5 shows the PN which describes the behavior of
the system containing the same machines a and b
of the previous example and applies the preemptive
LCFS scheduling scheme. The repair of machine a
(b), represented by a token at P 6 (P 7 ) is preempted
as soon as machine b (a) fails, i.e., transition f b (f a )
res. In this case the repair facility is assigned to
the machine which failed later (i 0
a or i 0
b res and a
token is placed to P 8 or P 9 ). After the repair of
the last failed machine (ring of r 0
a or r 0
b ) the repair
facility returns to the completion of preempted
repair action. Dierent memory policies can be
considered depending on whether the repairman is
able to \remember" the work already performed on
the machine before preemption or not. In the case
r r
r

6
?/
R
f a
i a
r a
a
a

Figure

5: Preemptive LCFS repair with non-identical
machines
that the prior work is lost due to the interruption
and the repair must be repeated from scratch with
an identical repair time requirement (pri policy) or
with a repair time resampled from the original cumulative
distribution function (prd policy). In the
case that the prior work is not lost and the time
to complete the preempted repair equals the residual
repair time given the portion of work already
completed before preemption (prs policy). The PN
on Fig. 5 captures the dierent memory policies for
repair by assigning transitions r a and r b the appropriate
preemption policies. (The preemption policies
of transitions r 0
a and r 0
b are not relevant since
a and r 0
b cannot be preempted.)
We analyze a simplied version of the two machine
system with preemptive LCFS repair and
with prs policy. We assume that the two machines
are statistically identical, i.e., their failure and repair
time distributions are the same. Fig. 6a shows
a PN which describes the behavior of the system of
two identical machines with LCFS scheduling. Tokens
in place tokens
in P 2 count failed machines (including the one
under repair), and a token in place P 4 the availability
of the single repair facility. In the initial marking
is the only enabled
transition. Firing of t 1 represents the failure of the
rst machine and leads to state M In
are competing. The GEN
transition t 2 represents the repair of the failed machine
and its ring returns the system to the initial
state M 1 . The EXP transition t 3 represents the
failure of the second machine and its ring disables
q
A
A AU
A
A AU
A
A AU
A
A AU
A
A AU

Figure

Preemptive LCFS repair with identical
machines
removing one token from P 3 (the rst repair
becomes dormant). In M
is under repair and the other repair is dormant,
and the only enabled transition is the repair of the
last failed machine. Firing of the GEN transition t 4
leads the system again to M 2 , where the dormant
repair is resumed. Assume that the failure times of
both machines are exponentially distributed with
parameter  so that the EXP transitions t 1 and t 3
have ring rates 2 and , respectively.
The preemptive policy of transition t 2 has to be
assigned based on the system behavior to be eval-
uated. (The preemptive policy of transition t 4 is
irrelevant since t 4 can not be preempted.) Assigning
a prd policy to t 2 means that each time t 2 is
disabled by the failure of the second machine (t 3
res before t 2 ), the corresponding age variable a 2
is reset. As soon as t 2 becomes enabled again (the
second repair completes and t 4 res) no memory is
kept of the prior repair period, and the execution
of the repair restarts from scratch. The prd service
policies, like this one, are covered by the model definition
in [39, 40].
The case when a pri policy is assigned to t 2 is
very similar to the previous one except that as soon
as t 2 becomes reenabled (the second repair completes
and t 4 res), the same repair (same ring
time sample) has to be completed from the begin-
ning. This type of pri memory policy is covered by
the model denition in [16], and can be analyzed
by the transform domain method discussed there.
Hereafter we assume that a prs policy is assigned
to t 2 . When a prs policy is assigned to t 2 , each time
t 2 is disabled without ring (t 3 res before t 2 ) the
age variable a 2 is not reset. Hence, as the second
repair completes (t 4 res), the system returns to
keeping the value of a 2 , so that the time to
complete the interrupted repair can be evaluated
as the original repair requirement minus the current
value of a 2 . The age variable a 2 counts the
total time during which t 2 is enabled before r-
ing, and is equal to the cumulative sojourn time in
. The Markov renewal moments in the marking
process correspond to the epochs of entrance
to markings in which the age variables associated
with all the transitions are equal to zero. By inspecting
Fig. 6b, the Markov renewal moments are
the epochs of entering M 1 and of entering M 2 from
The subordinated process starting from marking
1 is a single step CTMC (since t 1 the only enabled
EXP transition) and includes the only immediately
reachable state M 2 (Markovian regeneration
period).
The subordinated process starting from marking
includes all the states reachable from M 2 before
ring of t is the
only state in which t 2 is enabled, the age variable
a 2 increases only in marking M 2 and maintains its
value in M 3 . The ring of t 2 can only occur from
leading to marking M 1 .
Notice that the subordinated process starting
from M 2 is semi-Markov since the ring time of t 4
is generally distributed. The age variable a 2 grows
whenever the MRSPN is in marking M 2 , and the
ring of t 2 occurs when a 2 reaches the actual value
of the ring time (which is generally distributed
with cumulative distribution function G(t)). If we
condition that the ring time of t 2 to w, w acts an
absorbing barrier for the accumulation functional
represented by the age variable a 2 , the ring time
of t 2 is determined by the rst passage time of a 2
across the absorbing barrier w.
The closed form Laplace-Stieltjes transform expressions
of the kernel matrices of the LCFS repair
prs case are derived here in detail, applying
the technique based on the Markov renewal theory.
We build up the K  row
by row by considering separately all the states that
can be regeneration states and can originate a subordinated
process. M 3 can never be a regeneration
state since t 2 is always active when entering to M 3 ,
g. The fact that M 3 is not a regeneration
marking, means that the process can stay
in M 3 only between two successive Markov renewal
moments.
The starting regeneration state is M 1 - (Markovian
regeneration period) No general transition is enabled
and the next regeneration state can only be
state M 2 . The non-zero elements of the rst row of
the kernel matrices are
The starting regeneration state is M 2 - Transition t 2
is GEN so that the next regeneration time point is
the epoch of ring of t 2 . The subordinated process
starting from M 2 comprises states M 2 and M 3 and
is an SMP (since t 4 is GEN) whose kernel is:
G
where G  (s) is the LST of the distribution function
of the ring time of t 4 .
The transition t 2 res when the age variable a 2
reaches actual sample of the ring time
2 . In gen-
eral, when a GEN transition is active the occurence
of a Markov renewal epoch in the marking process
of an NMSPN is due to one of the following two
reasons:
the GEN transition res,
the GEN transition of prd type becomes disabled

For the analysis of subordinated processes of this
kind three matrix functions F i (t; w), D i (t; w) and
denotes the time, w a xed r-
ing time sample, and the superscript i refers to the
initial (regeneration) state of the subordinated pro-
cess) were introduced in [24]. F i (t; w) refers to the
case when the next regeneration moment is because
of the ring of the GEN transition with the (xed)
ring time sample w. For the analysis of this case
an additional matrix ( i referred to as branching
probability matrix) is introduced, as well, to describe
the state transition subsequent to the ring
of the GEN transition. D i (t; w) captures the case
when the next regeneration moment is caused by
the disabling of the prd type GEN transition. And
describes the state transition probabilities
inside the regeneration period.
Since transition t 2 is of prs type the matrix function
does not play a role in the analysis
of the subordinated process starting from marking
. The remaining functions can be evaluated
based on the kernel of the subordinated SMP
u' (s; v)
s
u' (s; v)
k' (t); s is the time variable and
v is the barrier level variable in transform domain;
r k is the indicator that the active GEN transition
is enabled in state k; R i is the part of the state
space reachable during the subordinated process;
and the superscript  () refers to Laplace-Stieltjes
(Laplace) transform.
Given that G g (t) is the distribution function of
the ring time of the GEN transition, the elements
of the i-th row of matrices K(t) and E(t) can be
expressed as follows, as a function of the matrices
dG g (w)
To evaluate the 2nd row of the kernel matrices
we are applying these results for the subordinated
process starting from regeneration state M 2 . Doing
so we obtain the following expressions for the non-zero
matrix entries:
F
22 (s;
22 (s;
Unconditioning with respect to the ring time distribution
of t 2 , and after inverting the Laplace
transform (LT) with respect to v, the non-zero entries
of the 2nd row of the LST matrix functions
K
e w(s+  G  (s)) dG(w)
22
The LST of the state probabilities are obtained
by solving the Markov renewal equation in transform
domain. The time domain probabilities are
calculated by numerically inverting the result by
resorting to the Jagerman method [41].
To evaluate the performance of the dierent
scheduling schemes, we compared the availability
and processing power of the FCFS and the LCFS
repair schemes with two dierent repair time dis-
tributions. The FCFS scheme was evaluated by
the time domain method introduced in the previous
section and the LCFS scheme was evaluated
by the above transform domain method. It is assumed
that the system is available when at least
one machine is working (marking M 1 and M 2 ) and
that the system performance doubles when both
machines are working. The failure times of both
machines are exponentially distributed with rates
0:01. The repair times of both
machines are assumed to be:
deterministic
G
hyperexponentially distributed with
G
The mean repair time is 5 in both cases. Fig. 7a
and 7b show the instantaneous and the interval
measures of availability and processing power with
deterministic repair time, respectively. The dotted
line shows the instantaneous and the short
dashed line shows the interval availability/power
with LCFS repair, while the long dashed line shows
the instantaneous and the solid line shows the interval
availability/power with FCFS repair. It can be
observed that the FCFS scheduling performs better
in this case. The availability and processing power
results for the hyperexponential repair time distribution
are plotted on Fig. 7c and 7d, respectively.
In these gures the dotted line shows the instantaneous
availability/power with LCFS repair, while
the dashed line shows the instantaneous availabil-
ity/performability with FCFS repair. As can be
seen from these gures, in contrast with the deterministic
repair time the LCFS scheduling performs
better with the hyperexponential repair time distribution

Modeling preemption in a
multi-tasking environment
NMSPN require complex solution techniques
mainly based on theory of Markov regenerative pro-
cesses. Software packages are then required which
can hide solution and implementation details. A
big boost in this direction came from two well-known
tools, DSPNexpress [42] and TimeNET [43,
44]. Recently, a new software package for non-Markovian
Petri nets has been developed in a joint
eort between the Universities of Catania and Bu-
dapest. This tool, named WebSPN [45],
provides a discrete time approximation of the
stochastic behaviour of the marking process which
results in the possibility to analyze a wider class
of PN models with prd, prs and pri concurrently
enabled generally distributed transitions. The approximation
of the continuous time model at equispaced
discrete time points involves the analysis
of the system behavior over a time interval based
on the system state at the beginning of the interval
and the past history of the system. A Web-
centered view has been adopted in its development
in order to make it easily accessible from
any node connected with the Internet as long as
it possesses a Java-enabled Web browser. Sophisticated
security mechanisms have also been implemented
to regulate the access to the tool which are
based on the use of public and private electronic
keys. WebSPN is available at the following site:
http://sun195.iit.unict.it/webspn/webspn2/
5.1 Model description
In this section we describe and solve a model of
Petri net with several concurrently enabled GEN
transitions and dierent memory policies. The system
moves between an operative phase, where useful
work is produced, and a phase of maintenance
where the processing is temporarily interrupted.
The Petri net shown in Fig. 8 represents the
model of the system that consists of three functional
blocks generically referred to as Block1,
Block2 and Block3. Block1 models the alternation
of the system between the operative phase and the
maintenance phase. Block2 models the two sequential
phases of processing of jobs. Finally, Block3
models the alternation of the system during the operative
phase between the phase of pre-processing
and the one of processing of jobs.
Within Block1, the two states of operation where
the system can be are represented by places user
and system and by transitions U time and S time.
A token in place user denotes the operative state,
while a token in place system denotes the maintenance
one. The duration of the operative phase
is denoted by transition U time, while the maintenance
one is denoted by transition S time. The inhibitor
arcs outgoing from place system and leading
to the timed and immediate transitions contained
in Block2 and Block3 producer, cons1, busy prod,
idle prod, busy2, idle2 are used for interrupting the
activity of the system during the phase of maintenance

Block2 models the processing of jobs. In partic-
ular, the number of jobs to be processed is denoted
by the number of tokens contained in place work,
while the time of pre-processing of each job is represented
by transition producer. Pre-processed jobs
are queued in a buer (place bu1) waiting for the
second phase of processing (transition cons1).
In Block3, the alternation between the phases
of pre-processing and processing of jobs is represented
through places slot1 and slot2 and transitions
busy brod, busy2, idle prod, idle2. A token in
place slot1 denotes that the system is executing the
pre-processing of a job, while a token in place slot2
denotes the execution of a phase of processing. An
inhibitor arc between slot1 and cons1 deactivates
the phase of processing when the pre-processing
one is active. In the same way, the inhibitor arc
between slot2 and producer deactivates the phase
of pre-processing when the processing one is ac-
tive. The time that the system alternately spends
for these two activities is represented by transitions
busy prod and busy2. The immediate transition
idle prod (idle2) prevents the system to remain in
phase 1 (2), even if no job is to be processed. The
function of the inhibitor arcs from place work to
transition idle prod and from place bu to transition
idle2 is to enable such transitions when no job
is to be processed in the corresponding phase of
processing.
Immediate transition end and place Stop are used
for modeling the processing of all the jobs assigned
to the system at the beginning. In fact, transition
end is inhibited until at least one token is present
in places work and bu. When all the jobs have
been processed, transition end res, and immediately
moves a token to place Stop. All the activities
of the system are thus interrupted through the
inhibitor arcs outgoing from place Stop.
The measure that we evaluate from this model is
the distribution of the time required for completing
the set of jobs assigned to the system at the
beginning. It can be obtained as the distribution
of having a token in place Stop.
With regard to the distributions of the ring
times to be assigned to timed transitions, we assume
that the ring times of transitions U time,
S time, busy brod, busy2 are deterministic. We
assume that the ring times of transitions producer
and cons1 are respectively distributed uniformly
and exponentially. The measures considered
can therefore be evaluated by changing the memory
policy associated with transitions producer and
cons1.
In the case of prd policy, the temporary interruption
of the processing of a job (either because
the whole system enters the phase of maintenance,
or because, even if the system is in the production
phase, it interrupts the pre-processing phase
for changing to the processing one or vice versa)
causes the interrupted job to be discarded. A new
job is executed when the system is available again.
The correspondence with a real system is perhaps
hard to nd; however, we note that prd policy is
the most commonly used one in the literature.
Conversely, by adopting prs policy, we keep a
memory of the work that we were executing. In
this case, when transition producer is disabled, we
keep a memory of the work that has already been
executed on the job considered. When the system
enters the operative state again, the pre-processing
of the job continues from the point we had reached.
In this case, the model can represent a system of
manufacturing, where a machine used for production
alternates cycles of production and cycles of
maintenance, and production takes place in two sequential
phases. We note that prd and prs policies
are equivalent for transition cons1, since this one is
and EXP transition.
With pri policy, when transition producer is dis-
abled, the work that had already been produced
is lost, but we keep a memory of the job that we
were processing. When the transition is enabled
again we start from zero, but the amount of work
to be produced on the job remains the same, because
the job has not been changed. Such a behavior
can be easily noted when accessing transactional
databases, where each transaction is atomic
(i.e., has to be processed with no interruption). If
an interruption occurs, the transaction is entirely
processed again. If we assume a memory policy like
prs for transition cons1, the model could represent a
client/server system where the accesses to database
(transition producer) take place atomically, and the
phase of processing of the query (transition cons1)
requires a variable time, distributed exponentially.
5.2 Numerical Results
For the solution of the model we assume that the
ring time of transition producer is distributed uniformly
between 0.5 and 1.5; the ring time of transitions
time and S time are deterministic, with
a ring time of 1; the ring time of transitions
busy prod and busy2 are deterministic, with a r-
ing time of 0.1; the ring time of transition cons1
is distributed exponentially, with a ring rate of
transition end is immediate and has a priority
of 2; transitions idle prod and idle2 are immediate
and have a priority of 1; the total number of jobs
to be processed is 3.
In Fig. 9 we show the distribution of completion
time for dierent memory policies assigned to
transitions producer and cons1. The behavior of
the system changes signicantly depending upon
the memory policy adopted. The prs policy accrues
the highest probability of completion within
a given time. Both the prd and the prs policies
accomplish the completion of jobs. In fact, curves
eventually reach the value 1. Conversely, a dier-
ent behavior can be observed if we assume a policy
like pri. In fact, in that case, the resulting distribution
is defective, since the unit value is never
reached for t ! 1. This is closely connected with
the choice of the parameters associated with transitions
producer and U time. As we note in Fig. 10,
when the ring time of transition U time is lower
than 1.5, transition producer has a positive probability
(50%)of not completing its work. Since in
the case of pri policy the job is processed with the
same work requirement, this causes a situation of
impasse, which prevents the work assigned to the
system to be completed.
Fig. 11 shows how the overall system behavior
changes if transition U time is assigned a ring time
higher than 1.5 (for example 2.0). In such case,
transition producer has a nite probability of ring
before the system enters the phase of maintenance,
and therefore the distribution of completion time
with pri policy reaches the value 1.
6 Conclusion
We discussed the need for more advanced techniques
to capture generally distributed events
which occur in everyday life. Among the dier-
ent approaches proposed in the literature, non-Markovian
nets represent a valid analytical
alternative to numerical simulation. An approach
based on the analysis of the underlying Markov Regenerative
Process has been presented. Advanced
preemption policies were introduced and several examples
solved in detail.



--R








Modeling and Analysis of Stochastic Systems











Renewal Theory
An Introduction to Probability Theory and Its Applications




The Theory of The Volterra Integral Equation of the Second Kind



The Numerical Solution of Volterra Equations
Analytical and Numerical Methods for Volterra Equations















--TR

--CTR
Giacomo Bucci , Andrea Fedeli , Luigi Sassoli , Enrico Vicario, Timed State Space Analysis of Real-Time Preemptive Systems, IEEE Transactions on Software Engineering, v.30 n.2, p.97-111, February 2004
stochastic Petri nets;numerical analysis;markov regenerative processes;preemption policies