Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Wie modelliert man Nebenläufigkeit + Synchronisation präzise? Petri-Netze (Carl Adam Petri 1962) sind DIE mathematische Notation dafür. Klausurpflicht in 6/15 Modellierungs-Modulen.
Die Idee in einem Satz
Petri-Netz: Ein gerichteter bipartiter Graph aus Stellen (Zustände) und Transitionen (Aktionen), mit Marken (Tokens) die Aktivierungs-Zustände markieren.
4 Bausteine
| Element | Symbol | Bedeutung |
|---|---|---|
| Stelle (Place) | Kreis ○ | Zustand / Ressource |
| Transition | Rechteck ▭ | Aktion / Ereignis |
| Kante (Arc) | Pfeil → | Verbindung Stelle ↔ Transition (NIEMALS Stelle-Stelle oder Transition-Transition!) |
| Marke (Token) | Punkt ● | Steht in Stelle, repräsentiert Daten/Ressource |
Wichtig: Petri-Netz ist bipartit, Kanten gehen nur zwischen unterschiedlichen Typen (Stelle ↔ Transition, nie Stelle-Stelle).
Schalten einer Transition
Eine Transition t ist aktiviert (enabled), wenn in JEDER Eingangs-Stelle (Pre-Stelle) mindestens 1 Marke liegt.
Aktivierte Transition kann schalten (fire):
- Aus JEDER Eingangs-Stelle wird 1 Marke entfernt.
- In JEDE Ausgangs-Stelle wird 1 Marke gelegt.
Beispiel: Transition mit 2 Eingangsstellen und 1 Ausgangsstelle. Wenn beide Eingangs-Stellen je 1 Marke haben → schaltbar → schalten verbraucht 2 Marken und produziert 1.
Klassische Anwendungen
Erzeuger-Verbraucher
○ Erzeuger_bereit → ▭ produzieren → ○ Produkt_fertig → ▭ in_Puffer → ○ Puffer
↓
○ Erzeuger_bereit
○ Verbraucher_bereit ─ ┐
○ Puffer ─ ┴→ ▭ konsumieren → ○ Verbraucht + ○ Verbraucher_bereit
Petri-Netz modelliert Synchronisation: Verbraucher kann erst konsumieren, wenn 1) Puffer-Marke da UND 2) Verbraucher-bereit-Marke da.
Ampel-Steuerung
Modelliere Zustände (Grün/Gelb/Rot) als Stellen, Übergänge als Transitionen, Zeitgeber als spezielle Transitionen.
Petri-Netz-Sicht in Geschäftsprozessen
EPK und BPMN können als Petri-Netze interpretiert werden, dann lassen sich Eigenschaften formal beweisen (z.B. Deadlock-Freiheit).
Eigenschaften eines Petri-Netzes
Erreichbarkeit (Reachability)
Welche Markierungen (Verteilung von Marken auf Stellen) können vom Start aus erreicht werden?
→ Erreichbarkeits-Graph: Knoten = Markierungen, Kanten = Transitions-Schaltungen.
Beschränktheit (Boundedness)
Ein Netz ist k-beschränkt, wenn keine Stelle mehr als k Marken bekommt. 1-beschränkt heißt sicher (safe).
Lebendigkeit (Liveness)
| Stufe | Bedeutung |
|---|---|
| L0 (tot) | Transition kann NIE schalten |
| L1 | Transition kann mindestens 1× schalten |
| L2 | Beliebig oft schaltbar |
| L3 | Schaltbar in unendlich vielen Markierungs-Folgen |
| L4 (lebendig) | In jeder erreichbaren Markierung gibt es eine Schaltfolge die Transition aktiviert |
L4 = "lebendiges Netz", keine Deadlocks.
Deadlock-Freiheit
Deadlock: Markierung in der keine Transition mehr schalten kann.
Petri-Netze erlauben formales Beweisen der Deadlock-Freiheit via Erreichbarkeits-Analyse.
Varianten
Klassische Petri-Netze (Place/Transition-Netze)
Ungekennzeichnete Marken (alle gleich). Standardform.
Höhere Petri-Netze
Gefärbte Petri-Netze (CPN): Marken haben Farben/Typen, können unterschiedliche Datenwerte tragen.
Zeitbehaftete Petri-Netze: Transitionen haben Zeitverzögerungen.
Stochastische Petri-Netze: Schalten mit Wahrscheinlichkeiten.
Hierarchische Petri-Netze: Sub-Netze als 'Black Boxes' geschachtelt.
Petri-Netze vs. andere Modelle
| Modell | Wann? |
|---|---|
| Petri-Netze | Nebenläufigkeit + Synchronisation, formal beweisbar |
| Aktivitätsdiagramm | Software-Workflow |
| BPMN | Geschäftsprozess, weniger formal |
| Endlicher Automat | Sequenzielles System, ein Zustand |
| Sequenzdiagramm | Objekt-Interaktionen über Zeit |
Petri-Netze sind mächtiger als endliche Automaten, können unendlich viele Zustände modellieren (durch Marken-Akkumulation).
Verhaltens-Analyse
Aus einem Petri-Netz kann man berechnen:
- Erreichbarkeits-Graph: alle möglichen Markierungen
- Invarianten: Erhaltungs-Größen (P-Invarianten + T-Invarianten)
- Deadlocks / Livelocks
- Wartezeiten (bei zeitbehafteten Netzen)
Software-Tools: CPN Tools (DAIMI), Snoopy (Cottbus), TINA (Toulouse), Renew (Hamburg).
Klausur-Faustregeln
1. Petri-Netz = bipartiter Graph, Stellen ↔ Transitionen, KEINE Stelle-Stelle-Kante.
2. Transition aktiviert wenn ALLE Pre-Stellen ≥ 1 Marke.
3. Schalten: −1 in Pre-Stellen, +1 in Post-Stellen.
4. Beschränkt + lebendig = idealer Zustand. Beschränkt (keine Marken-Explosion) + lebendig (kein Deadlock).
5. Deadlock = Markierung ohne schaltbare Transition.
6. Sicher = 1-beschränkt. Keine Stelle mehr als 1 Marke.
Häufige Stolpersteine
1. Stelle-Stelle oder Transition-Transition-Kante. STRENG VERBOTEN. Petri-Netz ist BIPARTIT. Klausur-Falle.
2. Schalten ohne alle Pre-Stellen. Eine Transition mit mehreren Pre-Stellen schaltet nur, wenn ALLE Marken haben. Klassiker bei Verbraucher-Beispielen.
3. Petri-Netz als Sequenz lesen. Falsch, Petri-Netze sind NEBENLÄUFIG. Mehrere Transitionen können gleichzeitig aktiviert sein und in beliebiger Reihenfolge schalten.
4. Lebendigkeit mit Erreichbarkeit verwechseln. Erreichbarkeit = welche Markierungen möglich? Lebendigkeit = welche Transitionen können (immer) schalten?
5. Marken als Daten interpretieren in klassischem Netz. Klassisches Petri-Netz: alle Marken gleich. Für Daten-Werte brauchst du gefärbte Petri-Netze (CPN).
6. Zeitbehaftete Petri-Netze mit klassischen verwechseln. Klassisches Petri-Netz hat KEINE Zeit-Semantik, Transitionen schalten sofort. Zeitliche Aspekte → Zeitbehaftete oder Stochastische Petri-Netze.
Interaktiv verstehen
Petri-Netz interaktiv simulieren
Erzeuger-Verbraucher-Modell mit Puffer. Aktivierte Transitionen (orange) klickbar, Marken bewegen sich live.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Modellieren Sie als Petri-Netz" IMMER prüfen: bipartit (Stellen ↔ Transitionen), Marken in Stellen, Aktivierungs-Bedingung (alle Pre-Stellen ≥ 1 Marke). Bei "Beschränktheit/Lebendigkeit prüfen" Erreichbarkeits-Graph aufstellen, alle Markierungen + Übergänge. Deadlock = Markierung ohne schaltbare Transition.
Praxis-Übung
Petri-Netze, Praxis-Übung
6 Aufgaben zu Notation, Schalten und Eigenschaften.
Klausurfragen mit Lösungen (6)
- F1.Welche Elemente bilden ein Petri-Netz?
Antwort: Stellen (Kreise) + Transitionen (Rechtecke) + Marken (Tokens)
Erklärung: Petri-Netz besteht aus: 1) Stellen (Plätze, Kreise), repräsentieren Zustände/Ressourcen. 2) Transitionen (Rechtecke), repräsentieren Aktionen. 3) Marken (Tokens, Punkte), liegen in Stellen, repräsentieren Datenfluss. 4) Kanten (Pfeile), verbinden Stelle ↔ Transition (bipartit). Mathematisch: P/T-Netz N = (S, T, F, M₀).
- F2.Wann ist eine Transition AKTIVIERT (kann schalten)?
Antwort: Wenn ALLE Pre-Stellen jeweils ≥ 1 Marke haben
Erklärung: Aktivierung: ALLE Eingangs-Stellen (Pre-Stellen) müssen mindestens 1 Marke enthalten. Bei Multi-Eingangs-Transitionen ist das eine SYNCHRONISATIONS-Bedingung (typisch für Verbraucher-Pattern). Schalten verbraucht 1 Marke aus jeder Pre-Stelle, legt 1 Marke in jede Post-Stelle. Standard-Formel: M ≥ F⁻(t).
- F3.Ordne Petri-Netz-Element zum Symbol.
Zuordnungen:
- Stelle (Place) → Kreis ○
- Transition → Rechteck ▭
- Marke (Token) → Punkt ● in Stelle
- Kante (Arc) → Pfeil → zwischen Stelle und Transition
Erklärung: Standard-Notation: Kreise für Stellen (Zustände), Rechtecke für Transitionen (Aktionen), Punkte für Marken (Tokens) in Stellen, Pfeile für Kanten. Wichtige Regel: Kanten bipartit, Stelle ↔ Transition, NIE Stelle-Stelle oder Transition-Transition. Klausur-Klassiker beim Erkennen falscher Petri-Netze.
Typ: Zuordnung
- F4.Wann ist ein Petri-Netz '1-beschränkt' (auch 'sicher' genannt)?
Antwort: Keine Stelle hat jemals mehr als 1 Marke
Erklärung: 1-beschränkt = SAFE: in jeder erreichbaren Markierung hat KEINE Stelle mehr als 1 Marke. Anwendung: digitale Schaltungen (boolesche Werte), Synchronisations-Pattern. Allgemein: k-beschränkt = max k Marken pro Stelle. Unbeschränkt = unbegrenzte Marken-Anhäufung möglich (Marken-Explosion).
- F5.In einem Petri-Netz dürfen Kanten direkt zwischen zwei Stellen verlaufen.
Antwort: Falsch
Erklärung: FALSCH. Petri-Netz ist BIPARTIT: Kanten gehen ausschließlich zwischen Stellen und Transitionen, niemals Stelle-Stelle oder Transition-Transition. Diese Bipartität ist essentiell für die Semantik (Transitionen 'konsumieren' Marken aus Stellen, produzieren in Stellen). Wenn Kanten direkt zwischen Stellen wären, gäbe es keine Aktivierungs-Bedingung mehr. Klausur-Klassiker bei Notation-Prüfungen.
Typ: Wahr/Falsch
- F6.Was ist ein Deadlock in einem Petri-Netz?
Antwort: Eine Markierung, in der keine Transition mehr schalten kann
Erklärung: Deadlock = Markierung ohne schaltbare Transition. Das System steht still. In Petri-Netzen kann Deadlock-Freiheit FORMAL bewiesen werden (Erreichbarkeits-Analyse: gibt es eine erreichbare Markierung ohne aktivierte Transition?). Praxis: Verbraucher-Pattern oft Deadlock-anfällig (z.B. zwei Verbraucher warten gegenseitig). Lebendiges Netz (L4) = kein Deadlock möglich.
Klausur-Quiz
Petri-Netze, Klausur-Quiz
6 typische Klausurfragen zu Eigenschaften und Analyse.
Klausurfragen mit Lösungen (6)
- F1.Wer entwickelte das Petri-Netz?
Antwort: Carl Adam Petri (1962, Dissertation)
Erklärung: Petri-Netze: Carl Adam Petri, Dissertation 'Kommunikation mit Automaten', Universität Bonn 1962. Dijkstra = Dining Philosophers, Semaphores. Turing = Turing-Maschine, Berechenbarkeit. Hoare = CSP, Quicksort. Petri war ein Pionier der nebenläufigen Systeme, Petri-Netze sind heute Standard in Modellierung paralleler Systeme.
- F2.Was unterscheidet ein klassisches P/T-Netz von einem gefärbten Petri-Netz (CPN)?
Antwort: CPN-Marken können unterschiedliche Werte/Typen tragen (Farben)
Erklärung: Gefärbtes Petri-Netz (Coloured Petri Net, CPN, Jensen 1981): Marken haben Farben/Typen, können unterschiedliche Datenwerte tragen. Z.B. eine Marke vom Typ Integer mit Wert 42. Klassisches P/T-Netz: alle Marken gleich (anonyme Tokens). CPN ist praktischer für Daten-Modellierung, aber mathematisch komplexer.
- F3.Petri-Netz wurde von {{1}} im Jahr {{2}} entwickelt. Es besteht aus {{3}} (Kreise) und {{4}} (Rechtecke), verbunden durch gerichtete Kanten (bipartit). Eine {{5}} kann schalten, wenn alle Vor-Stellen mindestens 1 Marke enthalten.
Lösungen pro Lücke:
- {{1}}: Carl Adam Petri / Petri / C.A. Petri
- {{2}}: 1962
- {{3}}: Stellen / Places
- {{4}}: Transitionen / Transitions
- {{5}}: Transition
Erklärung: Petri-Netz-Standard: Carl Adam Petri 1962 (Bonn, Dissertation). Bausteine: Stellen (Kreise) + Transitionen (Rechtecke) + Marken + bipartite Kanten. Aktivierungs-Bedingung: alle Pre-Stellen ≥ 1 Marke. Diese Fakten sind PT-Netze-Standard.
Typ: Lückentext
- F4.Bringe die Lebendigkeits-Stufen eines Petri-Netzes in aufsteigender Reihenfolge (von 'tot' zu 'lebendig').
Richtige Reihenfolge:
- L0, Tot: nie schaltbar
- L1, Mindestens 1× schaltbar
- L2, Transition beliebig oft schaltbar
- L4, Lebendig: jede Markierung erlaubt Schaltfolge
Erklärung: Lebendigkeits-Hierarchie (L0 < L1 < L2 < L3 < L4): L0 = tot (NIE schaltbar). L1 = mindestens 1× schaltbar. L2 = beliebig oft (ohne Garantie der Reproduktion). L3 = in unendlich vielen Schaltfolgen aktivierbar. L4 = lebendig (in JEDER erreichbaren Markierung gibt es Schaltfolge, die Transition aktiviert). L4 ist Idealzustand, kein Deadlock möglich.
Typ: Reihenfolge
- F5.Welche Aussage zu Petri-Netzen ist FALSCH?
Antwort: Petri-Netze und endliche Automaten sind äquivalent in ihrer Ausdrucksstärke
Erklärung: FALSCH ist Aussage D. Petri-Netze sind MÄCHTIGER als endliche Automaten, können unendlich viele Zustände modellieren (Marken-Akkumulation in Stellen → unbeschränkte Markierungen). Petri-Netze sind ausdrucksstärker als reguläre Sprachen (FA), aber weniger ausdrucksstark als Turing-Maschinen. Position auf Chomsky-Hierarchie zwischen kontextfrei und kontextsensitiv. Andere Aussagen sind korrekt.
- F6.Ein Petri-Netz kann sowohl beschränkt als auch lebendig sein, diese beiden Eigenschaften zu prüfen ist Hauptzweck der Verhaltens-Analyse.
Antwort: Wahr
Erklärung: RICHTIG. Idealer Zustand eines Petri-Netzes: beschränkt (keine Marken-Explosion) UND lebendig (kein Deadlock). Beschränkt verhindert unendliches Wachsen, lebendig garantiert ständige Aktivität. Verhaltens-Analyse: 1) Erreichbarkeits-Graph aufstellen, 2) Beschränktheits-Test (sind alle Markierungen endlich?), 3) Lebendigkeits-Test (kann jede Transition aus jeder Markierung wieder aktiviert werden?). Software-Tools: CPN Tools, TINA, Renew.
Typ: Wahr/Falsch
