• Petri-Netze sind eine verbreitete Technik zur Beschreibung von dynamischem Verhalten

• und bilden beispielsweise eine Basis zur Definition der Semantik von Sprachen zur Geschäftsprozessmodellierung

• Ein Graph G ist eine Struktur, die aus Elementen N, genannt Knoten (engl. Node oder Vertex), und deren Verbindungen , genannt Kanten (engl. Edge), besteht.

• Beispiele für derartige Graphen sind endliche Automaten,

  • die aus Zuständen (Knoten) und Zustandsübergängen (Kanten) bestehen, oder Syntaxbäume.

Bei Petri-Netzen handelt es sich um eine spezielle Form von Graphen, nämlich bipartite Graphen, die zwei verschiedene Typen von Knoten nutzen.

• Bei Petri-Netzen handelt es sich um eine spezielle Form von Graphen, nämlich bipartite Graphen, die zwei verschiedene Typen von Knoten nutzen.

Beispiele für Sachverhalte, die sich für eine Beschreibung mit einem bipartiten Graphen eignen, sind

• Aufgaben und Aufgabenverantwortliche,

• Ehepaare (ohne gleichgeschlechtliche Partnerschaft)

• und Geschäftsprozessmodelle, in denen abwechselnd Aktivitäten und Zustände beschrieben werden.

• Ein Platz beschreibt einen Zustand einer Komponente des betrachteten Systems,

• und eine Transition beschreibt eine Aktivität, also den Übergang von einem Zustand in einen anderen.

  
  

• Daher sind Plätze nur mit Transitionen verbunden und umgekehrt, also genau die von einem bipartiten Graphen erwartete Eigenschaft.

• Plätze P, dargestellt als Kreise,

• Transitionen T , dargestellt als Rechtecke (oder Balken),

• Fluss F , dargestellt als Pfeile von Transitionen zu Plätzen oder umgekehrt.

Die Plätze sind markiert als p1, p2 etc., die Transitionen als t1, t2 etc.

• Eine Markierung wird auch als Belegung, Zustand oder Konfiguration des Petri-Netzes bezeichnet.

• Petri-Netze beschreiben Prozesse mithilfe von Plätzen (Kreisen), Transitionen (Rechtecken) und Marken (Token), die sich durch das Netz bewegen.

• Diese Bewegung wird als Tokenspiel bezeichnet und folgt bestimmten Regeln.

• Vorbereich (∙x): Alle Knoten, die eine Verbindung zu einem bestimmten Knoten x haben.

  • Bei Transitionen: Plätze, die Ressourcen bereitstellen (Eingangsplätze).

• Nachbereich (x∙): Alle Knoten, die eine Verbindung von x haben.

  • Bei Transitionen: Plätze, in denen Ergebnisse abgelegt werden (Ausgangsplätze).

Regeln des Tokenspiels

1. Startzustand: Jeder Platz enthält eine bestimmte Anzahl von Marken (Token), die durch die Anfangsmarkierung vorgegeben sind.

2. Feuern einer Transition:

   • Eine Transition ist aktiviert, wenn alle ihre Eingangsplätze mindestens eine Marke haben.

   • Eine aktivierte Transition kann feuern, muss aber nicht.

   • Wenn sie feuert:

     • Entfernt sie je eine Marke aus allen Eingangsplätzen.

     • Fügt sie je eine Marke zu allen Ausgangsplätzen hinzu.

1. AND-Split:

   • Eine Transition führt zu mehreren Plätzen.

   • Wenn die Transition feuert, werden in allen folgenden Plätzen Marken abgelegt.

2. XOR-Split:

   • Ein Platz führt zu mehreren Transitionen.

   • Wenn eine Marke im Platz liegt, kann eine der Transitionen feuern – aber nicht beide gleichzeitig.

3. Joins:

   • Zusammenführungen von Verzweigungen. Sie sind keine Pflicht, aber häufig sinnvoll, um Prozesse klar abzubilden.

1. Bedingungs-Ereignis-Netze

2. Workflow-Netze

3. Platz-Transitions-Netze

Bedingungs-Ereignis-Netze

• Eigenschaft: Jeder Platz darf höchstens eine Marke enthalten.

  
  

1. Bedeutung:

   • Eine Marke steht für eine Bedingung, die erfüllt ist (Marke vorhanden) oder nicht (Marke fehlt).

2. Anwendung: Diese Netze eignen sich gut, um einfache Ja/Nein-Bedingungen abzubilden.

