M-timed Petri nets, priorities, preemptions, and performance evaluation
Advances in Petri Nets 1985 (Lecture Notes in Computer Science 222),
Springer-Verlag 1986, pp.478-498.
In M-timed Petri nets, firing times are exponentially distributed random
variables associated with transitions of a net.
Several classes of M-timed Petri nets are discussed in this paper to
show increasing "modelling power" of different nets. Conflict-free
nets can model M- and E-type queueing systems. Free-choice
nets can also represent H-type systems. Systems with several
classes of users and with service priorities assigned to user classes
require nets with inhibitor arcs. Preemption of service can be represented
by extended nets with escape (or generalized inhibitor) arcs. Finally,
to provide flexible modelling of scheduling and decision strategies,
enhanced Petri nets are introduced with two classes
of transitions, immediate and timed ones, and with (exponentially
distributed) firing times associated with the timed transitions.
It is shown that the behaviour of bounded M-timed Petri nets
can be represented by finite state graphs which are finite-state
continuous-time homogeneous Markov processes. Stationary probabilities
of states can thus be obtained by standard techniques used for analysis
of Markov chains, and then operational analysis can be applied for
performance evaluation. Simple models of interactive systems are used
as an illustration of modelling.
Timed Petri nets, state description, state graphs, Markov chains,
stationary probabilities, reachability analysis.
T. Agerwala, "Putting Petri nets to work"; IEEE Computer Magazine,
vol.12, no.12, pp.85-94, 1979.
T. Agerwala, M. Flynn, "Comments on capabilities and 'correctness' of
Petri nets"; Proc. First Annual Symp. on Computer Architecture, Gainesville
FL, pp.81-86, 1973.
M. Ajmone Marsan, G. Conte, G. Balbo, "A class of generalized stochastic
Petri nets for the performance evaluation of multiprocessor systems";
ACM Trans. on Computer Systems, vol.2, no.2, pp.93-122, 1984.
B. Bayaert, G. Florin, P. Lonc, S. Natkin, "Evaluation of computer
systems dependability using stochastic Petri nets"; Proc. 11-th Annual
Int. Symp. on Fault-Tolerant Computing, Portland, MA, pp.79-81, 1981.
B. Berthomieu, M. Menasche, "An enumerative approach for analyzing
time Petri nets"; Information Processing 83, R.E.A. Mason (ed.),
pp.41-45, IFIP 1983.
W. Brauer (ed.), Net theory and applications; Proc. Advanced
Course on General Net Theory of Processes and Systems, Hamburg 1979
(Lecture Notes in Computer Science 84); Springer-Verlag 1980.
J.P. Buzen, "Fundamental operational laws of computer system
performance"; Acta Informatica, vol.7, no.2, pp.167-182, 1976.
J. Carlier, P. Chretienne, C. Girault, "Modelling scheduling problems
with timed Petri nets"; in Advances in Petri Nets 1984
(Lecture Notes in Computer Science 188); G. Rozenberg (ed.),
pp.62-82, Springer-Verlag 1985.
A. Danthine, "Modeling and verification of end-to-end protocols";
in New Advances in Distributed Computer Systems (Proc. NATO Advanced
Study Institute, Bonas, France, June 1982), K.G. Beauchamp (ed.),
pp.125-158, Reidel Publ. Co. 1982.
P.J. Denning, J.P. Buzen, "The operational analysis of queueing
network models"; Computing Survey, vol.10, no.3, pp.225-261, 1978.
M. Diaz, "Modeling and analysis of communication and cooperation protocols
using Petri net based models";
Computer Networks, vol.6, no.6, pp.419-441, 1982.
D. Ferrari, Computer systems performance evaluation;
E. Gelenbe, I. Mitrani, Analysis and synthesis of computer systems;
Academic Press 1980.
C. Girault, W. Reisig (eds.), Application and theory of Petri nets
(Informatik-Fachberichte 52); Springer-Verlag 1982.
M. Hack, "Analysis of production schemata by Petri nets"; Project
MAC Technical Report TR-94, Massachusetts Institute of Technology,
Cambridge MA, 1972.
L. Kleinrock, Queueing systems, vol.1: "Theory",
vol.2: "Computer applications"; J. Wiley & Sons 1975, 1976.
S.R. Kosaraju, "Limitations of Dijkstra's semaphore primitives and
Petri nets"; Operating Systems Review, vol.7, no.4, pp.122-126, 1973.
E.D. Lazowska, J. Zahorjan, G.S. Graham, K.C. Sevcik, Quantitative system
performance - computer system analysis using queueing network models;
P.M. Merlin, D.J. Farber, "Recoverability of communication protocols -
implications of a theoretical study"; IEEE Trans. on Communications,
vol.24, no.9, pp.1036-1049, 1976.
M.K. Molloy, "Performance analysis using stochastic Petri nets";
IEEE Trans. on Computers, vol.31, no.9, pp.913-917, 1982.
S. Natkin, "Timed and stochastic Petri nets: from the validation to
the performance of synchronization schemes";
Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.2-3, 1985.
A. Pagnoni, G. Rozenberg (eds.), "Applications and theory of Petri
nets" (Informatik-Fachberichte 66); Springer-Verlag 1983.
J.L. Peterson, Petri net theory and the modeling of systems,
C. Ramchandani, "Analysis of asynchronous concurrent systems by
timed Petri nets"; Project MAC Technical Report TR-120,
Massachusetts Institute of Technology, Cambridge, MA, 1974.
R.R. Razouk, "The derivation of performance expressions for
communication protocols from timed Petri nets"; Computer Communication
Review, vol.14, no.2, pp.210-217, 1984.
J. Sifakis, "Use of Petri nets for performance evaluation"; in
Measuring, modelling and evaluating computer systems, pp.75-93,
"Timed Petri nets and preliminary performance evaluation";
Proc. IEEE 7-th Annual Symp. on Computer Architecture,
La Baule, France, pp.88-96, 1980.
"Performance evaluation using extended timed Petri nets";
Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.37-42, 1985.
W.M. Zuberek, "Modelling and performance evaluation of systems
using enhanced timed Petri nets"; Proc. 12-th IASTED Conf. on Applied
Simulation and Modelling, Montreal, Canada, pp.154-157, 1985.
"M-timed Petri nets and Markov chains in modelling of computer systems";
Proc. ACM 14-th Annual Computer Science Conf., Cincinnati, OH, pp.101-106,