Petri-Netz

Als Petri-Netze werden Modelle diskreter, vorwiegend verteilter Systeme bezeichnet, die alle einigen wenigen, einfachen Prinzipien genügen. Diese Prinzipien hat der Informatiker Carl Adam Petri in den 1960er Jahren entwickelt.

Heutzutage werden Petri-Netze nicht nur in der Informatik zur Modellierung verwendet, sondern beispielsweise auch in der theoretischen Biologie, in der Geschäftsprozesswelt, im Maschinenbau, der Logistik und vielen anderen Gebieten. Zahlreiche Modellierungstechniken wie z.B. Aktivitätsdiagramme der UML 2 haben Prinzipien der Petri-Netze übernommen.

Modellieren mit Petri-Netzen

Für Petri-Netze sind ganz unterschiedliche Varianten und Ausprägungen vorgeschlagen worden. In den 1960er und 1970er Jahren wurden zunächst elementare Varianten untersucht; heutzutage werden oft „high-level“-Formen verwendet. Sie sind formal aufwendiger, beschreiben aber das modellierte System intuitiv genauer und unmittelbarer.

Einführendes Beispiel

Abb. 1: abstraktes Modell der Aktion eines Keksautomaten

Als einführendes Beispiel eines High-level-Netzes zeigt Abb. 1 ein von Einzelheiten weitestgehend abstrahierendes Modell eines Keksautomaten: Im Anfangszustand befindet sich eine Münze im Eingabeschlitz des Automaten. Damit kann der Automat einen Schritt durchführen: Er kassiert die Münze und legt eine Keksschachtel in das Ausgabefach. So entsteht der Endzustand.

Abb. 2: Modell des Inneren des Keksautomaten

Abbildung 2 verfeinert und erweitert das Modell in seinem Anfangszustand, indem nun das Verhalten des Inneren des Automaten sichtbar wird, zusammen mit der möglichen Rückgabe der eingeworfenen Münze.

Komponenten von Petrinetzen

Der genaue Sinn der Abbildungen 1 und 2 folgt aus den universellen Modellierungsprinzipien von Petrinetzen: In einem (gegebenen oder geplanten diskreten) System identifiziert man eine Reihe von Komponenten, die im Petrinetz-Modell explizit dargestellt werden. Dazu gehören:

• Gegenstände oder Datenelemente, die im System vorkommen, d.h. erzeugt, transformiert und verbraucht werden (im Beispiel: Münzen, Keksschachteln und Signale). Im Modell werden sie als Marken bezeichnet und graphisch möglichst „intuitiv“ dargestellt.
• Speicherkomponenten, die Gegenstände oder Datenelemente enthalten können (im Beispiel: Eingabeschlitz, Entnahmefach, Kasse, Signalplatz, Keksspeicher, Rückgabe). Im Modell werden sie als Plätze bezeichnet und graphisch als Kreise oder Ellipsen dargestellt;
• Zustände, also wechselnde Verteilungen von Gegenständen oder Datenelementen in Speicherkomponenten. (Abb. 2 beschreibt einen Zustand mit einer Münze im Eingabeschlitz und 3 Keksschachteln im Keksspeicher. Alle anderen Speicherkomponenten sind leer). Im Modell bildet eine Verteilung von Marken auf die Plätze eine Markierung. Graphische Darstellungen (wie die in Abb. 1 und Abb. 2) zeigen üblicherweise die Anfangsmarkierung, die den Anfangszustand des Systems beschreibt.
• Aktivitäten, die Speicherinhalte verändern können (in Abb. 1: t, in Abb. 2: a, b, c). Im Modell werden sie als Transitionen bezeichnet und graphisch als Quadrat oder Rechteck dargestellt.
• Die Beschreibung der Übergänge von Zuständen in neue Zustände: (im Beispiel: der Übergang vom Anfangs- zum Endzustand in Abb. 1 und vom Anfangs- zu einem Zwischenzustand in den Abbildungen Abb. 2 und Abb. 3). Im Modell kann man solche Schritte intuitiv als "Fluss von Marken durch die Pfeile" auffassen.

Schritte

Abb. 3: nach Eintritt von a