Workflow-Netze

• Eigenschaft:

  • Es gibt genau einen Startplatz (i) ohne Eingangsverbindungen.

  • Es gibt genau einen Endplatz (o) ohne Ausgangsverbindungen.

  • Jeder Platz und jede Transition liegt auf einem Pfad zwischen dem Start- und dem Endplatz.

• Bedeutung:

  • Ideal für die Modellierung von Geschäftsprozessen oder Workflows.

• Anwendung: Werden oft in Workflow-Systemen genutzt, um Prozesse zu automatisieren (ähnlich wie BPMN).

Platz-Transitions-Netze

• Eigenschaft:

  • Jede Verbindung hat ein Gewicht, das angibt, wie viele Marken verbraucht oder erzeugt werden.

• Regeln:

  • Beim Feuern einer Transition wird die Anzahl der Marken entsprechend dem Gewicht angepasst.

• Anwendung: Geeignet für Szenarien mit parallelen Abläufen, wie die Bearbeitung mehrerer Aufträge gleichzeitig.

Sowohl Petri-Netze als auch endliche Automaten modellieren Zustände als Knoten in einem Graphen. In einem Petri-Netz werden allerdings die Zustandsübergänge als ein anderer Typ von Knoten modelliert, während sie in endlichen Automaten als Kanten modelliert werden.

In allen drei Fällen können die Transitionen t1 und t2 feuern. t5 kann nicht feuern, da nur p5, aber nicht p6 eine Marke enthält.

Eigenschaften von Petri-Netzen

1. Lebendigkeit (Liveness):

2. Sicherheit (Safety):

3. Deadlock-Freiheit:

4. Terminierung:

   
   

Lebendigkeit (Liveness):

• Eine Transition ist lebendig, wenn sie immer irgendwann aktiviert werden kann.

• Ein Netz ist lebendig, wenn alle Transitionen lebendig sind.

• Beispiel: Ein Netz ist nicht lebendig, wenn eine Transition nie feuern kann.

Sicherheit (Safety):

• Ein Platz ist sicher, wenn es eine Obergrenze kkk für die Anzahl der Marken gibt, die sich dort ansammeln können.

• Ein Netz ist sicher, wenn alle Plätze diese Obergrenze einhalten.

• Beispiel: Ein Netz ist nicht sicher, wenn sich an einem Platz unendlich viele Marken sammeln können.

Deadlock-Freiheit:

• Ein Netz ist deadlock-frei, wenn immer mindestens eine Transition aktiviert ist, also das System nicht „steckenbleibt“.

Terminierung:

• Ein Netz terminiert, wenn jede Abfolge von Transitionen irgendwann zu einem Zustand führt, in dem nichts mehr aktiviert werden kann (Deadlock).

1. Netz a):

   • Nicht lebendig: t3 kann nie feuern.

   • Sicher: Es gibt keine Möglichkeit, zusätzliche Marken zu erzeugen.

   • Hat einen Deadlock: Nach dem Feuern von t1 oder t2 ist nichts mehr aktiviert.

   • Terminiert: Das Netz führt immer zu einem Deadlock.

2. Netz b):

   • Lebendig: Beide Transitionen t1 und t2 können unendlich oft feuern.

   • Nicht sicher: Die Marken in Platz p3 können unbegrenzt wachsen.

   • Deadlock-frei: Es bleibt immer etwas aktiviert.

   • Nicht terminiert: Es gibt keinen endgültigen Stillstand.

3. Netz c):

   • Nicht lebendig: Manche Transitionen können nicht immer feuern.

   • Hat einen Deadlock: Nach bestimmten Abfolgen bleibt das Netz stecken.

   • Sicher: Es gibt keine Möglichkeit, zusätzliche Marken zu erzeugen.

   • Nicht terminiert: Abwechselnde Transitionen verhindern einen Stillstand.

Das Philosophenproblem

1. Problem: Fünf Philosophen teilen sich fünf Gabeln. Jeder braucht zwei Gabeln, um zu essen. Ohne Regeln kann es zu einem Deadlock kommen, wenn alle gleichzeitig eine Gabel nehmen und auf die zweite warten.

2. Lösung: Mit einem Petri-Netz kann man modellieren, dass jeder Philosoph irgendwann essen kann, ohne dass es zu einem Deadlock kommt.

Wechselseitiger Ausschluss

• Definition: Zwei Prozesse dürfen nicht gleichzeitig einen „kritischen Bereich“ betreten.

