Modellierung paralleler Systeme PDF

Kapitel 4 Modellierung paralleler Systeme 4.1 Einleitung Dieses Kapitel führt nun die vorherigen Kapitel, welche parallele Programme be- reits behandelt haben, unter dem Aspekt der Formalisierung zusammen. Wir ha- ben bereits verschiedene Formen der Interaktion zwischen Programmen kennen- gele...

Kapitel 4 Modellierung paralleler Systeme 4.1 Einleitung Dieses Kapitel führt nun die vorherigen Kapitel, welche parallele Programme be- reits behandelt haben, unter dem Aspekt der Formalisierung zusammen. Wir ha- ben bereits verschiedene Formen der Interaktion zwischen Programmen kennen- gelernt und Eigenschaften paralleler Programme und deren Beschreibung in ver- schiedenen Abstraktionsebenen betrachtet. Dieses Kapitel möchte parallele Aktivitäten auf Modell-Ebene formalisieren. Im Genaueren werden werden Zustandsautomaten und Petrinetze betrachtet, wobei der Fokus der Vorlesung auf letzteren liegt. Petrinetze modellieren Zustände und Zustandsveränderungen durch Ereignisse. Diese haben das Ziel, parallele Syste- me auf verständliche Weise zu beschreiben und zu analysieren durch Beschrän- kungen auf die wesentlichen Eigenschaften. 4.2 Zustandsautomaten 4.2.1 Definition Ein Zustandsautomat ist ein nicht deterministischer endlicher Automat. Das be- deutet: Transitionsaktionen sind von Zuständen ausführbar, wodurch ein neu- er Systemzustand erzeugen wird. Die Transitionaktions-Auswahl kann zu unter- schiedlichen Nachfolgezuständen führen. 92 Ein Zustandsautomat ist folglich durch eine Menge an Transitionsaktionen A und einer Menge an möglichen Zuständen S (=Zustandsraum) angegeben. Wenn S ⊆ S1 × S2 wurde S aus den beiden unterschiedlichen Mengen S1 und S2 zu- sammengesetzt. Zustände können durch Transistionsaktionen (A) erreicht wer- den. (Bildlich durch Beschriftung der gerichteten Pfeile zwischen den Zuständen dargestellt (siehe Abbildung 4.1)). Anfangszustände werden durch die Menge S0 definiert. Zustandsübergangsrelationen sind folgendermaßen definiert: R ⊆ S × A × S. Das bedeutet, dass eine Relation, aus einem Zustand, mithilfe einer Transition einen neuen Zustand erzeugt. Beide Zustände kommen aus derselben Zustands- menge. Mathematisch formuliert: Seien s0 , s1 ∈ S und a ∈ A gegeben, so gilt im Zustand s0 : Die Aktion a kann ausgeführt werden, um den Zustand s1 zu erreichen (s0 → s1 ), falls die Zustandsübergangsrelation (s0 , a, s1 ) ∈ R. 4.2.2 Beispiel: Fahrkartenautomat In jedem Zustand steht links die ausgewählte Fahrkarte und rechts der noch zu bezahlende Geldbetrag. Die von Zuständen ausgehenden Transitionsaktionen stel- len alle Interaktionsmöglichkeiten der einzelnen Knoten dar. Zum Beispiel der Ausgangszustand (Wahl,0) ermöglicht einem Kunden auszu- wählen, welche Fahrkarte er kaufen möchte. Zur Auswahl stehen die beiden Op- tionen: Kurzstrecke (ein Euro) und normale Fahrt (zwei Euro). Beide Zustände können über je eine Transitionsaktion, Wahl der Fahrkarte, erreicht werden. An- schließend wird der Kunde aufgefordert zu bezahlen. Je nachdem wie viel Geld ein Kunde in den Automaten einwirft, wechselt der Zustand, bis kein Restbe- trag mehr gezahlt werden muss. Die Karte wird ausgedruckt und gegebenenfalls Wechselgeld ausgezahlt. Der Ausgangszustand wird wieder erreicht. 4.2.3 Aktionsspuren Während Zustandsautomaten einen Prozess modellieren, stellen Aktionsspuren das Verhalten eines Prozesses dar. Aktionen sind dabei deterministisch, falls für jeden Zustand höchstens ein Nachfolgezustand existiert. 93  Wahl normale Fahrt Wahl Kurzstrecke (normal,2) (Wahl,0) Ausgabe Ausgabe Einwurf normale kurze Einwurf 2 Euro Fahrkarte Fahrt 1 Euro Einwurf 1 Euro Rückgabe (normal,1) (normal, 0) 1 Euro (kurz,0) Einwurf (kurz,1) 1 Euro Rückgabe 1 Euro Rückgabe Einwurf 2 1 Euro Einwurf Euro 2 Euro Ausgabe Ausgabe normale kurze Fahrkarte Fahrt (normal, -1) (Wahl, -1) (kurz,-1) Abbildung 4.1: Beispiel: Fahrkartenautomat Sei Z = (S, A, R, S0 ) ein Zustandsautomat. Eine Folge ai , mit 1 ≤ i ≤ k und k ∈ N ∪ {∞} ist eine endliche oder unend- liche Aktionsspur des Zustandsautomaten Z, falls gilt: – Es existiert eine Folge von Zuständen si , mit si ∈ S, s1 ∈ S0 , und – si−1 → ai si für alle i mit 1 < i ≤ k. Eine Aktion a heißt deterministisch, wenn für jeden Zustand s ∈ S höch- stens ein Nachfolgezustand s f ∈ S existiert mit s → a s f. Als Aktionsspuren werden endliche oder unendliche Spuren eines Zustandsauto- maten, ausgehend von Anfangszuständen, beschrieben. 4.3 Petri-Netze Petri-Netze erlauben graphische Verhaltensmodellierung sowie die Beschreibung eines nebenläufigen Systems und dessen Abläufen. Das Model trifft keine Aus- sage über die zeitliche Komponente. Petri-Netze sind ebenfalls Basis für UML- Aktionsdiagramme. 94 4.3.1 Struktur eines Petri-Netzes Ein Petri-Netz (vgl. 4.2) ist ein Tripel (S, T, F ) mit – S endliche Menge von Stellen, dargestellt durch eine Kreis: , – T endliche Menge von Transitionen1 , dargestellt durch Rechtecke: , – F ⊆ (S × T ) ∪ ( T × S) eine Flussrelation, dargestellt durch die Pfeile.. Für einen Knoten x ∈ (S ∪ T ) gilt: – x = {y | yFx } ist derVorbereich, – x = {y | xFy} ist der Nachbereich. Stellen modellieren passive Elemente, z.B. Speicherzellen, während aktive Ele- mente, z.B. Prozessoren und Prozesse, durch Transitionen modelliert werden. Au- ßerdem ist zu beachten, dass in der Flussrelation nur Paare aus genau einer Stelle und genau einer Transition vorkommen, d.h. es folgen nie zwei Transitionen oder zwei Stellen aufeinander. s1 s3 x t1 x s2 s4 Abbildung 4.2: Petri-Netz 1 Achtung:Transitionen sind nicht das selbe wie Transitionsaktionen. Transitionsaktionen wer- den in Zustandsautomaten verwendet. Transitionen werden in Petrinetzen vewendet 95 Beispiel: Materialverarbeitung In Abbildung 4.3 wird eine Materialverarbeitungskette als weiteres Beispiel ge- zeigt. Stellen repräsentieren Zustände, während Transitionen für Aktionen stehen. Die Vor- und Nachbereiche sind entsprechend aufgezeichnet. Bestellung Bestellaufnahme Lieferauftrag Auslieferung Waren Bestellaufnahme Bestellaufnahme Produktionsauftrag Produktion Lager Abbildung 4.3: Beispiel Petri-Netz, Materialverarbeitung Teile des Petri-Netzes können durch eine detailliertere Modellierungen ersetzt werden. Der Wechsel zwischen den Abstraktionsebenen wird Verfeinerung ge- nannt. In dem Beispiel 4.3 kann der Schritt «Auslieferung» genauer betrachtet werden, und wiederum als Petri-Netz dargestellt werden. Eine mögliche Verfeinerung ist auf dem Bild 4.4 zu sehen. 4.3.2 Zustand eines Petri-Netzes Definition: Markiertes Netz, Stellen-Transitionsnetz Es sei ein Petri-Netz gegeben. Die Abbildung c : S → N ∪ {∞} beschreibt die Kapazität einer Stelle. Wenn die Kapazität der Stellen nicht explizit begrenzt sind, besitzen sie eine unendliche Kapazität. 96  Lieferauftrag Lieferscheinerstellung Lieferschein Versenden Waren Lager Verpacken verpackte Produkte Abbildung 4.4: Verfeinerung von dem Beispiel 4.3 Die Abbildung w:F→N beschreibt die Gewichtung einer Kante. Wenn das Kantengewicht nicht angege- ben ist, ist es 1. Kanten mit dem Gewicht 0 können Token erzeugen beziehungs- weise vernichten. t1 t1 0 0 Erzeuger Verbraucher Ein Stellen-Transitionsnetz ist ein 6-Tupel (S, T, F, c, w, m), also ein Petri-Netz mit den definierten Abbildungen c und w, und zusätzlichen einer Abbildung m : S → N, die auch Markierung genannt wird. Elemente der Bildmenge heißen Marken oder Tokens. Alle momentanen Markierungen bilden den Zustand eines Petri- Netzes. 97 Es können nicht mehr Token in einer Stelle vorliegen, als deren Kapazität zulässt. Ein boolisches Netz (auch: Bedingungs/Ereignisnetz) ist ein markiertes Netz mit m : S → {0, 1}. Also kann maximal ein Token in einer Stelle sein. In diesem Spezi- alfall wird eine markierte Stelle true und eine nicht markierte Stelle false genannt. Beispiele s1 2 s1 s2 t1 s3 t1 s2 1 1 1 1 3 Das Petri-Netz hat zwei Stellen, s1 und Das Petri-Netz hat drei Stellen s1 , s2 , s3. s2. Beide Stellen haben die Kapazi- Die Kapazität der Stelle s2 ist 3, die tät 1, also c(s1 ) = c(s2 ) = 1. Die Kapazität von s1 und s3 ist unend- Kanten (s1 , t1 ) und (t1 , s2 ) sind jeweils
lich. Kante (t1 , s3 ) hat das Gewicht mit 1 gewichtet,
also w ( s 1 , t 1 ) = 2. Andere Kanten sind nicht explizit w (t1 , s2 ) = 1. Die Stelle s1 ist mar- gewichtet, haben also jeweils das kiert, die Stelle s2 nicht. Also m(s1 ) = 1, Gewicht 1. Es gilt m(s3 ) = 3, m(s2 ) = m(s2 ) = 0. Da die Kapazität der Stellen 1, m(s1 ) = 0. Die Menge der Paare höchstens 1 sein darf, stellt das Beispiel {(s3 , 3), (s2 , 1), (s1 , 0)} beschreibt den ein boolisches Netz dar. Zustand des Netzes. 4.3.3 Verhalten eines Petri-Netzes Schaltregel - Transitionsbereitschaft Ein markiertes Netz (S, T, F, c, w, m) mit einer Anfangsmarkierung M0 sei gege- ben. Ein Zustandsübergang erfolgt durch das Schalten von Transitionen. Eine Transition t ∈ T kann schalten (d.h. transitionsbereit), falls
1. ∀s ∈ t gilt: m(s) ≥ w (s, t). Die Markierung jeder Stelle im Vorbereich der Transition muss mindestens gleich mächtig wie die Gewichtung der verbin- denden Kante sein. 98 
2. ∀s ∈ t gilt: m(s) + w (t, s) ≤ c(s). Jede Stelle im Nachbereich muss au- ßerdem in der Lage sein, die Gewichtung der eingehenden Kante, zusätzlich zu den bereits vorhandenen Tokens, zu tragen. Schaltregel - Folgemarkierungen Durch das Schalten wird die Folgemarkierung M′ mit einer neuen Markierungs- funktion m′ erzeugt: 1. ∀s ∈ t \ t gilt: m′ (s) = m(s) − w (s, t)
Von der Markierung jedes Knotens im Vorbereich wird das Gewicht der zu- gehörigen Kante abgezogen. Das bedeutet, dass die Anzahl der Token um das Kantengewicht reduziert wird. 2. ∀s′ ∈ t \ t gilt: m′ (s′ ) = m(s′ ) + w (t, s′ )
Zu jeder Markierung im Nachbereich wird das Gewicht der zugehörigen Kante addiert. 3. ∀s′′ ∈ t ∩ t gilt: m′ (s′′ ) = m(s′′ ) − w (s′′ , t) + w (t, s′′ ).