Von einer gegebenen Markierung M eines Petrinetz-Modells aus ist eine neue Markierung M' erreichbar, indem eine Transition t eintritt. Dazu muss t in M aktiviert sein. t ist in M aktiviert, wenn jeder bei t endende Pfeil an einem Platz p beginnt, der eine Marke enthält, die am Pfeil selbst notiert ist. In Abb. 1 ist t also aktiviert; in Abb. 2 sind a und c aktiviert, nicht aber b. Wenn eine aktivierte Transition t eintritt, verschwinden die oben beschriebenen Marken von ihren Plätzen, und für jeden bei t beginnenden Pfeil f entsteht gemäß seiner Anschrift eine Marke auf dem Platz, wo f endet.

Auf diese Weise entsteht in Abb. 1 aus der Anfangsmarkierung durch Eintritt von t die Endmarkierung. Aus Abb. 2 entsteht durch Eintritt von a die in Abb. 3 gezeigte Markierung.

Die "abstrakte" Marke (schwarzer Punkt) auf dem Signal-Platz von Abb. 3 aktiviert nun zusammen mit einer Keksschachtel im Speicher die Transition b. Indem b eintritt, erscheint schließlich eine Keksschachtel im Entnahmefach. In Abb. 2 ist auch die Transition c aktiviert. Tritt c (statt a) ein, entsteht eine Markierung mit einer Münze in Rückgabe.

Mit der obigen Regel zum Eintritt von Transitionen sieht man unmittelbar, dass 2 oder 3 Münzen im Einwurfschlitz zu entsprechend vielen Schachteln im Entnahmefach führen. Mit einer zweiten Münze im Einwurfschlitz kann die Transition a unmittelbar nach ihrem ersten Eintritt wiederum eintreten, unabhängig vom (ersten) Eintritt von b.

Das Verhalten verteilter Systeme

Das obige Beispiel zeigt vielfältige Bezüge zwischen den Aktivitäten eines verteilten Systems. Dementsprechend kann der Eintritt zweier Transitionen in unterschiedlicher Weise zusammenhängen. In Abb. 2 beispielsweise:

• nichtdeterministisch: a und c treten alternativ zueinander ein. Die Münze im Einwurfschlitz aktiviert die beiden Transitionen a und c. Indem eine von beiden eintritt, ist die andere nicht mehr aktiviert. Welche der beiden Transitionen eintritt, wird nicht modelliert.
• geordnet: a tritt vor b ein: Um einzutreten, benötigt b eine Marke, die a vorher erzeugt hat.
• nebenläufig: Nachdem - wie in Abb. 3 - a eingetreten ist, kann mit einer zweiten Münze im Einwurfschlitz (in Abb. 2 nicht dargestellt) a ein zweites (oder c ein erstes) Mal eintreten, nebenläufig zum (d.h. unabhängig vom) Einritt von b.

Elementare Netze

Abb. 4: elementare Fassung des Keksautomaten

Abbildung 4 zeigt ein Petrinetzmodell des Keksautomaten, in dem die Marken für Münzen, Signale und Keksschachteln nicht unterschieden werden: Alle werden gleichermaßen als "schwarze" Marken dargestellt. Dabei tragen Pfeile keine Inschrift (nach der Systematik der Abbildungen 1 bis 3 müsste jeder Pfeil mit "$\bullet$" beschriftet sein). In dieser Form sind Petri-Netze in den 1960er Jahren entstanden und häufig als Platz-/Transitionsnetze bezeichnet worden ^[1][2]. Die Regeln zum Eintritt einer Transition t sind in diesem Fall besonders einfach: t ist aktiviert, wenn jeder bei t endende Pfeil bei einem Platz beginnt, der mindestens eine Marke enthält. Diese Marken verschwinden beim Eintritt von t und es entsteht eine neue Marke auf jedem Platz, an dem ein bei t beginnender Pfeil endet.

Abb. 5: wechselseitiger Ausschluss

