M-timed Petri nets, priorities, preemptions, and performance evaluation of systems

Zuberek, W.M.

Advances in Petri Nets 1985 (Lecture Notes in Computer Science 222), Springer-Verlag 1986, pp.478-498.

Abstract:

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.

Keywords:

Timed Petri nets, state description, state graphs, Markov chains, stationary probabilities, reachability analysis.

References:

• 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; Prentice-Hall 1978.
• 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; Prentice-Hall 1984.
• 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, Prentice-Hall 1981.
• 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, North-Holland 1977.
• W.M. Zuberek, "Timed Petri nets and preliminary performance evaluation"; Proc. IEEE 7-th Annual Symp. on Computer Architecture, La Baule, France, pp.88-96, 1980.
• W.M. Zuberek, "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.
• W.M. Zuberek, "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, 1986.