TIME EXTENSIONS OF PETRI NETS FOR MODELLING AND YERIFICATION OF HARD REAL-TIME SYSTEMS

Slawomir Samolej, Tomasz Szmuc

Abstract


The main aim ofthepaper is apresentation oftime extensions ofPetri nets appropriate for modelling and analysis o f hard real-time systems. It is assumed, that the extensions must provide a model o f time flow, an ability to force a transition to fire within a stated timing constraint (the so-called the strongfiring rule), and timing constraints represented by inte- rvals. The presented survey includes extensions o f classical Place/Transition Petri nets, as well as the ones applied to high-level Petri nets. An expressiveness o f each time extension is illustrated using simple hard real-time system. The paper includes also a brief description o f analysis and verification methods related to the extensions, and a survey o f software tools supporting modelling and analysis o f the considered Petri nets.


Full Text:

PDF

References


van der Aalst W.M.P.: Interwal Timed Coloured Petri Nets and their Analysis. Application and Theory of Petri Nets 1993, Proc. of the 14th International Petri Net Conference, Chicago

, Lecture Notes in Computer Science, vol. 691, Springer-Verlag 1993, 452—427

Berhtomieu B., Diaz M.: Modeling and Verification of Time Dependent Systems Using Time Petri Nets. IEEE Transactions on Software Engineering, vol. 17, No. 3, March 1991, 259-273

Bowden F.D.J.: Modelling Time in Petri Nets. Proc. of the Second Australia-Japan Workshop on Stochastic Models in Engineering, Technology and Management, Gold Coast, Australia, July 1996

Bowden F.D.J.: A BriefSurvey and Synthesis of the Roles ofTime in Petri Nets. Mathematical and Computer Modelling, 1999

Burkhard H.D.: Ordered Firing in Petri Nets. Journal of Information Proc. and Cybemetics EIK, 17, 1981, 71-86

Cerone A.: A Net-Based Approach for Specijying Real-Time Systems. Dipartamento di Infor- matica, Universita di Pisa 1993 (Ph.D., Thesis, TD-16/93)

Cerone A., Maggiolo-Shettini A.: Time-Based Expressivity of Time Petri Netsfor System Spe cification. Theoretical Computer Science, vol. 216, 1999, 1-53

Coolahan J.E. Jr., Roussopoulos N.: Timing Reąuirementsfor Time-Driven Systems Using Au- gmented Petri Nets. IEEE Transactions on Software Engineering, vol. SE-9, No. 5, September

, 603-616

Felder M., Ghezzi C., Pezze M.: Formal Specyfication and Timing Analysis o f High-Integrity Real-Time Systems. Real Time Computing, NATO ASI Series, vol. 127, 1992, 187-211

de Frutos-Escrig D., Ruiz V.V., Alonso O.M.: Decidability o f Properties o f Timed-Arc Petri Nets. Application and Theory of Petri Nets 2000,21 st International Conference, ICATPN 2000, Aarhus, Denmark, June 26-30, 2000, 187-206

Ghezzi C., Mandrioli D., Morasca S., Pezze M.: A Unified High-Level Petri Net Formalism

for Time-Critical Systems. IEEE Transactions on Software Engineering, vol. 17, No. 2, Febru- ary 1991, 160-172

HanischH.M.:AnalysisofPlace/TransitionNetswithTimedAresanditsApplicationtoBatch process Control. Application and Theory of Petri Nets 1993, Proc. of the 14th International Petri Net Conference, Chicago 1993, Lecture Notes in Computer Science, vol. 691, Springer- -Verlag 1993, 282-299

Hanisch H.M., Thieme J., Lautenbach K., Simon C.: Timestamp nets in technical applica- tions. Proc. IEEE Int. Conf. on Systems, Man, and Cybemetics (SMC'98), San Diego, CA, 11-14 October 1998, 119-124

Halang W.A., Sacha K.M.: Real-Time Systems. London, World Scientific Publishing Co. 1992

Holliday M.A., Vemon M.K.: A Generalized Timed Petri Net Modelfor Performance Analy

sis. IEEE Transactions on Software Engineering, vol. SE-13, No. 12, December 1987, 1297-1310

Jensen K.: Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. vol. 1-3. Berlin, Springer-Verlag 1995/96

Leveson N.G., Stolzy J.L.: Safety Analysis Using Petri Nets. IEEE Transactions on Software Engineering, vol. SE-13, No. 3, March 1987, 386-397

MerlinP.M.,FarberD.J.:RecoverabilityofCommunicationProtocols-ImplicationsofaThe- oretical Study. IEEE Transactions on Communications, September 1976, 1036-1043

Meta Software Corporation: Design/CPN Tutorialfor X-Windows. Meta Software 1993

Meta Software Corporation: Design/CPN Reference Manuał for X-Windows. Meta Software

Murata T.: Petri Nets: Properties, Analysis and Applications. Proc. of the IEEE, vol. 77, No.

, 1989, 541-580

Peterson J.L.: Petri Net Theory and The Modelling of Systems. Englewood Cliffs, Prentice-

-Hall, 1981

Ramamoorthy C.V., Ho G.S.: Performance Evaluation ofAsynchronous Concurrent Systems

Using Petri Nets. IEEE Transactions on Software Engineering, vol. SE-6, No. 5, September

, 440-449

Ramchandani C.: Analisys ofAsynchronous Concurrent Systems by Petri Nets. Project MAC,

MAC-TR 120, MIT 1974 (Ph.D. Thesis)

Roch S., Starkę H.P.: INA Integrated Net Analyzer, Yersion

2, Manuał. Berlin, Humboldt-

-Universitat zu Berlin, Institut fur Informatik, Lehrstuhl fur Automaten und Systemtheorie 1999 [26] Sacha K.: Projektowanie oprogramowania systemów wbudowanych. Warszawa, Politechnika

Warszawska 1996 Prace Naukowe Elektronika, z. 115,

Sifakis J.: PerformanceEvaluation ofSystems UsingNets. Net Theory and Applications, Proc.

of the Advanced Course on General Net Theory of Processes and Systems, Hamburg, October 1979, Lecture Notes in Computer Science, vol. 84, Springer 1980, 307-319

Starkę P.H.: Some Properties of Timed Nets under the Earliest Firing Rule. Lecture Notes in Computer Science, vol. 424, Advances in Petri Nets 1989, Germany, Springer-Verlag 1990, 418-432

Starkę P.H.: A Memo on Time Constraints in Petri Nets. Informatik-Bericht, Nr 46

Stórrle H.: An Ealuation ofHigh-End Toolsfor Petri-Nets. Ludwig-Maximilians-Universitat

Miinchen, Institut fur Informatik, June 1998

Szmuc T.: Zaawansowane metody tworzenia oprogramowania systemów czasu rzeczywistego.

Kraków, Cracow Centre for Advanced Training in Information Engineering, vol. 15, 1998

Walter B.: Timed Petri Netsfor Modelling and Analysis Protocols with Real-Time Characteri- stics. Proc. 3rd IFIP Workshop

on Protocol Specification, Testing, and Verification, North-

-Holland, Amsterdam 1983, 149-159

http://www.daimi.au.dk/PetriNets/classification/tools/cabemet.html

http://www.daimi.au.dk/PetriNets/classification/tools/merlot.html




DOI: https://doi.org/10.7494/csci.2002.4.1.3599

Refbacks

  • There are currently no refbacks.