Solche einfachen Marken sind intuitiv angemessen, wenn (verteilter) Kontrollfluss modelliert wird, wie beispielsweise im Schema des wechselseitigen Ausschlusses in Abb. 5: Jeder der beiden Prozesse l und r ("links" und "rechts") durchläuft zyklisch die drei Zustände lokal, wartend, kritisch. Der Schlüssel sorgt dafür, dass niemals beide Prozesse zugleich kritisch sind. In diesem Beispiel trägt jeder Platz immer entweder keine oder eine Marke. Man kann jeden Platz daher als eine Bedingung auffassen, die gelegentlich erfüllt und gelegentlich unerfüllt ist. Solche Netze werden häufig als Bedingungs-/Ereignisnetze bezeichnet.

Analyse von Petrinetzen

Eigenschaften von Petrinetzmodellen

Wichtige Eigenschaften eines Systems sollten sich in seinem Modell widerspiegeln. Ein Petrinetz muss daher nicht nur Verhalten, sondern auch Eigenschaften eines Systems darstellen. Beispielsweise hat in den Netzen der Abbildungen 2, 3 und 4 jede erreichbare Markierung M die Eigenschaft

$M(\mathsf{Kasse})+ M(\mathsf{Speicher})= 3+M(\mathsf{Signal}).$

Dabei bezeichnet M(p) für einen Platz p die Anzahl der Marken auf p in der Markierung M. Für jede Münze in der Kasse ist also eine Keksschachtel abgegeben worden oder (mit einer Marke auf Signal) wird noch abgegeben. Entsprechend gilt für Abb. 5

$M(\mathsf{kritisch}_l)+ M(\mathsf{kritisch}_r)\leq 1.$

Es ist also immer höchstens ein Prozess in seinem kritischen Zustand. Eine naheliegende, aber schon für elementare Systemnetze überraschend komplizierte Fragestellung ist die Erreichbarkeit einer beliebig gewählten Markierung M:

$\text{Ist}\ M\ \text{von der Anfangsmarkierung aus erreichbar?}$

Es hat eine Reihe von Jahren gedauert, bis dafür ein Algorithmus gefunden wurde [Mayr80]. Weitere wichtige Eigenschaften eines elementaren Systemnetzes N sind:

• N terminiert: Jede in der Anfangsmarkierung beginnende Sequenz von Schritten von N erreicht irgendwann einen Deadlock, d.h. eine Markierung, die keine Transition aktiviert (die Keksautomaten terminieren).
• N ist deadlockfrei: In N sind keine Deadlocks erreichbar (der wechselseitige Ausschluss ist deadlockfrei).
• N ist lebendig: Von jeder erreichbaren Markierung aus ist für jede Transition t eine Markierung erreichbar, die t aktiviert (der wechselseitige Ausschluss ist lebendig).
• N ist schwach lebendig: Zu jeder Transition t von N gibt es eine erreichbare Markierung, die t aktiviert (Keksautomat und wechselseitiger Ausschluss sind beide schwach lebendig).
• N ist k-beschränkt für eine Zahl k: Jeder Platz enthält unter jeder erreichbaren Markierung höchstens k Marken (der Keksautomat ist 3-beschränkt, der wechselseitige Ausschluss ist 1-beschränkt).
• N ist reversibel: Die Anfangsmarkierung ist von jeder erreichbaren Markierung aus erreichbar (der wechselseitige Ausschluss ist reversibel).
• N hat einen Homestate: Ein Homestate von N ist eine Markierung, die von jeder erreichbaren Markierung aus auf jeden Fall erreicht wird. Weder der Keksautomat noch der wechselseitige Ausschluss hat einen Homestate.

Nachweis von Eigenschaften

Bei allen beschriebenen Eigenschaften stellt sich die Frage, wie man sie für ein gegebenes anfangsmarkiertes Netz beweist oder widerlegt. (vgl. Verifikation) Alle genannten Eigenschaften sind für elementare Netze entscheidbar, allerdings nur mit Algorithmen, deren Komplexität für die Praxis viel zu groß ist. In der Praxis werden deshalb Algorithmen für hinreichende oder notwendige Bedingungen verwendet. Diese Algorithmen beruhen auf Platzinvarianten, anfangsmarkierten Fallen, der Markierungsgleichung und dem Überdeckungsgraphen eines Systemnetzes.

Softwarewerkzeuge

