SYSTEM MODELLING WITH PETRI NETS Andrea BOBBIO Istituto Elettrotecnico Nazionale Galileo Ferraris Strada delle Cacce 91 10135 Torino Italy Reprinted from A G Colombo and A Saiz de Bustamante eds System Reliability Assessment Kluwer p c pp 102 143 1990 CONTENTS 1 Introduction 1 2 List of Symbols 2 3 The Primitive Elements of a Petri Net 3 4 Petri Nets and the Modelling of Systems 5 4 1 CONCURRENCY OR PARALLELISM 5 4 2 SYNCHRONIZATION 6 4 3 LIMITED RESOURCES 6 4 4 SEQUENTIALITY THE PRODUCER CONSUMER PROBLEM 7 4 5 MUTUAL EXCLUSION CONFLICT 8 5 Properties of Petri Nets 8 5 1 LIVENESS 8 5 2 SAFENESS 9 5 3 BOUNDEDNESS 9 5 4 CONSERVATION 9 6 Analysis Techniques 10 6 1 THE REACHABILITY TREE AND REACHABILITY GRAPH 10 6 2 MATRIX ANALYSIS 12 6 2 1 Reachability 14 6 2 2 Conservation 15 6 2 3 Place Invariant 15 7 Extensions 15 7 1 INHIBITOR ARCS 16 7 2 PRIORITY LEVELS 16 7 3 CONDITIONING FUNCTIONS 16 7 4 HIGH LEVEL PETRI NETS 17 ii 8 Timed Petri Nets 18 9 Homogeneous Markov SPN HMSPN 19 9 1 FORMAL DEFINITION OF THE MODEL 21 9 2 MARKING DEPENDENT FIRING RATES 22 9 3 IMMEDIATE AND TIMED PN TRANSITIONS 23 10 Computation of Measures of Reliability and Performance 26 10 1 PROBABILITY OF A GIVEN CONDITION ON THE SPN 27 10 2 EXPECTED TIME SPENT IN A MARKING 27 10 3 MEAN PASSAGE TIME 28 10 4 DISTRIBUTION OF TOKENS IN A PLACE 28 10 5 EXPECTED NUMBER OF FIRINGS OF A PN TRANSITION 28 11 Performance Reliability Modelling through SPN 29 11 1 PARALLEL UNITS WITH SHARED RESOURCE 29 11 2 PARALLEL SYSTEM WITH FINITE INPUT BUFFER 32 12 Simulative Analysis of SPN 36 13 Conclusion 38 13 References 38 iii SYSTEM MODELLING WITH PETRI NETS Andrea BOBBIO Istituto Elettrotecnico Nazionale Galileo Ferraris Strada delle Cacce 91 10135 Torino Italy ABSTRACT Petri Nets PN are a graphical formalism which is gaining popularity in recent years as a tool for the representation of complex logical interactions like synchronization sequentiality concurrency and conflict among physical components or activities in a system This notes are devoted to introduce the formalism of Petri nets with particular emphasis on the application of the methodology in the area of the performance and reliability modelling and analysis of systems The quantitative analysis of the behaviour of systems in time requires the superposition of a stochastic timing mechanism to the classical representation of PN Timed Petri nets and in particular Stochastic Petri nets SPN are the object of the second part of the notes Finally some fully developed examples enlighten peculiar aspects which differentiate PNs from other modelling techniques usual in reliability analysis In few words the goal of these notes is to show that the proposed methodology based on the PN formalism can be conveniently used as a user friendly language to represent and evaluate complex stochastic systems 1 Introduction Petri Nets PN are a graphical tool for the formal description of the flow of activities in complex systems With respect to other more popular techniques of graphical system representation like block diagrams or logical trees PN are particularly suited to represent in a natural way logical interactions among parts or activities in a system Typical situations that can be modelled by PN are synchronization sequentiality concurrency and conflict The theory of PN originated from the doctoral thesis of C A Petri in 1962 39 Since then the formal language of PN has been developed and used in many theoretical as well as applicative areas Introductory survey papers can be found in 37 3 Several textbooks on the subject are also available 38 where an extended annotated bibliography is contained 42 13 44 An yearly Workshop on Application and Theory of Petri Nets is held in Europe the IX edition of the workshop took place in Venice in June 1988 The classical PNs do not convey any notion of time in order to use the PN formalism for the quantitative analysis of the performance and reliability of system versus time a class of Timed PN TPN has been introduced The time variables associated to the PN can be either deterministic variables leading to the class of models called deterministic PN or random variables leading to the class of models called Stochastic PN SPN The bibliography on TPN is not as wide as the one on classical PN however an extended 1 collection of papers and applications can be found in the proceedings of two international workshops specifically devoted to the use of TPN in performance and reliability evaluation 1 2 The first part sections 3 4 5 6 and 7 of these lecture notes is aimed at introducing the classical theory of PN while the second part sections 8 9 10 and 11 discusses the stochastic timing of a PN with application in the field of reliability modelling and evaluation In particular Section 2 contains the list of symbols Section 3 defines the primitive elements of the PN and the execution rules by means of which the dynamic properties of the system are described Section 4 illustrates typical examples of logical interactions among activities modelled by PN while Section 5 introduces characteristic properties of PNs Section 6 shows how a PN can be analyzed through the generation of the reachability tree or by means of matrix techniques Finally some possible extensions of the modelling capabilities of classical PNs are considered in Section 7 The second part of the lecture notes is devoted to illustrate how PNs can be conveniently used as a modelling language for the quantitative analysis of the performance and reliability of systems The use of PN for this purpose requires that the duration of the activities representing the system operations can be specified and measured therefore the first step toward the definition of a suitable modelling framework is the insertion of the notion of time in classical PNs This topic is addressed in Section 8 Section 9 examines the class of Stochastic PN SPN in which the durations of the activities are exponentially distributed random variables With this assumption the dynamic behaviour of the PN can be mapped into a continuous time homogeneous Markov chain In this way we cast a natural bridge between SPN and Markov models in reliability analysis With reference to the above models we discuss the following topics the generation of the Markov chain associated to the PN the assignment of marking dependent transition rates and the partition of PN transitions into immediate and timed transitions Section 10 shows how SPN models can be