Analyse von Petri-Netz-Modellen

Frontmatter

1. Modellierung mit Petri-Netzen

Zusammenfassung

Zu einem Modell greift man immer dann, wenn man Fragen an ein System hat, die man anhand des Systems selbst nicht beantworten kann; sei es, daß dieses System noch gar nicht existiert (erst entworfen werden soll), sei es, daß die Benutzung des Systems zu kostspielig oder zu gefährlich wäre oder sei es, daß das System zu kompliziert ist. Modellierung bedeutet demnach einen Abstraktionsprozeß, bei dem einige wesentliche Aspekte des betrachteten Systems und seines Verhaltens in einem Modell widergespiegelt werden. Welches die wesentlichen Aspekte sind, hängt natürlich von den Fragen ab, deren Beantwortung gewünscht wird. In diesem Kapitel werden wir versuchen, einen ersten Eindruck davon zu vermitteln, welche Systeme und Systemeigenschaften mit Netzmodellen analysiert werden können, d.h. Fragen welcher Art mit Hilfe von Petri-Netz-Modellen beantwortet werden können.

Peter H. Starke

2. Grundbegriffe

Zusammenfassung

Das Netzmodell eines Systems besteht aus Elementen, die den Zustandsparametern (Zustandskomponenten, Systembedingungen) zugeordnet sind. Diese Elemente werden Plätze oder Stellen, manchmal auch Bedingungen genannt und graphisch durch Kreise dargestellt, ihre Markierung in Form von fetten Punkten (genannt Marken) beschreibt den aktuellen Stand der Erfiilltheit der Systembedingungen, d.h. den Systemzustand.

Peter H. Starke

3. Nebenläufigkeit und Konflikt

Zusammenfassung

Die Arbeit der zu modellierenden Systeme vollzieht sich in der Zeit, deshalb erscheint es natürlich, auch für die Systemmodelle eine Zeitskala zu postulieren, die als Modell der realen Zelt dient. Dieses Vorgehen ist sicher für bestimmte Anwendungen unumgänglich, hat aber eine Reihe von Nachteilen, die für eine grundlegende Theorie informationeller Systeme untragbar sind.

Peter H. Starke

4. Beschränktheit

Zusammenfassung

Wenn ein Netzmodell eines Systems, z.B. einer Steuerung, entworfen 1st, stellt sich als eines der ersten Verifikationsprobleme die Frage nach der Realisierbarkeit, d.h. die Frage, ob wir ein System mit endlicher Zustandsmenge entworfen haben. Die entsprechende Frage auf der Netzebene ist die nach der Beschränktheit des Netzes.

Peter H. Starke

5. Überdeckbarkeit und Erreichbarkeit

Zusammenfassung

Die Frage nach der Erreichbarkeit einer bestimmten Markierung in einem Netzmodell ist die Frage danach, ob das System einen bestimmten denkbaren Zustand annehmen kann. Wenn es sich dabei um einen gefährlichen Zustand handelt, kann diese Frage allein der Grund für die Modellierung sein. Bei einem verteilten System wird es dabei häufig nicht um einen einzelnen Zustand gehen, sondern um eine Klasse von Zuständen, die nur in den Werten bestimmter Parameter übereinstimmen, d.h. es geht um alle die Zustände, bei denen gewisse Teilsysteme gegebene Teilzustände haben. Im Netzmodell kann diese Situation dadurch widergespiegelt werden, daß man nach der Erreichbarkeit einer Teilmarkierung, also einer Markierung einer Teilmenge der Platzmenge fragt. Andererseits kann die Zustandsklasse so bestimmt sein, daß ihren Elementen Markierungen entsprechen, die eine gegebene Markierung in den Markenzahlen platzweise nicht unterschreiten, sie überdecken.

Peter H. Starke

6. Lebendigkeit

Zusammenfassung

Von einer Verklemmung spricht man dann, wenn sich nichts mehr bewegen kann. Die Verklemmung kann das gesamte System betreffen, z.B. wenn alle Prozesse auf Nachrichten warten, die von ihnen selbst erzeugt werden müssen, oder nur Teile des Systems, z.B. wenn zwei Prozesse sich gegenseitig blockieren, andere aber weiterarbeiten. In diesem Abschnitt werden wir das zur Reflektion solcher Phänomene nötige Begriffssystem und erste Ansätze zur Analyse der entsprechenden Eigenschaften entwickeln.

Peter H. Starke

7. Äquivalente Markierungen

Zusammenfassung

Wenn wir nochmals das Netz in der Abbildung 1.1 (Seite 17) betrachten, erkennen wir, daß hier ein System modelliert wird, bei dem drei Teilsysteme gleichberechtigt agieren. Es liegt nahe, diese Symmetrie des Systems und des Netzmodells bei der Analyse auszunutzen. Wir stellen im folgenden Ideen dazu dar, die von JENSEN (für gefärbte Netze) entwickelt wurden.