Seit den 1980er Jahren entstand eine Vielzahl unterschiedlicher Softwarewerkzeuge zur Erstellung und zur Analyse von Petrinetzen. Als universelles Werkzeug für High-level-Netze hat sich insbesondere das Werkzeug CPN durchgesetzt ^[3]. Daneben gibt es eine Vielzahl spezifischer Werkzeuge für spezielle Netzvarianten, beispielsweise zur Analyse zeitbehafteter und stochastischer Netze ^[4] oder für spezielle Anwendungsbereiche, beispielsweise service-orientierter Architekturen.^[5]

Verallgemeinerungen, Spezialfälle, Varianten

Die allgemeinste Form von High-level-Netzen

Abb. 6: Variante des Keksautomaten

Das Modell des Keksautomaten in (Abb. 1 - Abb. 3) ist ein Beispiel eines high-level Netzes. Die volle Ausdrucksstärke solcher Netze erreicht man mit Hilfe von Variablen und Funktionen in den Inschriften der Pfeile. Als Beispiel modelliert Abb. 6 eine Variante des Keksautomaten mit 4 Münzen im Eingabeschlitz. Für die 4. Münze gibt es keine Schachtel im Speicher; die Münze soll also auf jeden Fall zurückgegeben werden. Dazu enthält Abb. 6 einen Zähler, deren Marke die Anzahl verfügbarer Schachteln angibt. Die Transition a wird aktiviert, indem die Variable x den aktuellen Wert dieser Marke annimmt. Zusätzlich ist a mit der Bedingung x > 0 beschriftet, die zum Eintritt von a erfüllt sein muss. Damit reduziert jeder Eintritt von a den Zählerwert um 1 und a ist beim Wert 0 nicht mehr aktiviert. Jede weitere Münze landet dann also über c in der Rückgabe.

Spezialfall free-choice

Abb. 7: Die free-choice Eigenschaft

Im Modell des Keksautomaten der Abbildungen 2, 3 und 4 wählt die Marke im Einwurfschlitz nichtdeterministisch eine der Transitionen a oder c. Diese Wahl hängt von keinen weiteren Vorbedingungen ab; sie ist frei.

Im System des wechselseitigen Ausschlusses aus Abb. 5 hat der Schlüssel die Wahl zwischen den Transitionen b und e. Diese Wahl hängt aber zusätzlich davon ab, dass auch $\mathsf{wartend}_l$ und $\mathsf{wartend}_r$ markiert sind. Sie ist nicht frei.

Ein Netz N ist ein Free-choice-Netz, wenn schon seiner Struktur nach alle Wahlmöglichkeiten frei sind, falls also für zwei Pfeile, die am selben Platz p beginnen, gilt: Sie enden an Transitionen, an denen keine weiteren Pfeile enden ^[6]. Abbildung 7 skizziert diese Bedingung. Offensichtlich sind alle Modelle des Keksautomaten Free-choice-Netze, nicht aber der wechselseitige Ausschluss in Abb. 5.

Ob eine der in oben beschriebenen Eigenschaften gilt oder nicht gilt, ist für Free-choice-Netze mit effizienten Algorithmen entscheidbar ^[6].

Verallgemeinerungen elementarer Netze

Abb. 8: Kantengewichte und Platzkapazitäten: t ist nicht aktiviert

Schon in den 1970er Jahren wurden elementare Netze um zahlreiche weitere Ausdrucksmittel ergänzt. Drei davon seien hier geschildert:

• Pfeile gewichten: Jedem Pfeil ist als "Gewicht" eine natürliche Zahl n zugeordnet. Bei Eintritt der mit dem Pfeil verbundenen Transition fließen dann n Marken (statt nur einer Marke) durch den Pfeil.
• Die Kapazität der Plätze beschränken: Jedem Platz p wird als "Schranke" eine natürliche Zahl n zugeordnet. Wenn beim Eintritt einer Transition t mehr als n Marken auf p entstehen würden, ist t nicht aktiviert. Abbildung 8 zeigt ein Beispiel.
• Einen Platz auf Abwesenheit von Marken testen: Ein Platz p ist mit einer Transition t durch eine neuartige "Inhibitor"-Kante verbunden. t ist nicht aktiviert, wenn p eine oder mehrere Marken trägt. Abbildung 9 skizziert diese Konstruktion.

