Petri Nets and Timed Petri Nets in Modeling and Analysis of Concurrent Systems – An Overview

Zuberek, W. M. (2003) Petri Nets and Timed Petri Nets in Modeling and Analysis of Concurrent Systems – An Overview. Research Report. Memorial University of Newfoundland, St. John's, Newfoundland and Labrador.

[English] PDF - Published Version Available under License Creative Commons Attribution Non-commercial. Download (525kB)

Abstract

Petri nets are formal models of systems which exhibit concurrent activities. Communication networks, multiprocessor systems, manufacturing systems and dis- tributed databases are simple examples of such systems. As formal models, Petri nets are bipartite directed graphs, in which the two types of vertices represent, in a very gen- eral sense, conditions and events. An event can occur only when all conditions associated with it (represented by arcs directed to the event) are satisfied. An occurrence of an event usually satisfies some other conditions, indicated by arcs directed from the event. So, an occurrence of one event causes some other event to occur, and so on. In order to study performance aspects of systems modeled by Petri nets, the durations of modeled activities must also be taken into account. This can be done in different ways, resulting in different types of temporal nets. In timed Petri nets, occurrence times are associated with events, and the events occur in real–time (as opposed to instantaneous oc- currences in other models). For timed nets with constant or exponentially distributed occurrence times, the state graph of a net is a Markov chain, in which the stationary prob- abilities of states can be determined by standard methods. These stationary probabilities are used for the derivation of many performance characteristics of the model. Analysis of net models based on exhaustive generation of all possible states is called reachability analysis; it provides detailed characterization of model’s behavior, but often re- quires generation and analysis of huge state spaces (in some models the number of states increases exponentially with some model parameters, which is known as “state explo- sion”). Structural analysis determines the properties of net models on the basis of connections among model elements; structural analysis is usually much simpler than reachability analysis, but can be applied only to models satisfying certain properties. If neither reachability nor structural analysis is feasible, discrete–event simulation of timed nets can be used to study the properties of net models. This paper overviews basic concepts of Petri nets, intro- duces timed Petri nets, and provides brief summaries of sev- eral case studies of performance analysis which are discussed in greater detail in other publications of the author.

Actions (login required)

View Item