Time extensions of Petri nets for modelling and verification of hard real-time systems

Abstract

The main aim of the paper is a presentation of time extensions of Petri nets appropriate for modelling and analysis of hard real-time systems. It is assumed, that the extensions must provide a model of time flow, an ability to force a transition to fire within a stated timing constraint (the so-called the strong firing rule), and timing constraints represented by intervaIs. The presented survey includes extensions of classical Place/Transition Petri nets, as welI as the ones applied to high-level Petri nets. An expressiveness of each time extension is illustrated using simple hard real-time system. The paper includes also a brief description of analysis and verification methods related to the extensions, and a survey of software tooIs supporting modelling and analysis of the considered Petri nets. Głównym celem pracy jest prezentacja rozszerzeń czasowych sieci Petriego pod kątem przydatności do modelowania i analizy systemów czasu rzeczywistego o twardych wymaganiach losowych. Zakłada się, że rozważane rozszerzenia winny spełniać następujące warunki: modelowania upływu czasu, forsowania odpalenia przejścia w określonych warunkach czasowych (tzw. silna reguła odpalania), przedziałowej reprezentacji ograniczeń czasowych. Przegląd dotyczy zarówno klasycznych sieci miejsc i przejść, jak również sieci Petriego wyższego poziomu. Siła ekspresji poszczególnych rozszerzeń jest ilustrowana na wspólnym przykładzie systemu o twardych wymaganiach czasowych. Artykuł zawiera również krótki opis metod analizy i weryfikacji ograniczeń czasowych oraz przegląd systemów wspomagających modelowanie i analizę rozważanych sieci Petriego.