Abb. 9: Wirkung einer Inhibitorkante

Gewichtete Pfeile und kapazitätsbeschränkte Plätze steigern nicht wirklich die Ausdruckskraft: Man kann sie mit intuitiv plausiblen Mitteln simulieren. Hingegen kann man mit Inhibitorkanten echt mehr ausdrücken und konsequenterweise weniger entscheiden. Insbesondere ist die Erreichbarkeit für Netze mit Inhibitorkanten nicht entscheidbar ^[7]. Weitere Ausdrucksmittel sind gelegentlich erforderlich, um wirklich genau zu modellieren, wie sich ein verteiltes System verhält. Beispielsweise wollen wir im System des wechselseitigen Ausschlusses in Abb. 5 darstellen, dass jeder der beiden Prozesse für immer in seinem lokalen Zustand, aber nicht für immer in seinem kritischen Zustand verharren darf. Dazu unterscheiden wir die kalte Transition a ("tritt nicht unbedingt ein, wenn sie aktiviert ist") von der heißen Transition b ("tritt ein, wenn sie aktiviert ist"). Mit den Transitionen b und e ist es noch komplizierter: Wenn wir jedem wartenden Prozess garantieren möchten, dass er irgendwann einmal kritisch wird, müssen wir Fairness für b und e verlangen. Mit dem Unterschied zwischen heißen und kalten Transitionen und mit der Forderung von Fairness kann man die Menge der "gemeinten" Abläufe eines Petrinetzes sehr viel genauer charakterisieren. ^[2]

Zeitbehaftete und stochastische Netze

Wenn Transitionen geordnet eintreten, in Abb. 2 beispielsweise erst a dann b, soll diese Ordnung kausal und nicht zeitlich interpretiert werden. Dann ist es konsequent, in Abb. 2 mit einer zweiten Münze im Eingabeschlitz das erste Eintreten von b und das zweite Eintreten von a als unabhängig voneinander aufzufassen und nicht als gleichzeitig.

Dennoch gibt es Systeme mit Aktionen, deren Dauer modelliert werden soll, oder die in irgendeiner Weise an Uhren orientiert sind. Zur Modellierung solcher Systeme wurden zahlreiche Varianten zeitbehafteter Petrinetze vorgeschlagen. Dabei werden Plätze, Transitionen, Marken und Pfeile mit Zeitstempeln und Zeitintervallen versehen. Diese Zusätze regeln die Aktivierung von Transitionen und erzeugen neue Zeitstempel nach dem Eintritt einer Transition.

Wenn zwei Transitionen t und u um dieselbe Marke einer Markierung M konkurrieren (beispielsweise konkurrieren in Abb. 5 b und e um die Marke auf Schlüssel) und wenn M immer wieder erreicht wird, will man gelegentlich modellieren, dass t mit der Wahrscheinlichkeit p und u mit der Wahrscheinlichkeit 1 − p eintritt. Dafür eignet sich die breit ausgebaute Theorie der stochastischen Netze ^[8].

Die historische Entwicklung

Der Anfang

Die Forschung zu Petrinetzen begann mit der Dissertation von Carl Adam Petri im Jahr 1962 ^[9]. Diese Arbeit wurde zunächst kaum beachtet; die Theoretische Informatik hat damals andere Fragestellungen verfolgt und für die Praxis kamen Petris Vorschläge zu früh. Ein erster Durchbruch im Bereich der Theorie kam Ende der 1960er Jahre mit der Verwendung von Petris Ideen im Projekt MAC des MIT. In den 1970er Jahren wurden Platz-/Transitionsnetze weltweit studiert, allerdings recht oft aus dem verengten Blickwinkel formaler Sprachen ^[10].

Die Entwicklung seit den 1980er Jahren

Seit Beginn der 1980er Jahre wurden ganz unterschiedliche Varianten von High-level-Netzen vorgeschlagen, die Gegenstände, Datenelemente oder Symbole als Marken verwenden. Diese Formalismen erhöhen die Ausdruckskraft von Platz-/Transitionsnetzen beträchtlich. Zugleich konnten viele Analysetechniken von Platz-/Transitionsnetzen auf diese Formalismen verallgemeinert werden ^[2].

