A.1.6 派翠網絡分析

hlperng

A.1.6 Petri net analysis

A.1.6.1 Description and purpose

Petri nets are a graphical tool for the representation and analysis of complex logical interactions among components or events in a system.  Typical complex interactions that are naturally included in the Petri net language are concurrency, conflict, synchronization, mutual exclusion and resource limitation.  

The static structure of the modelled system is representated by a Petri net graph.  The Petri net graph is composed of three primitive elements:
- places (usually drawn as circles) that represent the conditions in which the system can be found;
- transitions (usually drawn as bars) that represent the events that may change a condition into another one;
- arcs (drawn as arrows) that connect places to transitions and transition to places and represent the logical admissible connections between conditions and events.  

A condition is valid in a given situation if the corresponding place is marked, i.e., contains at least one token • (drawn as a black dot).  The dynamics of the system are represented by means of the movement of the tokens in the graph.  A transition is enabled if its input places contain at least one token.  An enabled transition may fire, and the transition firing removes one token from each input place and puts one token into each output place.  The distribution of the tokens into the places is called the marking.  Starting from an initial marking, the application of the eanbling and firing rules produces all the reachable markings called the reachability set of the Petri nets.  The reachability set provides all the states that the system can reach from an initial state.  
Standard Petri nets do not carry the notion of time.  However, many extensions have appeared in which a timing is superimposed onto the Petri net.  If a (constant) firing rate is assigned to each transition, the dynamics of the Petri nets can be analyzed by means of continuous Markov time chain whose state space is isomorphic with the reachability set of the corresponding Petri net.  

The Petri net can be utilized as a high level language to generate Markov models, and several tools in performance dependability analysis are based on this methodology.  

Petri nets provide also a natural environment for simulation.   

A.1.6.2 Application
The use of Petri nets is recommended when complex logical interactions need to be taken into account (concurrently, conflict, synchronization, mutual exclusion, resource limitation).  Moreover, Petri nets are usally an easier and more natural language to describe a Markov model.  

A.1.6.3 Key elements
The key elements of the Petri net analysis is as description of the system structure and its dynamic behaviour in terms of primitive elements (places, transitions, arcs, and tokens) of the Petri net language; this step requires the use of ad hoc software tools:
a) structural qualitative analysis;
b) quantitative anlaysis: if constant firing rates are assigned to the Petri net transitions the qualitative analysis can be performed via the numerical solution of the corresponding Markov model. otherwise simulation is th only viable technique.  

A.1.6.4 Benefits
Petri nets are suitable for representing complex interactions among hardware or software modules that are not easily modelled by other techniques.  

Petri nets are a viable vehicle to generate Markov models.  In general, the description of the system by means of a Petri net requires for fewer elements than the corresponding Markov representation.  

The Markov model is generated automatically from the Petri net representtion and the complexity of the analytical solution procedure is hidden to the modeller who interacts only at the Petri net level.  

In addition, the Petri nets allow a qualitative structural analysis based only on the property of the graph.  This structural analysis is, in general, less costly than the generation of the Markov model, and provides information useful to validate the consistency of the model.  

A.1.6.5 Limitations
Since the quantitative analysis is based on the generation and solution of the corresponding Markov model, most of the limitations are shared with the Markov analysis.  

A.1.6.6 Example
A fault-tolerant multiprocessor computer system, whose block diagram is depicted in Figure A.8, contains two independent sub-system S₁ and S₂ with a shared common memory M₃.
Each sub-system S_i (i =1 ; 2) is composed of one processor P[sub]i[/sup], one local memory M_i and tow replicated disk units D_i1 and D_i2.   A single bus N connects the two sub-systems and the shared common memory.  

The GSPN (generalized stochastic Petri net) reprentation of the system of Figure A.8 is depicted in Figure A.9.  

Places whose names have the suffix .dn model components in the non-operational condition.  

A token in place S.dn models the overall system failure.

Transitions whose names have the suffix .f model the failulre of a component.  

The initial marking of the net represents the multiprocessor having all component operational.  

Bibliography

• Schneeweiss, W., Petri Nets for Reliability Modelling, LiLoLe, Hagen, 1999.
• S.K. Yang and T.S. Liu, Failure Analysis for an Airbag Inflator by Petri Nets, Quality and Reliability Engineering International, Vol. 13, 139 - 151 (1997).
• S.K. Yang and T.S. Liu, A Petri Net Approach to Early Failure Detection and Isolation for Preventive Maintenance, Quality and Reliability International, Vol. 14, 319 - 330 (1998).