Peter H. Starke

8. Sture Transitionen

Zusammenfassung

Im Abschnitt 7 haben wir Erreichbarkeitsgraphen betrachtet, die nicht alle erreichbaren Markierungen enthalten, es aber dennoch gestatten, Aussagen über das Verhalten des betreffenden Netzes abzuleiten. Die Hauptschwierigkeit des angegebenen Verfahrens besteht in der Bestimmung der Symmetriegruppe des Netzes bzw. einer adäquaten Untergruppe. Ist ein Netz graphisch gegeben, so kann es leicht sein, (wie in unseren Beispielen) wenigstens einige Symmetrien visuell zu erkennen. Wir müssen aber auch ari Anwendungsfälle denken, wie sie bei der Verifikation von Kommunikationssoftware auftreten, wo das Netz aus einer irgendwie gegebenen Spezifikation automatisch erzeugt wird. Der hier dargestellte Ansatz von VALMARI vermeidet diese Schwierigkeit, er nutzt stattdessen Freiheiten in der Reihenfolge des Schaltens von Transitionen aus, wie sie von Nebenläufigkeit (vgl. Abschnitt 3) impliziert werden. Das Ziel besteht auch hier darin, einen möglichst kleinen Ausschnitt des Erreichbarkeitsgraphen zu konstruieren, aus dem sich noch Aussagen beweisen lassen. Der zentrale Begriff dabei ist der der sturen Menge von Transitionen.

Peter H. Starke

9. Reduktion

Zusammenfassung

Eine weitere Methode, zu kleineren Erreichbarkeitsgraphen zu kommen, besteht in der schrittweisen Reduktion des Netzes. Ein Reduktionsschritt besteht dabei im Ersetzen eines Unternetzes durch ein anderes Unternetz (im allgemeinen mit weniger Plätzen) in einer solchen Weise, daß die interessierenden Eigenschaften des Netzes bei dieser Transformation invariant bleiben. Dabei nennen wir eine Eigenschaft E invariant beim Übergang vom Netz N zum Netz N′,wenn das Netz N′ dann und nur dann die Eigenschaft E hat, wenn N die Eigenschaft E hat. Die Eigenschaften, die uns hier interessieren werden, sind Lebendigkeit und Beschränktheit.

Peter H. Starke

10. Netztypen

Zusammenfassung

In diesem Abschnitt besprechen wir die Zusammenhänge zwischen verschiedenen bei der Systemmodellierung verwendeten Netztypen, insbesondere gehen wir auf ihre gegenseitige Simulierbarkeit ein. Bei einer ersten Bekanntschaft und Begeisterung für die Konzepte der Netztheorie ist man leicht geneigt, für eigene Anwendungen bequeme Modifikationen der Grundbegriffe, insbesondere der Schaltregel, vorzunehmen. Man gewinnt damit unter Umständen einfachere und übersichtlichere Modelle, verliert aber in vielen Fällen die Möglichkeit zu analysieren, weil die entsprechenden theoretischen Resultate für den ad hoc definierten Netztyp nicht vorliegen. Einen solchen Netztyp kann mari natürlich erfolgreich als Beschreibungssprache, als Mittel zur Modellbildung und als Grundlage für Ablaufsimulationen anwenden, aber der wesentliche Vorteil der Modellierung mit Petri-Netzen, eine entwickelte Netztheorie im Rücken zu haben, geht verloren.

Peter H. Starke

11. Invarianten

Zusammenfassung

Als Invariante eines Systems bezeichnet man gewöhnlich eine solche Eigenschaft, die bei der Arbeit des Systems unabhängig vom konkreten Ablauf erhalten bleibt. Wir haben bereits Fakten (tote Transitionen) als Widerspiegelung solcher Systeminvarianten kennengelernt. In diesem Abschnitt werden wir die Lösungen gewisser homogener Gleichungssysteme als Invarianten bezeichnen, diese Bezeichnung aber dadurch rechtfertigen, daß wir ihren Zusammenhang mit Invarianten des modellierten Systems aufzeigen.

Peter H. Starke

12. Fairness

Zusammenfassung

Verklemmungsfreiheit und Lebendigkeit sind wichtige Eigenschaften für Systeme, die fortlaufend arbeiten sollen, z.B. um Steuerungs- oder Kontrollfunktionen kontinuierlich wahrzunehmen. Es kann aber nicht ausgeschlossen werden, daß eine durchaus immer wieder ausführbare Aktion niemals ausgeführt wird, weil das System einerseits die Freiheit hat, unter den ausführbaren Aktionen eine oder einige zur Ausführung auszuwählen, andererseits das Auswahlprinzip in irgendeinem Sinne unfair oder überhaupt nicht präzisiert ist, also einige Aktionen benachteiligt. Im letzten Fall sagt man, daß für eine solche Aktion die Gefahr eines Livelocks besteht. In diesem Abschnitt beschäftigen wir uns mit der Widerspiegelung derartiger Phänomene in Petri-Netz-Modellen.

