TIME EXTENSIONS OF PETRI NETS FOR MODELLING AND YERIFICATION OF HARD REAL-TIME SYSTEMS
DOI:
https://doi.org/10.7494/csci.2002.4.1.3599Abstract
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.
Downloads
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