Mit zunehmenden Interesse an verteilten Systemen und verteilten Algorithmen wurden und werden seit den 1980er Jahren zahlreiche neue Modellierungstechniken vorgeschlagen. Petrinetze haben sich gegenüber diesen Neuentwicklungen behauptet; vielfach werden sie als Maßstab für die Qualität und die Ausdrucksmächtigkeit für Modelle verteilter Systeme verwendet. Einen Überblick über zahlreiche Anwendungsbereiche von Petrinetzen gibt ^[11].

Aktuelle Themen

Mit Petrinetzen werden heutzutage Systeme modelliert, deren Verhalten aus diskreten, lokal begrenzten Schritten besteht. Das sind oft, aber keineswegs ausschließlich Systeme, die Rechner integrieren oder die mit Rechnern simuliert werden. Zu den derzeit besonders viel versprechenden Anwendungen von Petrinetzen gehört die Modellierung von Prozessen der Systembiologie ^[12], der Geschäftsprozesswelt ^[13] und der Service-orientierten Architekturen ^[5].

Zum Weiterlesen

In den fünfzig Jahren seit den Anfängen der Petrinetze hat sich eine Vielfalt an Varianten und Anwendungsbereichen herausgebildet, deren großer Umfang eine vollständige, systematische Darstellung ausschließt. Wer die vielfältigen Aspekte von Petrinetzen kennenlernen möchte, findet im Petrinetz-Portal der Universität Hamburg [PetriWorld] einen geeigneten Anfang. Die im Abstand mehrerer Jahre veranstaltete Sommerschulreihe Advanced Course on Petrinets (zuletzt der 5. Kurs in Rostock, 2010) und die jährliche Conference on Applications and Theory of Petri Nets geben aktuelle Überblicke und Darstellungen. Unter den zahlreichen Lehrbüchern ist ^[2] das aktuellste.

Anwendungsgebiete

• Asynchroner Schaltkreis
• Nebenläufige Programmierung
• Paralleler Algorithmus
• Softwareentwurf
• Verwaltung von Arbeitsabläufen
• Verifikation von nebenläufigen Prozessen
• Automatisierung (Steuerungstechnik)
• Stoffstromnetz
• Geschäftsprozessmodellierung

Siehe auch

• Aktivitätsdiagramm der UML
• Erreichbarkeitsgraph
• Graphentheorie

Weblinks

• Fachgruppe "Petrinetze und verwandte Systemmodelle" der Gesellschaft für Informatik
• Übersicht über Softwaretools zur Erstellung von Petri-Netzen
• Petri Nets World (englisch)
• Informelle Einführung (PDF-Datei; 768 kB)

Literaturverweise

1. ↑ B. Baumgarten: Petri-Netze - Grundlagen und Anwendungen. 1996, Spektrum-Akademischer Verlag.
2. ↑ ^{a b c d} W. Reisig: Petrinetze - Modellierung, Analyse, Fallstudien. 2010, Vieweg-Teubner Verlag.
3. ↑ K. Jensen, L.M. Kristensen: Coloured Petri Nets. 2009, Springer-Verlag.
4. ↑ The Petri Net World
5. ↑ ^{a b} www.service-technology.org
6. ↑ ^{a b} J. Desel, J. Esparza: Free Choice Petri Nets. In Theoretical Computer Science. Vol. 40, 1995.
7. ↑ C. Reutenauer: The mathematics of Petri nets. 1990, Prentice Hall.
8. ↑ M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, G. Frankeschinis: Modeling with generalized stochastic Petri nets. 1995, Wiley.
9. ↑ C.A. Petri: Kommunikation mit Automaten. 1962, Institut für instrumentelle Mathematik der Universität Bonn.
10. ↑ L. Peterson: Petri Net Theory and the Modeling of Systems. 1981, Prentice Hall.
11. ↑ C. Girault, R. Valk: Petri Nets for Systems Engineering. 2003, Springer-Verlag.
12. ↑ I. Koch, W. Reisig, F. Schreiber (eds): Modeling in Systems Biology. 2011, Springer-Verlag.
13. ↑ W.M.P. van der Aalst and C. Stahl: Modeling Business Processes, A Petri Net-Oriented Approach. 2011, The MIT Press