Peter H. Starke

13. Synchronie

Zusammenfassung

Man bezeichnet Aktivitäten als synchronisiert, wenn sie nur gleichzeitig ausgeführt werden können; in einem Petri-Netz-Modell würde ihnen eine gemeinsame Transition entsprechen. Wir beschäftigen uns hier mit der Frage nach (i.a. nicht sofort erkennbaren) Abhängigkeiten zwischen Schaltvorgängen. Unser Interesse an dieser Frage leitet sich aus der im vorigen Abschnitt, besprochenen Livelock-Problematik her.

Peter H. Starke

14. Struktureigenschaften

Zusammenfassung

Mit diesem Abschnitt beginnen wir die Darstellung von Ergebnissen der Netztheorie, die Zusammenhänge zwischen der Struktur von Petri-Netzen und ihrem Verhalten zum Inhalt haben. Ein triviales Beispiel bildet die Aussage, daß jedes Petri-Netz, bei dem alle Spalten der Akzidenzmatrix die Summe 0 haben, bei dem also das Schalten einer Transition keine Änderung der Markenzahl im Netz bewirkt, bei jeder Anfangsmarkierung beschränkt ist. Nicht ganz so billig ist die Aussage, daß jedes gewöhnliche Petri-Netz, das als Graph stark-zusammenhängend ist, bei dem jede Transition genau einen Vorplatz und genau einen Nachplatz besitzt und das eine Marke enthält, lebendig ist. Wir können hier nicht erwarten, allgemeingültige strukturelle Kriterien für das Vorliegen dynamischer Eigenschaften von Netzen zu finden, aber insbesondere für gewöhnliche Netze liegen Resultate vor, die hilfreich für die Analyse sind. Es muß betont werden, daß diese Ergebnisse nur für Netze unter der normalen Schaltregel bewiesen werden. Im Abschnitt 10 haben wir an Beispielen gesehen, daß Veränderungen der Schaltregel wesentliche Veränderungen der Verhaltenseigenschaften nach sich ziehen können.

Peter H. Starke

15. Die Deadlock-Falle-Eigenschaft

Zusammenfassung

Wir haben im vorigen Abschnitt gesehen, daß Deadlocks, die nicht ausreichend viele Marken haben, nicht wieder mit Marken versorgt werden können, so daß es zu Verklemmungen kommen kann. In jedem Netz, das keine Transitionen ohne Vorplatz enthält, also in allen praktisch initeresssanten Fällen, ist die Menge P aller Plätze ein Deadlock. Die Aussage. daß ein Netz ohne Deadlock lebendig ist, nützt also wenig. Daher sucht man nach Strukturen innerhalb eines Deadlocks, die verhindern können, daß er seine Marken verliert. Eine solche Struktur ist durch den Begriff der Falle (für Marken) gegeben.

Peter H. Starke

16. Dekomposition

Zusammenfassung

Mit Hilfe der Deadlock-Falle-Eigenschaft gelingt es, für große Klassen von Netzen die Lebendigkeit zu beweisen, über die Beschränkheit wird dabei nicht ausgesagt. Strukturelle Methoden zum Nachweis von Lebendigkeit und Sicherheit bzw. Beschränktheit beruhen auf der Idee, das gegebene Netz als überlagerung (Komposition) von lebendigen und sicheren Netzteilen aufzufassen. Hierbei dienen Zustandsmaschinen als Prototypen lebendiger und beschränkter Netze (vgl. Abschnitt 14). Wir beschränken uns daher in diesem Abschnitt auf die Betrachtung gewöhnlicher zusammenhängender Netze. In vielen Fällen ist auch die Anfangsmarkierung nicht von Bedeutung, so daß wir mit Netzstrukturen N = [P,T,F] arbeiten können.

Peter H. Starke

17. Zeitbewertete Netze

Zusammenfassung

In diesem und den folgenden beiden Abschnitten postulieren wir die Existenz und Verfügbarkeit einer Zeitskala im modellierten System, ungeachtet der Einwände, die wir dagegen im Abschnitt 3 erhoben haben. Mit anderen Worten, die hier für zeitbewertete Netze dargestellten Ergebnisse haben natürlich ihre Berechtigung, ihre Anwendbarkeit ist aber sozusagen auf makroskopische Verhältnisse beschränkt, d.h. auf Bedingungen, unter denen Gleichzeitigkeit mit hinreichender Genauigkeit festgestellt werden kann.

