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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
Petri-Netz: Ein gerichteter bipartiter Graph aus Stellen (Zustände) und Transitionen (Aktionen), mit Marken (Tokens) die Aktivierungs-Zustände markieren.
| 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).
Eine Transition t ist aktiviert (enabled), wenn in JEDER Eingangs-Stelle (Pre-Stelle) mindestens 1 Marke liegt.
Aktivierte Transition kann schalten (fire):
Beispiel: Transition mit 2 Eingangsstellen und 1 Ausgangsstelle. Wenn beide Eingangs-Stellen je 1 Marke haben → schaltbar → schalten verbraucht 2 Marken und produziert 1.
○ 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.
Modelliere Zustände (Grün/Gelb/Rot) als Stellen, Übergänge als Transitionen, Zeitgeber als spezielle Transitionen.
EPK und BPMN können als Petri-Netze interpretiert werden — dann lassen sich Eigenschaften formal beweisen (z.B. Deadlock-Freiheit).
Welche Markierungen (Verteilung von Marken auf Stellen) können vom Start aus erreicht werden?
→ Erreichbarkeits-Graph: Knoten = Markierungen, Kanten = Transitions-Schaltungen.
Ein Netz ist k-beschränkt, wenn keine Stelle mehr als k Marken bekommt. 1-beschränkt heißt sicher (safe).
| 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: Markierung in der keine Transition mehr schalten kann.
Petri-Netze erlauben formales Beweisen der Deadlock-Freiheit via Erreichbarkeits-Analyse.
Ungekennzeichnete Marken (alle gleich). Standardform.
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.
| 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).
Aus einem Petri-Netz kann man berechnen:
Software-Tools: CPN Tools (DAIMI), Snoopy (Cottbus), TINA (Toulouse), Renew (Hamburg).
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.
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.
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.
6 Aufgaben zu Notation, Schalten und Eigenschaften.
Klausurfragen mit Lösungen (6)
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₀).
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).
Zuordnungen:
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
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).
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
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.
6 typische Klausurfragen zu Eigenschaften und Analyse.
Klausurfragen mit Lösungen (6)
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.
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.
Lösungen pro Lücke:
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
Richtige Reihenfolge:
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
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.
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