• Beispiele:

  • Bei einer Ampel dürfen nicht beide Richtungen gleichzeitig grün zeigen.

  • Auf einer eingleisigen Bahnstrecke dürfen keine Züge in beide Richtungen fahren.

    
    

Modellierung von wechselseitigem Ausschluss

Workflow-Netze terminieren gemäß Definition immer. Für die anderen Varianten ist keine allgemeingültige Aussage möglich.

Mit Petri-Netzen kann man überprüfen, ob ein System bestimmte Eigenschaften wie

• Lebendigkeit,

• Sicherheit oder

• Deadlock-Freiheit besitzt.

Zwei wichtige Ansätze:

• Erreichbarkeitsgraphen und

• Invarianten.

Ein Erreichbarkeitsgraph zeigt:

• Alle möglichen Zustände (Markierungen) eines Petri-Netzes.

• Welche Transitionen von einem Zustand aus ausführbar sind.

Beispiel: Eingleisige Eisenbahnstrecke

• Ziel: Sicherstellen, dass nie zwei Züge gleichzeitig auf derselben Strecke sind.

Der Erreichbarkeitsgraphe:

• die Modellierung einer eingleisigen Eisenbahnstrecke als Variation des wechselseitigen Ausschlusses

Probleme bei komplexeren Netzen:

• Wenn Transitionen unbegrenzt oft feuern können, wird der Erreichbarkeitsgraph unendlich groß

• Selbst bei endlichen Netzen können die Graphen schnell unübersichtlich werden.

Erreichbarkeitsproblem:

Gleichheitsproblem von Erreichbarkeitsmengen

Da die Anzahl der Plätze im Petri-Netz endlich ist, kann man alle theoretisch möglichen Belegungen aufzählen und dann mithilfe der Entscheidbarkeit des Erreichbarkeitsproblems entscheiden, ob die jeweilige Belegung erreichbar ist.

Sie sind wichtige Werkzeuge,

• um das Verhalten eines Petri-Netzes zu analysieren

• und dessen Korrektheit sicherzustellen.

In der Praxis:

• In Software helfen Invarianten sicherzustellen, dass Algorithmen keine logischen Fehler machen.

• In einem Petri-Netz können Invarianten garantieren, dass Deadlocks oder unerwünschte Zustände nicht auftreten

1. Platz-Invarianten (P-Invarianten): Betreffen die Markenanzahl an den Plätzen.

2. Transitions-Invarianten (T-Invarianten): Beschreiben, wie sich eine Sequenz von Transitionen auf das Netz auswirkt.

   • Die Wiederherstellung des gleichen Zustands nach einer bestimmten Abfolge von Transitionen.

. Beispiel: Transition t1

1. Schritt 1: Schau dir die Eingänge von t1 an t1 hat keine eingehenden Kanten. Das heißt, es entnimmt nirgends Tokens. → Überall bleibt 0.

2. Schritt 2: Schau dir die Ausgänge von t1 an t1 gibt ein Token an Platz p1 → Für p1schreiben wir eine +1.

3. Schritt 3: Fülle den Vektor

   • Für p1 +1(ein Token wird hinzugefügt).

   • Für alle anderen (p2,p3,p4,p5p): 0 (keine Änderung).

   Der Vektor ist also:

Transition t3

1. Schritt 1: Schau dir die Eingänge von t3​ an t3 nimmt Tokens von zwei Plätzen:

   • Von p1: ein Token wird entnommen → -1.

   • Von p2​: ein Token wird entnommen → -1.

2. Schritt 2: Schau dir die Ausgänge von t3 an t3 fügt ein Token zu Platz p4​ hinzu → +1.

3. Schritt 3: Fülle den Vektor

   • Für p1​: −1 (ein Token wird entnommen).

   • Für p2​: −1 (ein Token wird entnommen).

   • Für p4: +1(ein Token wird hinzugefügt).

   • Für p3 und p5: 0(keine Änderung).

   Der Vektor ist also:

Jede Spalte dieser Matrix beschreibt eine Transition.

1. Man multipliziert die 3 Spalte mit einem Spaltenvektor.

2. Dabei hat dieser so viele Zeilen wie die Matrix Spalten.

3. Dann wird die 3 Zeile auf 1 gesetz und der Rest auf 0.

4. Dann wird die Zeilenanzahl des Vektors mit der Spaltenanzahl der Matrix um diese dann zu addieren.