Peter H. Starke

18. Netze mit Schaltdauer

Zusammenfassung

In diesem Abschnitt betrachten wir Petri-Netze, deren Transitionen eine Schaltdauer zugeordnet ist. Die von einer Transition modellierte Aktion wird nicht mehr als momentan angesehen, sondern es wird angenommen, daß zu ihrer Ausführung ein nicht zuvernachlässigender Zeitbetrag verbraucht wird. Damit entstehen neue Probleme, die insbesondere die Lösung von Konflikten bzw. ihr Auftreten betreffen. Wir haben von einer Konfusion als einer Situation gesprochen, in der nicht entschieden werden kann, ob ein Konflikt objektiv auftritt. Durch eventuell mit unterschiedlicher Geschwindigkeit arbeitende Systemteile können solche Konfusionen aufgelöst und Konflikte einseitig entschieden werden, so daß ein lebendiges Netz unter Zeitbewertung Verklernmungen aufweist.

Peter H. Starke

19. Zeit-Netze

Zusammenfassung

Dieser Abschnitt ist Petri-Netzen gewidmet, bei denen die Zeitbewertung der Transitionen durch Schaltintervalle [α,β] erfolgt, dabei sind a und β nicht negative rationale Zahlen mit α ≤ β. Die Zahl α wird als früheste Schaltzeit (earliest firing time) und die Zahl β als späteste Schaltzeit (latest firing time) der jeweiligen Transition verstanden, d.h. das Schalten der Transition erfolgt frühestens α Zeiteinheiten und spätestens β Zeiteinheiten nach der Konzessionierung (sofern die Konzession nicht im Zeitintervall [0,β] verloren wurde). Dabei kann α = β = 0 sein, eine solche Transition muß sofort bei der Konzessionierung schalten. Auch in diesem Abschnitt lassen wir Nebenläufigkeit mit sich selbst nicht zu. Daher genügt es, jede Transition t mit genau einer Uhr auszurüsten, die abgestellt ist, solange t nicht Konzession hat, und die anderenfalls die Zeit anzeigt, die seit der Konzessionierung von t vergangen ist. Wir setzen voraus, daß alle diese Uhren von der globalen Zeitskala synchronisiert werden, d.h. daß sie alle gleich schnell laufen. Im Zustand eines Zeit-Netzes wird also neben der Markierung auch die Stellung der Uhren zu berücksichtigen sein.

Peter H. Starke

20. Gefärbte Petri-Netze

Zusammenfassung

In diesem und dem folgenden Abschnitt beschäftigen wir uns mit Netzen, die zu den sogenannte „höheren“ Netztypen gehören und sich von den klassischen Petri-Netzen darin unterscheiden, daß sie mit Marken verschiedener Sorten umgehen. Den Ausgangspunkt für überlegungen, die zu diesem Netzbegriffen führten, bildete die Erfahrung, daß praktische Probleme in der Regel zu sehr großen und damit unübersichtlichen Netzen führen, die sich aber zugleich häufig durch eine gewisse Regelmäßigkeit auszeichnen.

Peter H. Starke

21. Prädikat/Transitions-Netze

Zusammenfassung

Wie die im vorigen Abschnitt eingeführten gefärbten Netze bilden auch die Prädikat/Transitions-Netze einen höheren Netztyp, verwenden also Marken unterscheidbarer Sorten. Die Marken sind aber nicht nur durch ein einfaches Merkmal, ihre Farbe, unterschieden, sondern auch durch ihre Struktur. Prädikat/Transitions-Netze gehen mit strukturierten Marken um. In dieser Hinsicht gehören die im Abschnitt 10 erwähnten FIFO-Netze zu den Prädikat/Transitions-Netzen, denn Wörter (Marken in FIFO-Netzen) unterscheiden sich durch ihre Struktur, durch ihren Aufbau aus Buchstaben.

Peter H. Starke

20. Werkzeuge

Zusammenfassung

Rechnergestützte Werkzeuge zur Automatisierung von Analyse-Verfahren sind für die praktische Arbeit mit Petri-Netzen unerläßlich, sobald man von der reinen Modellierung, Veranschaulichung und Demonstration, eventuell verbunden mit einer Ablauf-Simulation zu einer zielgerichteten Untersuchung der Netzmodelle übergeht. Entsprechend den verfolgten Zielen hat man die Werkzeuge und ihren Einsatz zu wählen. Man kann sagen, daß sich das Niveau der Anwendungen von Petri-Netzen daran ablesen läßt, Werkzeuge welcher Art und welchen theoretischen Anspruchs nachgefragt werden.

Peter H. Starke

Backmatter