Augmented M-timed Petri nets, modeling and performance evaluation of computer systems

Zuberek, W.M.

Transactions of the Society for Computer Simulation, vol.2, no.2, pp.135-153, 1985.

Abstract:

It is shown that the behavior of augmented (i.e., generalized and extended) free-choice Petri nets with exponentially distributed firing times can be represented by probabilistic state graphs. For bounded Petri nets the corresponding state graphs are finite, stationary descriptions can thus be obtained by standard techniques used for analysis of continuous-time finite-state Markov chains. An immediate application of such a model is performance analysis of concurrent systems, and in particular queueing systems with exponentially distributed interarrival and service times. Places of Petri nets correspond to systems queues, transitions to servers, inhibitor arcs are used to indicate priorities, and bulk arrivals or services are conveniently modelled by generalized (multiple) arcs. Simple models of interactive computer systems are used as an illustration of performance evaluation.

Keywords:

Timed Petri nets, state graphs, Markov chains, performance analysis.

References:

• T. Agerwala, "Putting Petri nets to work"; IEEE Computer Magazine, vol.12, no.12, pp.85-94, 1979.
• 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. Berthomieu, M. Menasche, "An enumerative approach for analyzing time Petri nets"; Information Processing 1983, R.E.A. Mason (ed.), pp.41-45, IFIP 1983.
• W. Brauer (ed.), "Net theory and applications" (Proc. of the Advanced Course on General Net Theory of Processes and Systems, Hamburg 1979; Lecture Notes in Computer Science 84); Springer-Verlag 1980.
• M. Diaz, "Modeling and analysis of communication and cooperation protocols using Petri net based models"; Computer Networks, vol 6, no.4, pp.419-441, 1982.
• D. Ferrari, Computer systems performance evaluation; Prentice-Hall, Englewood Cliffs NJ, 1978.
• K. Garg, "An approach to performance specification of communication protocols using timed Petri nets"; Proc. 4-th International Conf. on Distributed Computing Systems, San Francisco CA, pp.202-211, 1984.
• L. Kleinrock, Queueing systems, vol.1: "Theory", vol.2: "Computer applications"; J. Wiley & Sons 1975, 1976.
• H. Kobayashi, Modeling and analysis - an introduction to system performance evaluation methodology; Addison-Wesley, Reading MA, 1978.
• Y.E. Lien, "Termination properties of generalized Petri nets"; SIAM Journal on Computing, vol.5, no.2, pp.251-265, 1976.
• J. Magott, "Performance evaluation of concurrent systems using Petri nets"; Information Processing Letters, vol.18, no.1, pp.7-13, 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.
• J.L. Peterson, "Petri nets"; ACM Computing Surveys vol.9, no.3, pp.223-252, 1977.
• J.L. Peterson, Petri net theory and the modeling of systems; Prentice-Hall, Englewood Cliffs NJ, 1981.
• S. Porat, M. Yoeli, "Towards a hierarchy of nets"; Journal of Computer and System Sciences, vol.29, no.2, pp.198-206, 1984.
• C. Ramchandani, "Analysis of asynchronous concurrent systems by timed Petri nets"; Project MAC Technical Report MAC-TR-120, Massachussetts 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.89-96, 1980.
• W.M. Zuberek, "Application of timed Petri nets to analysis of multiprocessor realizations of digital filters"; Proc. 25-th Midwest Symp. on Circuits and Systems, Houghton MI, pp.134-139, 1982.
• W.M. Zuberek, "Performance evaluation of concurrent systems using timed Petri nets"; Proc. ACM 13-th Annual Computer Science Conf., New Orleans LA, pp.326-329, 1985.