Beschreibt die Kombination beider Varianten. Hierzu stellt man sich ein fol- gendes Netz vor: 2 2 Die Stelle ist sowohl im Vor-, als auch im Nachbereich vorhanden. Das Netz kann nicht boolisch sein: Falls die Stelle leer wäre und jede Kante das Ge- wicht 1 hätte, dann könnte die Transition nicht schalten. Die Bedingung im Vorbereich wäre nicht erfüllt. Umgekehrt, falls die Stelle bereits eine Mar- kierung hätte, dann wäre die Bedingung im Nachbereich nicht erfüllt. Ist die Kapazität der Stelle hingegen unbegrenzt, würde die Markierung mit jedem Schalten um 1 erhöht werden. 4. Für alle anderen Stellen s des Netzes, die weder im Vorbereich, noch im Nachbereich enthalten sind, ändert sich nichts: m′ (s) = m(s). 99 Beispiele für Schaltungen s1 s3 s1 s3 t1 s4 t1 s4 Schalten s2 s5 s2 s5 Vor Nach Abbildung 4.5: Beispiel Schaltregel 1 Jede Kante hat die Gewichtung 1. Zuerst werden s1 und s2 geprüft.
Damit die Bedingung
für den Vorbereich erfüllt ist, muss m(s1 ) ≥ w (s1 , t1 ) und m(s2 ) ≥ w (s2 , t1 ) gelten. Da c(s3 ) = c(s4 ) = c(s5 ) = ∞ ist auch die Bedingung für den Nachbereich erfüllt. Daher kann t1 schalten. Nach dem Schalten wird die Markierung von jeder Stelle im Vorbereich um das Gewicht der ausgehenden Kante reduziert. Die Markierung jeder Stelle im Nach- bereich erhöht sich um das Gewicht der eingehende Kante. Beispiel 2 analog. s1 s3 s1 s3 3 3 t1 s4 t1 s4 Schalten 2 2 s2 s2 Vor Nach Abbildung 4.6: Beispiel Schaltregel 2 100 Achtung: Tokens «wandern» nicht durch die Transitionen! Es entscheiden nur die Gewichte der Kanten, wie viel tatsächlich aus dem Vorbereich konsumiert, und in dem Nachbereich erzeugt wird. Die Markierungen im Vorbereich und die Mar- kierungen im Nachbereich sind nicht aneinander gekoppelt. Schaltungen in booleschen Netzen s1 s1 t1 s3 t1 s3 Schalten s2 s2 Vor Nach Ein boolisches Netz kann erst dann schalten, wenn alle Stellen im Vorbereich mar- kiert sind, und alle Stellen im Nachbereich keine Tokens haben. Alle Kapazitäten der Stellen sind true, alle Gewichte der Kanten sind 1. Beispiele für nicht schaltbare Transitionen s1 3 t1 s3 s2
Nicht schaltbar, da m(s1 ) < w (s1 , t1 ). s1 t1 s2 3 Nicht schaltbar, da m(s2 ) = c(s2 ). 101 4.4 Modellierung von Systemeigenschaften Auch Prozesse können mithilfe von Petri-Netzen dargestellt werden. Im Folgen- den werden der Determinismus und die verschiedenen Eigenschafen in Petri- Netzen betrachtet. 4.4.1 Nichtdeterminismus Eine der wichtigsten Anforderungen an ein Rechensystem ist, dass es determi- nistisch2 ist. Petri-Netze sind jedoch laut Definition nicht zwingend determini- stisch. Zustände bei denen nicht vorhergesagt werden kann, welche Transition als nächstes geschaltet wird, dürfen in einem entsprechenden Petri-Netz nicht vor- kommen. Die Graphik 4.7 zeigt die Auswirkungen des nicht-Determinismus auf das Sy- stem: Zu Beginn sind t2 und t4 schaltbar. Wird nun wie in dem Beispiel t2 zuerst geschaltet, ist die Transition t4 nicht mehr schaltfähig. Würde t4 zuerst geschaltet werden könnte wiederum t2 nicht mehr geschaltet werden. 4.4.2 Erreichbarkeit Ein Erreichbarkeitsgraph beschreibt alle möglichen Zustände eines Petri-Netzes und wie sie ineinander übergehen. Jeder Zustand beschreibt dabei eine bestimm- te Verteilung der Markierungen in den Stellen. Sowohl Erreichbarkeitsgraph als auch das Petri-Netz beschreiben ein und dasselbe System, jedoch mit verschiede- nen Sichtweisen. Der Erreichbarkeitsgraph wird ebenfalls als Zustandsautomat modelliert. Die Kno- ten zeigen die Belegung aller erreichbaren Markierungen und die Kanten entspre- chen den Transitionsaktionen. In jedem Knoten sind alle Stellen, die aktuell mit einer Markierung versehen aufgelistet. Alternativ kann die Belegung aller Stellen des Systems numerisch (0: nicht belegt; 1: belegt; n: mit n Marken belegt) in jedem Knoten angegeben werden. Um einen Erreichbarkeitsgraphen zu erstellen, wird für jeden Systemzustand ge- prüft, welche Transitionen aktuell schaltbar sind. Für jede schaltbare Transition 2 Deterministisch bedeutet, dass der nachfolgende Zustand eindeutig bestimmt sein muss. Das heißt, eine Menge, aus der ein Zustand zufällig ausgewählt werden kann, darf nicht existieren. 102  1. t1 t2 t3 t4 t5 2. t1 t2 t3 t4 t5 3. t1 t2 t3 t4 t5 Abbildung 4.7: Nicht-Deterministisches Petri-Netz 103 wird der Folgezustand als Knoten in den Graphen eingetragen. Existiert die re- sultierende Markenverteilung bereits als Knoten im Graphen, so wird eine Kante von dem Ausgangszustands-Knoten zu dem Folgezustands-Knoten gezogen. Eine wichtige Fragestellung, die durch Erreichbarkeitsgraphen anschaulich ge- zeigt werden kann, ist, ob von einer bestimmten Markierung M eine andere Mar- kierung M‘ erreicht werden kann. Sprich: Ist es möglich von dem jetzigen Sy- stemzustand M den Zustand M′ zu erreichen? Sollte ein Pfad von M0 über die Transitionen t1 , t2 ,... , tn zu Mn in dem Petri- Netz existieren, ist Mn von M0 aus erreichbar. Die dafür notwendige Sequenz von Transitionen heißt auch: Von M0 aktivierte endliche Schaltfolge. Diese Schalt- sequenz kann auch als ρ (Menge aller Transitionen t1 bis tn ) zusammengefasst werden. Sollte Mn nicht von M0 aus erreichbar sein, existiert in dem Erreichbar- keitsgraphen kein Pfad von M0 nach Mn. Die Mathematische Definition wirkt auf den ersten Blick komplizierter, sagt aber das selbe aus: Definition: Erreichbarkeit Ein Petri-Netz mit einer Anfangsmarkierung M0 sei gegeben. Eine endliche Se- quenz ρ = t1 , t2 ,... , tn mit ti ∈ T für alle i, 1 ≤ i ≤ n ist die von M aktivierte endliche Schaltfolge, wenn Markierungen M1 , M2 ,... , Mn existieren mit 1t 2 t n t ρ M0 − → M1 − →... − → Mn , also M0 − → Mn. M′ ist von M aus erreichbar, wenn es eine Sequenz gibt, die von M in den End- zustand M′ führt. Beispiel: Bahnnetz Das Petri-Netz (vgl. Bild 4.8) zeigt die vier Städte t1 -t4 , die durch einseitig befahr- bare Gleise s1 -s4 erreichbar sind. Die Stellen k1 -k4 garantieren, dass nur ein Zug auf einmal in der vorgegebenen Richtung auf den Gleisen fahren darf. Die An- fangsmarkierungen liegen an den Stellen s2 , s4 , k1 und k3. Zu Beginn können also nur die beiden Transitionen t2 oder t4 geschaltet wer- den, jede Stelle des Vorbereiches ist mit einer Marke versehen, der entsprechende 104  s1 t4 t1 k1 Zug s4 k4 k2 s2 Zug k3 t3 t2 s3 Abbildung 4.8: Petri-Bahnhof Nachbereich nicht. Eine der beiden Transitionen wird zufällig ausgewählt und ge- schaltet. Danach ist aufgrund der neuen Markenverteilung nur die jeweils andere Transition (t2 bzw. t4 ) schaltfähig. Wenn sowohl t4 als auch t2 geschaltet wurden, sind t3 und t1 schaltfähig. Sobald diese beiden schaltbereiten Transitionen geschal- tet wurden, liegt wieder der Ausgangszustand vor. Der zugehörige Erreichbarkeitsgraph hat den Ausgangszustand M0 im obersten Knoten, die entsprechenden Markierungen sind vermerkt. Der Ausgangszustand entspricht der Markenverteilung des Anfangszustandes des Petri-Netz (vgl. Bild 4.8). Es ist deutlich zu sehen, dass nicht beide Transitionen t2 und t4 gleichzeitig schalten. Je nachdem welche zuerst geschaltet wird sind unterschiedliche Markie- rungen gesetzt und nur die jeweils andere Transition ist schaltfähig. Die beiden verschiedenen Wege führen zu demselben Endzustand, in dem t1 und t3 geschal- tet werden können. Je nach Schaltreihenfolge der Transitionen entstehen unter- schiedliche Zwischenzustände. 105  k1,s2,k3,s4 t2 t4 k1,k2,s3,s4 s1,s2,k3,k4 t3 t1 t4 t2 s1,k2,s3,k4 t1 t3 k1,s2,s3,k4 s1,k2,k3,s4 Abbildung 4.9: Erreichbarkeitsgraph Bahnnetz: «markierte Stellen» 0101 1010 t2 t4 0011 1100 1100 0011 t3 t1 t4 t2 0101 0101 t1 t3 0110 1001 1001 0110 Abbildung 4.10: Erreichbarkeitsgraph Bahnnetz: «alle Stellen» Reihenfolge der Stellen: s1, s2, s3, s4, k1, k2, k3, k4 106 4.4.3 Lebendigkeit Ein Petri-Netz ist lebendig, wenn für alle erreichbaren Zustände z und für alle Transitionen t gilt: Es existiert ein neuer, von z erreichbarer Zustand z′ , in dem t schaltbereit ist. Das heißt: Jede Transition t kann nach endlich vielen Schritten in dem lebendigen Petri-Netz erneut geschaltet werden. t2 nicht lebendig t1 kann nur ein t1 Mal schalten t3 lebendig alle schaltbaren Transitionen können erneut t1 t2 geschalten werden 4.4.4 Verklemmungen Erreichbarkeitsgraphen eignen sich besonders gut, um mögliche Verklemmungen in Systemen zu erkennen. Weil auf einen verklemmten Zustand kein weiterer Zu- stand folgt, bildet der zugehörige Knoten in dem Graphen eine Sackgasse. Entsprechend muss aus jedem nicht verklemmten Zustand mindestens eine Kan- te zu einem weiteren Knoten verlaufen. Beim Modellieren eines Systemes wer- den die verschiedenen Möglichkeiten zur Behebung von Verklemmungen, wie beispielsweise Semaphoren, im zugehörigen Petri-Netz eingefügt. Dabei können zum einen ungültige Zustände verboten werden, indem bestimmte Transitionen, durch das Einfügen neuer Stellen, verhindert werden. Andererseits können wei- tere Zustandsübergänge hinzugefügt werden. Diese können überschüssige Token an der kritischen Stelle vorbei leiten, oder die Anzahl der Token durch Erzeuger und Verbraucher (vgl. ??) regulieren. Dadurch können auch an anderen Stellen im 107 Graphen neue Pfade und Zustände erzeugen. Folglich muss der Erreichbarkeits- graph alle neuen Zustände und Transitionsaktionen erweitert werden. Neben der globalen Verklemmung, die das gesamte System blockiert, sind auch lokale Verklemmungen möglich. Dabei blockiert lediglich ein Teil des Systemes, während andere Teile des Systemes ungehindert weiterschalten können. Der ver- klemmte Teil kann von dem nicht blockierten Teil ohne weitere Maßnahmen (vgl. Kapitel 3) nicht gerettet werden. Lokale Verklemmungen erzeugen Stellen in dem Erreichbarkeitsgraphen, die, nach der Verklemmung, nicht mehr geändert wer- den. In jedem folgenden Zustand ist deren Belegung identisch. Lokale und globa- le Verklemmungen sollten gleichermaßen verhindert werden. t1 t4... t2 t3 Abbildung 4.11: lokale Verklemmung der Transitionen t2 und t3 nachdem t1 ge- schaltet wurde. 4.4.5 Verhungern Verhungern tritt auf, wenn eine transitionsbereite Transition, in einer unendlichen Sequenz, nicht geschaltet wird. Ähnlich wie bei dem Verhungern von Prozes- sen im Scheduler, werden kontinuierlich Transitionen geschaltet. Während aus- schließlich die verhungernde Transition in dem schaltbereiten Zustand verweilt. 4.4.6 Beispiele FIFO-Puffer Es soll ein FIFO-Puffer modelliert werden, in dem maximal drei Werte gespei- chert werden können. Das entsprechende Netz soll verklemmungsfrei und leben- 108 dig sein. «Hinten einfügen» und «vorne entnehmen» sind jeweils Aktionen. Sie werden mit den Transitionen t1 und t2 modelliert. Zwischen den Transitionen muss eine Stelle stehen, die maximal drei Token aufnehmen kann, deren Kapazität ist folglich drei. Der Übergang zwischen Transitionen und Stellen hat dabei die Kapazität 1, da immer nur ein Wert auf einmal weitergegeben werden kann. t1 t2 3 Abbildung 4.12: FIFO-Puffer: erster Ansatz Diese Modellierung beschreibt lediglich einen Puffer, es ist nicht sichergestellt, dass der zuerst eingefügte Wert auch zuerst entnommen wird. Die FIFO-Bedingung kann modelliert werden, indem, statt einer Stelle mit Kapa- zität drei, drei Stellen mit Kapazität eins in Reihe geschaltet werden. Es entsteht ein boolsches Netz und ein weiter vorne stehender Wert muss erst vorrücken, dass ein weiter hinten stehender Wert nachrücken kann. t1 t3 t4 t2 1 1 1 Abbildung 4.13: FIFO-Puffer: zweiter Ansatz Das Netz ist jedoch noch nicht lebendig, denn ohne einen neuen Token in t1 kann diese nicht erneut geschaltet werden. Laut Definition müsste die Transition t1 auch nach einer endlichen Folge von Transitionen geschaltet werden können, auch wenn Transition bereits geschaltet wurde. Die letzte Variante sichert, dass Token in dem Puffer auch eine Position nach hinten verschoben werden können. Ohne dass neue Token hinzugefügt werden, kann, indem Token nach vorne und hinten verschoben werden, jede Transition erneut geschaltet werden. Das Petri-Netz ist lebendig. Die FIFO-Bedingung gilt 109  1 1 1 t1 t3 t4 t2 1 1 1 Abbildung 4.14: FIFO-Puffer: dritter Ansatz weiterhin, keine Markierung könne übersprungen werden, da immer nur eine Transition auf einmal geschaltet werden kann. 110