Bisher haben wir uns ausschließlich für Algorithmenmodelle interessiert, die (zumindest logisch) auf einen einzelnen Ausführungsprozessor zugeschnitten sind. Unsere abstrakten Maschinen stellen ja genau so einen Prozessor dar.
Von einzelnen Prozessoren zu Mehrprozessorsystemen
In der Realität sind aber Mehrprozessorsysteme oder Mehrkernsysteme (engl. Multicore-Systeme) bereits jetzt eine verbreitete Rechnerarchitektur und ihre Bedeutung wird sicherlich weiter zunehmen. Der Übergang von klassischen Algorithmen zu auf mehreren Prozessoren ablaufenden Prozessen ist durchaus anspruchsvoll und würde den Rahmen dieses Buches sprengen. Wir müssen das Thema als Ganzes also weiterführenden Büchern überlassen. Dennoch werden wir versuchen, an dieser Stelle einige Grundprinzipien zu vermitteln, da parallele und verteilte Berechnungen in vielen Anwendungsgebieten den Alltag der Programmierung bestimmen.
In einem ersten Abschnitt werden wir grundlegende Begriffe der parallelen und verteilten Programmierung einführen und dabei auch auf kommunizierende Prozesse als Ausführungsmodell für verteilte Berechnungen eingehen. Einzelne Prozesse können dabei als eine Menge von klassischen Einprozessorprogrammen aufgefasst werden, die durch Kommunikation synchronisiert werden. Trotz dieser Verwandschaft zu klassischen Algorithmen werden wir im folgenden Abschnitt mit den Petri-Netzen einen Beschreibungsformalismus kennen lernen, der verteilte Abläufe als Ganzes zu beschreiben erlaubt.
Abschließend werden wir an einem Beispiel Programmierkonzepte erläutern, die die Programmierung paralleler und verteilter Abläufe in einer üblichen Programmiersprache ermöglichen.
Nebenläufigkeit
Bisher haben wir mit den Algorithmenmodellen immer eine Sequenz von Ausführungsschritten als Berechnung betrachtet. Moderne Computer sind jedoch meist mit mehreren Prozessoren oder Prozessorkernen (Multicore) ausgestattet und können daher mehrere Prozesse gleichzeitig ausführen. Um diese Hardware auch zur Beschleunigung einzelner Programme ausnutzen zu können, müssen diese nebenläufig programmiert werden. Dies bedeutet, dass die Berechnung in Teilaufgaben zerlegt wird, die gleichzeitig – also nebenläufig – von verschiedenen Prozessoren bzw. Prozessorkernen ausgeführt werden. Man spricht dabei von
Prozess
Weiterhin unterscheidet man auf Betriebssystemebene zwischen Prozessen und Threads. Ein Prozess ist ein Programm in Ausführung: Jeder Prozess hat einen eigenen Adressraum und ein Prozessor kann immer nur einen Prozess ausführen. Ein Beispiel hierfür ist die Ausführung eines Java-Programms – das Betriebssystem startet dazu einen eigenen Prozess mit der Java-VM.
Thread
Ein Thread (»Faden«) ist dagegen eine leichtgewichtige Ausführungseinheit oder Folge von Anweisungen innerhalb eines sich in Ausführung befindlichen Programms – also eines Prozesses. »Leichtgewichtig« bezieht sich dabei auf den Aufwand zum Start und zur Verwaltung im Vergleich zu einem Betriebssystemprozess. Ein Thread kann ebenfalls von einem Prozessor oder Prozessorkern ausgeführt werden. Die Besonderheit ist jedoch, dass sich die Threads eines Prozesses den Adressraum teilen, d.h., sie können auf die gleichen Speicherbereiche bzw. Daten zugreifen.
Shared Memory
Daraus ergeben sich zwei grundsätzliche Arten der Kommunikation zwischen Prozessen bzw. Threads. Beim gemeinsamen Speicher (engl. Shared Memory) kommunizieren die Prozesse bzw. Threads über Variablen im gemeinsamen Speicher. Ein Prozess kann direkt auf den Speicher eines anderen Prozesses zugreifen. Dies erfordert allerdings eine explizite Synchronisation dieser Zugriffe, z.B. über sogenannte kritische Abschnitte. Abbildung 9–1(a) zeigt dieses Prinzip: Der Produzent ändert den Wert der gemeinsamen Variablen x auf 42. Der zweite Prozess – der Konsument – wartet, bis das Flag gesetzt ist, und liest dann die Variable x aus.
Message Passing
Das Modell des Nachrichtenaustausches (engl. Message Passing) kommt bei Prozessen mit getrennten Adressräumen zum Einsatz, wenn jeder Prozess nur Zugriff auf den eigenen Speicher hat. Die Kommunikation erfolgt dann durch explizites Senden bzw. Empfangen von Nachrichten. Die Synchronisation geschieht dabei implizit durch Nachrichten. In Abbildung 9–1(b) ist dies durch den Aufruf der send- bzw. receive-Funktionen illustriert.
Abb. 9–1 Shared Memory vs. Message Passing
Kommunizierende Prozesse
Message Passing ist eine Anwendung des Konzeptes der kommunizierender Prozesse. Hierbei entspricht jeder einzelne Prozess einer Ausführungssequenz, wobei die Schritte mehrerer Prozesse prinzipiell unabhängig sind. Insbesondere ist die zeitliche Reihenfolge von Schritten aus verschiedenen Prozessen oft nicht bestimmt. Daher wird eine Synchronisation durch Kommunikation notwendig.
Weiterhin lassen sich verschiedene Arten der Parallelität unterscheiden:
Die Herausforderungen bei der Entwicklung solcher parallelen bzw. verteilten Programme bestehen nun darin, zum einen das Problem überhaupt in parallel verarbeitbare Teile zu zerlegen und zum anderen, konkurrierende Zugriffe auf gemeinsame Ressourcen in geeigneter Weise zu synchronisieren und dafür das passende Modell auszuwählen.
Petri-Netze
Bevor wir uns der Programmierung verteilter Systeme zuwenden, betrachten wir ein abstraktes Modell zur Beschreibung nebenläufiger Abläufe, das bereits 1962 von C. A. Petri vorgeschlagen wurde und als Modell der Petri-Netz bekannt ist. Petri-Netze bilden ein Modell zur Beschreibung von Abläufen mit nebenläufigen und nichtdeterministischen Vorgängen. Vorgänge sind dabei echt nebenläufig, wenn ihre zeitliche Anordnung nicht bestimmbar ist.
Petri-Netze werden für die ersten Entwurfsphasen allgemeiner verteilter Systeme eingesetzt. Neben der Entwicklung von Software werden sie unter anderem auch für die Beschreibung von Workflows (Arbeitsabläufen), logistischen Systemen und hardwarenaher Abläufe eingesetzt.
Ein Petri-Netz ist ein gerichteter Graph, aufgebaut aus folgenden Bestandteilen:
Transitionen
Ein- und Ausgabekanten
Markierungen
Für die Darstellung von Petri-Netzen ist die bereits erläuterte grafische Notation verbreitet, auch wenn die Darstellung in einer speziellen textuellen Spezifikationssprache für Netze natürlich auch möglich wäre. Abbildung 9–2 zeigt ein Beispielnetz ohne Markierungen, das ein Produzenten-Verbraucher-System mit einem Puffer der Größe 1 modelliert.
Abb. 9–2 Petri-Netz für Produzenten-Verbraucher-System
Das Petri-Netz in Abbildung 9–2 beschreibt mit den Transitionen produce und deliver einen Produzenten, der Teile produziert und ausliefert. Die Transitionen remove und consume sind die Gegenstücke eines Verbrauchers. Die Stellen buffer empty und buffer filled modellieren den Puffer des Systems. Die anderen vier Stellen modellieren die internen Zustände von Produzent und Verbraucher.
Abbildung 9–3 zeigt nun einen initialen Zustand des Systems, definiert durch eine Markierung. Jeweils eine Marke in Abbildung 9–3 definiert den internen Zustand von Produzent und Verbraucher – ein Produzent kann als Nächstes entweder produzieren oder ausliefern. Die dritte Marke gibt den Zustand des Puffers (voll oder leer) an.
Schalten einer Transition
In Abbildung 9–4 wird nun das Ergebnis des Schaltens einer Transition gezeigt. Das Schalten wird auch bildlich als »Feuern« bezeichnet. Das Feuern der Transition produce entfernt eine Marke in der Stelle ready to produce und legt dafür eine Marke an der Stelle ready to deliver ab.
Abb. 9–3 Petri-Netz mit Marken
Abb. 9–4 Petri-Netz nach Feuern von produce
Abbildung 9–5 zeigt nun mit dem Feuern von deliver eine Transition, die zwei Marken entfernt und auch zwei Marken ablegt.
Abb. 9–5 Petri-Netz nach Feuern von deliver
Das Feuern von Transitionen mit dem Entfernen und Setzen von Marken, die auch Token genannt werden, wird oft als Token-Game bezeichnet, da es ähnlich dem Setzen von Spielfiguren abläuft.
Wir haben die Bestandteile eines Petri-Netzes noch nicht genauer formalisiert. Ein Grund dafür ist, dass es mehrere Arten von Petri-Netzen gibt, die sich in den Einzelheiten unterscheiden:
Bedingungs-Ereignis-Netz
Der Übergang von Bedingungs-Ereignis-Netzen zu Stellen-Transitions-Netzen soll nun an einem Beispiel verdeutlicht werden.
Abbildung 9–6 zeigt ein Produzenten-Verbraucher-System mit der Puffergröße 2, modelliert als Bedingungs-Ereignis-Netz. Der Puffer wird durch zwei Teilpuffer der Größe 1 gebildet. Man kann sich leicht verdeutlichen, dass bei wachsender Puffergröße das Netz unhandlich wird.
Abb. 9–6 Produzenten-Verbraucher-System mit Puffergröße 2 als Bedingungs-Ereignis-Netz
Abbildung 9–7 zeigt dasselbe System als Stellen-Transitions-Netz. Die Puffergröße wird durch die Anfangsmarkierung mit zwei Marken modelliert.
Abb. 9–7 Stellen-Transitions-Netz für Puffergröße 2
Kapazitäten
Noch einfacher wird das Netz, wenn wie in Abbildung 9–8 Kapazitäten genutzt werden.
Wir werden im Folgenden Stellen-Transitions-Netze meinen, wenn wir den Begriff Petri-Netz verwenden, sofern wir nicht explizit eine andere Variante nennen.
Schaltregel
Nach der Einführung von Stellen-Transitions-Netzen können wir nun die Schaltregel, die das »Token-Game« beschreibt, genauer festlegen:
Abb. 9–8 Stellen-Transitions-Netz mit Kapazität
Bei Stellen mit Kapazitäten darf das Hinzufügen von Marken nicht die Kapazitätsbegrenzung verletzen. Zur Vereinfachung kann man auch in nahe liegender Weise eine Erweiterung um gewichtete Kanten vornehmen, bei der eine Kante in einem Schritt mehrere Marken entnehmen oder hinterlegen kann.
Ein Petri-Netz (genauer ein Stellen-Transitions-Netz) kann als Fünf-Tupel
P = (S, T, A, E, M)
Formalisierung von Petri-Netzen
formalisiert werden, wobei die einzelnen Bestandteile die folgende Bedeutung haben:
0 bezeichnen wir die Startmarkierung.Flussrelation
Es sei darauf hingewiesen, dass in einigen Lehrbüchern eine Flussrelation F = A ∪ E statt der separaten A und E eingeführt wird. Dies ist mathematisch natürlich äquivalent.
Diese eher trockene Formalisierung können wir gut an einem Beispiel erläutern. Die eingeführten Mengen werden wie folgt festgelegt:
S = {s1, s2, s3, s4, s5}
T = {t1, t2, t3, t4}
A = {(s1, t1), (s2, t2), (s3, t1), (s3, t3), (s4, t4), (s5, t3)}
E = {(t1, s2), (t2, s1), (t2, s3), (t3, s4), (t4, s3), (t4, s5)}
M(s1) = M(s3) = 1,M(s5) = 2,M(s2) = M(s4) = 0
Gegenseitiger Ausschluss zweier Prozesse
Das Beispiel modelliert den gegenseitigen Ausschluss zweier Prozesse: Die beiden Stellen s2 und s4 können nie gleichzeitig belegt sein. Die zweite Marke in s5 ist dabei nur aus Demonstrationszwecken eingeführt worden. Das modellierte Petri-Netz ist grafisch in Abbildung 9–9 dargestellt.
Abb. 9–9 Grafische Darstellung des formal beschriebenen Petri-Netzes P
Formalisierung der Schaltregel
Basierend auf der Formalisierung des Netzes können wir nun auch die Schaltregel exakt festlegen. Dazu definieren wir mit
•t = {s ∊ S|(s, t) ∊ A}
den Vorbereich einer Transition und mit
t• = {s ∊ S|(t, s) ∊ E}
den Nachbereich einer Transition.
Die formalisierte Schaltregel lautet nun formal beschrieben für zwei aufeinander folgende Markierungen M(s) und M′(s) und eine feuernde Transition t wie folgt:
Abschließend zeigen wir in Abbildung 9–10 den Bezug von Petri-Netz-Konstrukten zu typischen Kontrollstrukturen und beschreiben dabei gleichzeitig einige typische Entwurfsmuster bei der Modellierung mit Petri-Netzen.
Abb. 9–10 Modellierungsprimitive für Petri-Netze
Die fünf dinierenden Philosophen ist ein bekanntes Beispiel, um synchronisierte Prozesse und deren mögliche Blockierung durch gemeinsam benutzte Ressourcen zu modellieren. Wir werden dieses Beispiel zuerst mit Petri-Netzen modellieren und später auch dessen programmtechnische Umsetzung vorstellen.
Fünf dinierende Philosophen
Im Beispiel sitzen fünf Philosophen an einem runden Tisch. In der Mitte befindet sich eine Schüssel Spaghetti (oder ein anderes nicht so einfach zu portionierendes Gericht). Auf dem Tisch liegen fünf Gabeln, je eine zwischen zwei Philosophen. Ein Philosoph kann nur mit zwei Gabeln essen und er kann nur die ihm benachbarten Gabeln aufnehmen.
Jeder Philosoph durchläuft einen Zyklus von Zuständen: denken → hungrig → essen → denken etc. Dieses Beispiel ist für einen einzelnen Philosophen in Abbildung 9–11 als Petri-Netz modelliert.
Die drei aufeinander folgenden Zustände des Philosophen sind als Zyklus von drei Stellen modelliert. Ein Philosoph kann nur in den Zustand essen wechseln, wenn er bei der Transition start gleichzeitig beide Gabeln aufnimmt. Er legt diese Gabeln nach dem essen wieder zurück.
Abbildung 9–12 skizziert das Gesamtnetz, in dem jeweils zwei Philosophen sich eine Gabel-Stelle teilen. Somit kann ein Philosoph nur mit essen beginnen, wenn nicht gerade beide Nachbarn am Essen sind.
Die bisherige Modellierung stellt eine eher abstrakte Modellierung des Problems dar, insbesondere da beide Gabeln gleichzeitig aufgenommen werden. In einem verteilten System ist die Realisierung einer absoluten Gleichzeitigkeit für den Zugriff auf unterschiedliche Ressourcen nicht möglich, so dass an dieser Stelle die Modellierung verfeinert werden muss.
Abb. 9–11 Philosophenproblem als Petri-Netz: Ein Philosoph
Abb. 9–12 Stellen aller 5 Philosophen
Als Lösung müssen die Gabeln nacheinander aufgenommen werden, wie es in Abbildung 9–13 modelliert ist.
Möglichkeit der Verklemmung
Die neue Modellierung weist aber nun ein Problem auf, das für verteilte Systeme typisch ist – es besteht die Möglichkeit einer Verklemmung, englisch als Deadlock bezeichnet. Eine Verklemmung tritt in unserem Beispiel dann auf, wenn alle Philosophen die linke Gabel aufgenommen haben. Jeder Philosoph wartet nun darauf, auch seine rechte Gabel aufnehmen zu können, die sich allerdings in der Hand des jeweiligen rechten Nachbarn befindet (als dessen linke Gabel). Gabeln können erst wieder nach dem Essen zurückgelegt werden – das System steht, da keine Transition mehr möglich ist (und die Philosophen jämmerlich verhungern).
Abb. 9–13 Fünf Philosophen mit Verklemmungsmöglichkeit
Die Entdeckung von Verklemmungsmöglichkeiten und die Vorkehrungen, um diese zu vermeiden oder aufzulösen, sind ein wichtiger Bestandteil des Entwurfs von verteilten Systemen. Wir werden in den folgenden Abschnitten darauf erneut eingehen.
Im letzten Abschnitt haben wir mit den Petri-Netzen einen Formalismus zur Modellierung von verteilten Abläufen kennen gelernt. Dieser Abschnitt beschäftigt sich nun mit den Konzepten der Programmierung derartiger Systeme, bevor wir im letzten Abschnitt auf die Realisierung in Java eingehen.
Mehrprozess-Systeme
Ein System aus nebenläufigen Prozessen besteht im Prinzip aus mehreren kommunizierenden Automaten, die z.B über Betriebssystemfunktionen koordiniert werden. Wichtige Programmierkonzepte für kommunizierende Programme wurden ursprünglich nicht für echt verteilte Systeme entwickelt, sondern für Mehrprozess-Systeme, in denen mehrere Prozesse quasi gleichzeitig ablaufen, indem sie zyklisch eine »Zeitscheibe« von einem Prozessverwalter zugeteilt bekommen und in dieser Zeitscheibe wie ein normales Programm arbeiten. Ein derartiges Modell kann nicht durch direkte Kommunikation synchronisiert werden (es ist ja immer nur ein einziger Prozess zu jedem Zeitpunkt tatsächlich aktiv). Stattdessen erfolgt die Kommunikation durch den Zugriff auf gemeinsame (»shared«) Ressourcen.
In einem solchen System durchlaufen Prozesse bestimmte Zustände, die in Abbildung 9–14 dargestellt sind.
Abb. 9–14 Zustände von Prozessen
Zustandsänderungen von Prozessen
Ein Prozess wird zuerst initiiert und wechselt dann in den Zustand bereit. Durch den Prozessverwalter wird er aktiviert und nach Ablauf der Zeitscheibe wieder in den wartenden Zustand bereit versetzt. Während des aktiven Arbeitens kann es passieren, dass der Prozess auf eine gemeinsame Ressource zugreifen möchte, die von einem anderen Prozess bereits gesperrt wurde (man erinnere sich an den Philosophen, der auf die frei werdende Gabel wartet). In diesem Fall wird der Prozess blockiert, bis der Prozessverwalter das Freiwerden der Ressource registriert und den Prozess wieder in den Zustand bereit versetzt (er kann nicht einfach aktiviert werden, da mehrere Prozesse auf dieselbe Ressource warten können). Wie ein übliches Programm kann ein Prozess schlussendlich terminieren.
Wir werden nun mit dem Konzept der Semaphoren ein Programmkonstrukt kennen lernen, das die Programmierung kommunizierender Prozesse ermöglicht.
Konzept der Semaphore
Ein Semaphor ist ein spezielles Konstrukt zur Kontrolle des Zugriffes auf gemeinsame Ressourcen. Es wurde ursprünglich von Dijkstra vorgeschlagen und basiert auf einer ganzzahligen Variablen und einer Warteschlange von Prozessen.
Warteschlange von Prozessen
Eine Warteschlange ist ein Datentyp, den wir später in diesem Buch noch ausführlich diskutieren werden. An dieser Stelle sei nur erwähnt, dass eine Warteschlange wie eine Schlange an einer Supermarktkasse funktioniert: Neu angekommene Prozesse stellen sich »hinten an«, es wird jeweils der ganz vorne in der Schlange stehende Prozess bearbeitet (und nach Bearbeitung aus der Schlange entfernt).
Operationen auf Semaphoren
Neben der Initialisierung kennt ein Semaphor zwei Operationen. Diese Operationen sind atomar, d.h. unteilbar:
In der Programmierung wird sie als Warteoperation am Beginn eines kritischen Abschnitts eingesetzt.
Programmtechnisch ist up eine Signaloperation, die das Verlassen eines kritischen Abschnitts an andere Prozesse signalisiert.
Realisierung des Datentyps Semaphor
Wir geben nun die Realisierung eines Datentyps Semaphor in einer programmiersprachennahen Pseudocode-Notation an:
type semaphor = 0..maxint;
procedure down (var s: semaphor);
begin
if s ≥ 1
then s := s − 1
else
Blockiere den ausführenden Prozess;
Trage den Prozess in die Warteschlange W(s) ein
fi
end
procedure up (var s : semaphor);
begin
s := s + 1;
if Warteschlange W(s) nicht leer
then
Wähle Prozess Q aus W (s) aus;
Versetze Q in den Zustand »bereit«
fi
end
Den Einsatz von Semaphoren in der Programmierung werden wir nun an einem Erzeuger-Verbraucher-System mit begrenztem Puffer demonstrieren, das mittels Semaphore programmiert werden soll.
Semaphore für Erzeuger-Verbraucher-System
Wir beginnen mit der Festlegung der Variablen: drei Semaphore. Interessant ist an diesem Beispiel, dass neben der Sicherung der kritischen Bereiche auch die Größenbegrenzung des Puffers mittels Semaphore realisiert wird.
var nichtvoll, /* Puffer ist nicht voll */
nichtleer, /* Puffer ist nicht leer */
gesperrt /* Puffer ist gesperrt */
: semaphor;
nichtvoll := n ; /* Puffer mit n Plätzen */
nichtleer := 0;
gesperrt := 1
Um das Arbeiten des Systems und insbesondere die Rolle der beiden Variablen nichtvoll und nichtleer zu verdeutlichen, ist in Abbildung 9–15 das Erzeuger-Verbraucher-System als Petri-Netz modelliert.
Abb. 9–15 Erzeuger-Verbraucher-System als Petri-Netz
Die Variable nichtvoll begrenzt die leeren Pufferplätze auf den initial vorgegebenen Wert n, während nichtleer die jeweils aktuell gelagerten Marken repräsentiert.
Der Erzeuger-Prozess versucht in einer Endlosschleife Marken in den Puffer zu bewegen:
repeat
Erzeuge Marke;
down (nichtvoll);
down (gesperrt);
Transportiere Marke in Puffer;
up (gesperrt);
up (nichtleer);
until false
Synchronisation des Ressourcenzugriffs
Der Markentransport ist dabei durch zwei Mechanismen geschützt: Der Test, bei dem die Variable nichtvoll überprüft, ob der Puffer nicht voll ist. Der Prozess kann erst wieder durch die up-Operation des Verbrauchers aktiviert werden. Der innere Semaphorenzugriff übernimmt die eigentliche Synchronisation des Zugriffs auf die gemeinsame Ressource und verhindert damit, dass Erzeuger und Verbraucher gleichzeitig auf den Puffer zugreifen.
Realisierung des Verbrauchers
Der Verbraucher-Prozess ist analog aufgebaut, nur dass der Test mit dem äußeren Semaphorenzugriff jetzt prüft, ob sich eine Marke im Puffer befindet.
repeat
down (nichtleer);
down (gesperrt);
Entnehme Marke dem Puffer;
up (gesperrt);
up (nichtvoll);
Verbrauche Marke;
until false
Man beachte, dass mit up(nichtvoll) ein eventuell wartender Erzeuger geweckt wird, der aufgrund eines vollen Puffers blockiert wurde.
Varianten einer Realisierung mit Semaphoren
Als etwas größeres Beispiel betrachten wir wieder das Problem der fünf dinierenden Philosophen, das mit Semaphoren zu realisieren ist. Dabei sind mehrere Varianten vorstellbar:
Diese Variante, die wir als zweite Realisierung vorstellen werden, erlaubt mehr Nebenläufigkeit als die zweite Variante, ohne dass es zu Verklemmungen kommen kann.
Philosoph in Pseudocode-Notation
Wir beginnen mit einer kurzen Diskussion der Variante 1. Der Philosoph i kann in Pseudocode-Notation ohne Einsatz von Semaphoren wie folgt beschrieben werden:
repeat
denken;
hungrig werden;
nimm Gabel i;
nimm Gabel (i + 1) mod 5;
essen;
lege Gabel i zurück;
lege Gabel (i + 1) mod 5 zurück
until false
Philosoph mit Semaphoren
Eine Umsetzung des Philosophen i mit Semaphoren kann nun nahe liegend wie folgt realisiert werden:
repeat
denken;
hungrig werden;
down (gi);
down (gi+1)%5);
essen;
up (gi);
up (g(i+1)%5)
until false
Wie erwähnt sind in dieser Variante Verklemmungen möglich.
Die Realisierung einer verklemmungsfreien Variante des Philosophenproblems mit maximaler Nebenläufigkeit ist bereits eine etwas anspruchsvollere Aufgabe. Gegeben sind N Philosophenprozesse sowie ein Semaphor ausschluss zum Synchronisieren der Gabelaufnahme.
Wir verwenden eine Prozedur prüfe, die testet, ob mindestens einer der beiden Nachbarn isst; falls nicht, aktiviert sie den Philosoph für die Essensphase. Wir benötigen zusätzlich je Philosoph einen Semaphor phil, um die Blockade und das Aktivieren von Philosophen zu realisieren. Ein Philosoph aktiviert dabei (wenn möglich) beide Nachbarn, sobald er fertig gegessen hat.
Variablen der Realisierung
Zusammengefasst benötigen wir die folgenden Variablen für die Realisierung:
var zustand : array [0..N-1] int;
/* denkend, hungrig, essend */
ausschluss : semaphor;
/* Synchronisation aller Philosophen */
phil : Array [0..N-1] semaphor;
/* Blockade eines Philosophen */
Der Semaphor ausschluss wird mit dem Wert 1 belegt, die Semaphore phil[i] (i = 0… N − 1) erhalten den initialen Wert 0.
Realisierung der Philosophenprozesse
Die Realisierung erfolgt wieder durch eine Endlosschleife:
procedure philosoph (var i : int);
begin
while true do
denke ();
nimmGabeln (i);
esse ();
legeGabeln (i);
od
end
Realisierung der Gabelaufnahme
Das Aufnehmen der Gabeln benutzt den Semaphor ausschluss, um den Zugriff zu realisieren.
procedure nimmGabeln (var i : int);
begin
down ( ausschluss );
zustand[i] = hungrig;
prüfe (i);
up ( ausschluss );
down ( phil[i] );
/* Blockiere falls Gabeln nicht frei */
end
Im Schutz der Semaphore wird die Prüfung mittels der Prozedur prüfe durchgeführt:
procedure prüfe (var i : int);
begin
if zustand[i] = hungrig and
zustand[(i − 1) mod 5] ≠ essend and
zustand[(i + 1) mod 5] ≠ essend then
zustand[i] = essend;
up ( phil[i] );
fi
/* aktiviert bei Blockade! */
end
Beim Ablauf von prüfe innerhalb von nimmGabeln gibt es zwei Varianten:
Realisierung des Gabelzurücklegens
Die Prozedur legeGabeln legt die Gabeln – wieder im Schutz des Semaphors ausschluss – nieder und testet dabei die beiden Nachbarn, ob sie aktiviert werden können. Auch dieser Test kann mit der Prozedur prüfe erfolgen.
procedure legeGabeln (var i : int);
begin
down ( ausschluss );
zustand[i] = denkend;
prüfe ( (i − 1) mod N ); /* aktiviere ggf. Nachbarn */
prüfe ( (i + 1) mod N ); /*aktiviere ggf. Nachbarn */
up ( ausschluss );
end
Diese Realisierung ist bereits etwas trickreich (durch die doppelte Verwendung der Prozedur prüfe sowie die explizite Aktivierung der Nachbarn).
Programmiersprachen bieten sehr verschiedene Mechanismen zur Unterstützung der Programmierung nebenläufiger Berechnungen. Wir wollen im Folgenden nur einen kurzen Überblick über die wichtigsten Elemente in Java geben, um Aufgaben wie das zuvor beschriebene Philosophenproblem lösen zu können.
Thread
Java bietet eine direkte Unterstützung von Threads. Diese werden in Java durch eine spezielle Klasse java.lang.Thread repräsentiert, die im Wesentlichen folgende Methoden definiert:
Grundsätzlich existieren zwei Möglichkeiten, die Thread-Klasse zu nutzen, um einen eigenen Kontrollfluss zu implementieren:
Betrachten wir dazu eine einfache Klasse Heartbeat, die einen regelmäßigen Herzschlag »simuliert«, indem periodisch eine Ausgabe erfolgt. Programm 9.1 zeigt die erste Variante der Implementierung als direkte Thread-Subklasse.
public class Heartbeat1 extends Thread {
int pulse = 1000;
public Heartbeat1(int p) { setPulse(p); }
public void setPulse(int p) { pulse = p * 1000; }
public void run() {
while(true) {
try {
Thread.sleep(pulse);
}
catch(InterruptedException e) {}
System.out.println("poch");
}
}
public static void main(String[ ] args) {
Heartbeat1 t = new Heartbeat1(2);
t.start();
}
}
In der main-Methode kann dann einfach der Konstruktor der Klasse Heartbeat1 aufgerufen werden.
Die zweite Variante über die Runnable-Schnittstelle ist in Programm 9.2 dargestellt. Bei der Erzeugung des Objektes ist zu berücksichtigen, dass Heartbeat2 kein Thread-Objekt ist. Deshalb muss in der main-Methode der Thread-Konstruktor explizit aufgerufen werden.
public class Heartbeat2 implements Runnable {
int pulse;
public Heartbeat2(int p) { pulse = p * 1000; }
public void run() {
while(true) {
try {
Thread.sleep(pulse);
}
catch(InterruptedException e) {}
System.out.println("poch");
}
}
public static void main(String[ ] args) {
Thread t = new Thread(new Heartbeat2(2));
t.start();
}
}
Semaphor Kritischer Abschnitt
Da die Threads in einem Java-Programm im gleichen Adressraum laufen, können sie problemlos auf die gleichen Variablen zugreifen. Dies erfordert – zumindest für schreibende Zugriffe – jedoch eine Synchronisation der Zugriffe. Das im vorigen Abschnitt vorgestellte Konzept der Semaphoren existiert in dieser Form nicht in Java, allerdings gibt es die Möglichkeit, kritische Programmabschnitte vor dem simultanen Zugriff mehrerer Threads zu schützen. Hierzu wird die synchronized-Anweisung mit folgender Notation verwendet:
synchronized (ausdruck) anweisung
Sperre
Der Ausdruck ausdruck muss dabei ein Objekt liefern. Für dieses Objekt wird eine Sperre gesetzt, die den exklusiven Zugriff sichert. Anschließend wird die Anweisung bzw. der Anweisungsblock anweisung ausgeführt und nach der Abarbeitung die Sperre wieder freigegeben. Da zu jeder Zeit nur ein Thread eine Sperre auf einem Objekt halten kann, wird anweisung als kritischer Abschnitt geschützt.
Programm 9.3 zeigt den Einsatz der synchronized-Anweisung. Die Klasse Producer füllt in einem Thread ein int-Feld mit Zufallswerten, die Klasse Consumer versucht im zweiten Thread, diese Werte auszulesen. Da das Feld initial mit 0 belegt ist, muss Consumer nur prüfen, ob das aktuell zu lesende Feldelement ≠ 0 ist.
class Producer implements Runnable {
int[ ] buf;
Producer(int[ ] b) { buf = b; }
public void run() {
for (int i = 0; i < 10; i++) {
int v = (int)(Math.random() * 100) + 1;
System.out.println("--> " + v);
synchronized(buf) {
buf[i] = v;
}
try { Thread.sleep(100); } catch(InterruptedException e) {}
}
}
}
class Consumer implements Runnable {
int[ ] buf;
Consumer(int[ ] b) { buf = b; }
public void run() {
int n = 0;
while (n < 10) {
synchronized(buf) {
if (buf[n] != 0) {
System.out.println("<-- " + buf[n]);
n++;
}
}
try { Thread.sleep(50); } catch(InterruptedException e) {}
}
}
}
Da beide Threads auf das gleiche Objekt zugreifen, das dem Konstruktor als Parameter übergeben wird, muss der Zugriff auf das Feld buf synchronisiert werden.
Die beiden Threads können dann wie folgt gestartet werden – buffer ist hierbei das gemeinsam genutzte Feld:
int[] buffer = new int[10];
Thread t1 = new Thread(new Producer(buffer));
Thread t2 = new Thread(new Consumer(buffer));
t1.start();
t2.start();
synchronized-Methoden
Neben der hier beschriebenen Verwendung von synchronized zur Realisierung kritischer Abschnitte können auch komplette Methoden als synchronized deklariert werden. In diesem Fall darf nur ein Thread diese Methode auf einem Objekt zur gleichen Zeit ausführen.
Threads bilden in Java die Basis für die Parallelisierung von Berechnungen und können sowohl zur Realisierung von Taskparallelität als auch von Datenparallelität genutzt werden. Programm 9.3 aus dem vorigen Abschnitt ist ein Beispiel für Taskparallelität: Producer und Consumer führen verschiedene Aufgaben durch, laufen aber gleichzeitig ab.
Als Beispiel für Datenparallelität wollen wir uns die Berechnung einer Menge von Fibonacci-Zahlen anschauen. Die Berechnung dieser Zahlen haben wir bereits in Abschnitt 3.2.6 eingeführt. Wenn wir nun mehrere Fibonacci-Zahlen berechnen müssen, kann dies auf einfache Weise parallelisiert werden, indem jede Fibonacci-Zahl in einem eigenen Thread berechnet wird. Unser Problem – eine Menge von zu berechnenden Fibonacci-Zahlen – wird also so partitioniert, dass jede Partition aus einer Zahl besteht und einem Thread zugewiesen wird. Programm 9.4 zeigt diese Realisierung. Die Klasse Fibonacci implementiert wieder die Runnable-Schnittstelle, wobei in der run-Methode die eigentliche Berechnungsfunktion fibo aufgerufen wird.
public class Fibonacci implements Runnable {
long fi; // zu berechnende Fibonacci-Zahl
int num; // Nummer des Threads
public Fibonacci(int n, long f) { num = n; fi = f; }
long fibo(long f) {
if (f < 2) return 1;
else return fibo(f −1) + fibo(f −2);
}
public void run() {
System.out.println("Starte #" + num);
long res = fibo(fi);
System.out.println("#" + num + " Fibonacci(" +
fi + ") = " + res);
}
public static void main(String[ ] args) {
Thread[ ] threads = new Thread[10];
for (int i = 0; i < 10; i++)
threads[i] = new Thread(new Fibonacci(i,
(long)(Math.random() * 50) + 1));
for (int i = 0; i < 10; i++)
threads[i].start();
}
}
In der main-Methode wird nun ein Feld für 10 Threads angelegt und die entsprechende Zahl von Fibonacci-Threads wird erzeugt und gestartet. Die Ausgabe des Programms zeigt dann, welcher Thread welche Zahl berechnet hat.
Bereits an diesem sehr einfachen Beispielprogramm lassen sich zwei Herausforderungen bei der Parallelisierung verdeutlichen. Zum einen ist die Art der parallelen Berechnung nicht optimal: Threads, die größere Fibonacci-Zahlen berechnen müssen, haben mehr Arbeit und laufen daher länger als Threads, die kleinere Zahlen berechnen müssen. Die Gesamtlaufzeit wird aber durch den am längsten laufenden Thread bestimmt. So kann es passieren, dass 9 der 10 Threads bereits fertig sind, während der letzte Thread noch rechnen muss. Besser wäre es, wenn Threads, die ihre Arbeit erledigt haben, weitere Berechnungen durchführen könnten. Zum anderen sind auch die Erzeugung von Threads sowie das Umschalten zwischen Threads (sofern die Zahl der Threads größer als die Zahl der Prozessoren bzw. Prozessorkerne ist) mit einem gewissen Aufwand verbunden. Daher sollten nicht zu viele Threads erzeugt werden.
Thread-Pool
Task
Eine Lösung hierfür sind sogenannte Thread-Pools. Hierbei existiert eine feste Zahl von Threads. Die eigentlichen Berechnungsaufgaben (sogenannte Tasks) werden diesen Threads dynamisch zugeordnet, indem die Tasks zunächst in eine Warteschlange eingefügt werden. Immer wenn einer der Threads seine Arbeit erledigt hat, wird ihm der nächste Task aus der Warteschlange zugeordnet. Dieses Prinzip ist auch aus vielen Schnellrestaurants bekannt: Die Kunden repräsentieren hier die Tasks, die von den Angestellten (Threads) bedient werden.
In den neueren Java-Versionen sind im Paket java.util.concurrent eine ganze Reihe von Klassen und Schnittstellen verfügbar, die die Programmierung paralleler Abläufe vereinfachen. Wir wollen an dieser Stelle nur die Schnittstelle ExecutorService kurz vorstellen, welche die Nutzung von Thread-Pools ermöglicht. So kann ein einfacher Pool aus 10 Threads über die Anweisung
ExecutorService executor = Executors.newFixedThreadPool(10);
erzeugt werden. Die auszuführenden Tasks sind einfach Objekte der bekannten Runnable-Schnittstelle. Für das Einfügen der Tasks in die Warteschlange stehen verschiedene Methoden zur Verfügung: Die einfachste Form ist die Methode execute, die genutzt werden kann, wenn keine Ergebnisse der Tasks zurückgegeben werden. Programm 9.5 zeigt eine Modifikation des Programms 9.4 zur Berechnung der Fibonacci-Zahlen, wobei der ExecutorService zum Einsatz kommt.
public class FibonacciPool {
public static void main(String[ ] args) {
ExecutorService executor = Executors.newFixedThreadPool(10);
for (int i = 0; i < 50; i++) {
Runnable task = new Fibonacci(i,
(long)(Math.random() * 50) + 1);
executor.execute(task);
}
executor.shutdown();
}
}
Im Programm werden 50 Fibonacci-Zahlen berechnet. Bei der Ausführung des Programms sieht man, dass zunächst nur 10 Berechnungen sofort gestartet werden und die weiteren erst dann, wenn eine laufende Berechnung abgeschlossen ist.
Future
Neben dieser einfachen Variante eines Thread-Pools stellt das Java-Paket noch weitere Formen zur Verfügung, die zusätzliche Einflussmöglichkeiten bieten. So können auch Tasks implementiert werden, die ihre Ergebnisse über sogenannte Futures zurückgeben. Dabei handelt es sich um Resultate einer asynchronen Berechnung, d.h. einer Berechnung, die erst noch stattfindet und für die ein Platzhalter verwaltet wird. Eine weitere Möglichkeit stellt der ForkJoinPool dar. Hierbei können sich Tasks rekursiv in neue Subtasks aufteilen. Dies ist dann sinnvoll, wenn eine Berechnung (oder die zu verarbeitende Datenmenge) zu groß ist und rekursiv zerlegt werden kann. Die Zerlegung und die damit verbundene Erzeugung neuer Tasks erfolgt dann so lange, bis das Problem klein genug für die direkte Ausführung ist.
Bei der Umsetzung des Philosophenproblems in ein Java-Programm ergibt sich das Problem, dass die Philosophen ja gleichzeitig existieren, d.h. denken und essen. Daher können wir diese Situation nicht einfach mit einem sequenziellen Programm abbilden. Vielmehr müssen wir fünf Ausführungseinheiten parallel ablaufen lassen. Die einfachste Möglichkeit ist die Nutzung von Threads wie oben eingeführt. Grundsätzlich kann dies auch realisiert werden, indem ein Philosophenprogramm fünfmal gestartet wird. Allerdings gestaltet sich dann die Kommunikation schwierig, da hierfür dann spezifische Betriebssystemfunktionen genutzt werden müssen.
Auf Basis der Thread-Klasse kann ein Philosoph als Java-Klasse implementiert werden. Die Grundidee ist in dem noch nicht vollständigen Programm 9.6 dargestellt. Die Klasse Philosopher wird von java.lang.Thread abgeleitet. Als Attribute der Klasse werden leftFork und rightFork eingeführt, die die nutzbaren Gabeln auf dem Tisch bezeichnen. Im Konstruktor wird nach der Belegung dieser Attribute das Leben des Philosophen durch Aufruf der Methode start initiiert. Dieses »Leben« spielt sich ausschließlich in der Methode run ab – daher besteht diese auch aus einer Endlosschleife. Innerhalb der Schleife versucht der Philosoph zunächst die Gabeln aufzunehmen, d.h., die Ausführung blockiert so lange, bis die beiden Gabeln verfügbar sind. Anschließend kann gegessen werden, was durch den Aufruf von sleep mit einer zufälligen Zeitdauer simuliert wird. Da der Thread während der Ausführung von sleep durch einen anderen Thread unterbrochen werden kann, muss dies durch Abfangen der InterruptedException-Ausnahme behandelt werden. Danach werden die Gabeln niedergelegt und das Denken kann wieder durch ein sleep simuliert werden.
class Philosopher extends Thread {
int leftFork, rightFork; // die linke und rechte Gabel
// Konstruktor: initialisiert alle
// Attribute und startet den Thread
public Philosopher(int left, int right) {
leftFork = left;
rightFork = right;
start();
}
// Lebenslauf eines Philosophen
public void run() {
// Anfangszustand: " Denkend "
while (true) {
// Warten, bis beide Gabeln verfügbar sind
// und schließlich aufnehmen
...
// jetzt kann er eine Weile essen
try {
sleep((int) (Math.random () * 3000.0));
} catch (InterruptedException exc) { }
// Gabeln niederlegen
...
// wieder eine Weile nachdenken ...
try {
sleep((int) (Math.random () * 5000.0));
} catch (InterruptedException exc) { }
}
}
}
Bisher haben wir noch offengelassen, wie die Gabeln und insbesondere der koordinierte, verklemmungsfreie Zugriff darauf realisiert werden kann. Eine Gabel lässt sich am einfachsten als eine boolesche Variable darstellen: Ist der Wert true, so ist die Gabel frei, d.h., sie liegt auf dem Tisch, ist der Wert dagegen false, so ist sie belegt. Da fünf Gabeln vorhanden sind, verwalten wir diese als Feldattribut in einer Klasse Forks, die gleichzeitig Methoden zum Aufnehmen (take), Ablegen (put) und Testen auf Verfügbarkeit (isAvailable) anbietet. Alle diese Methoden erwarten als Parameter die Nummer der entsprechenden Gabel (im Bereich 0...4).
class Forks {
// 5 Gabeln: true -> frei, false -> belegt
// Beginn: alle Gabeln sind verfügbar
private boolean forks[ ] = {
true, true, true, true, true
};
// Testet, ob Gabel verfügbar ist
public boolean isAvailable(int f) {
return forks[f];
}
// Aufnehmen der Gabel
void take(int f) {
forks[f] = false;
}
// Ablegen der Gabel
void put(int f) {
forks[f] = true;
}
}
Da die Gabeln von allen Philosophen gemeinsam genutzt werden, ist die Synchronisation des Zugriffs darauf, d.h. auf Objekte der Klasse Forks, über eine synchronized-Anweisung notwendig. Allerdings kann es immer noch passieren, dass zwar der Zugriff auf die Gabeln möglich ist, aber dennoch eine oder sogar beide Gabeln gerade von den Nachbarn benutzt werden. In diesem Fall muss der betroffene Philosophen-Thread warten, bis die Gabeln frei werden. Java bietet zu diesem Zweck im Rahmen der Klasse java.lang.Object die Methoden wait und notify sowie notifyAll, die im Prinzip auch auf Warteschlangen von Threads basieren. Mit wait wird der aktive Thread so lange angehalten, bis er von einem anderen Thread mittels notify bzw. notifyAll aufgeweckt wird. Während des Wartens wird die Sperre des Threads aufgehoben. Erst mit dem Aufwecken wird wieder versucht, die Sperre zu erlangen. Zu beachten ist, dass diese Methoden immer nur in einem kritischen Abschnitt aufgerufen werden können.
Mit diesem Wissen kann nun die Philosophen-Klasse vervollständigt werden (Programm 9.8). Zunächst wird das Forks-Objekt in jedem Thread bekannt gemacht, indem ein entsprechendes Attribut forks hinzugefügt und im Konstruktor initialisiert wird. Zum Aufnehmen der Gabeln wird der betreffende Programmabschnitt durch den exklusiven Zugriff auf das Attribut forks gekapselt. Dort wird zuerst gewartet, bis beide Gabeln verfügbar sind. Hierzu wird in der inneren while-Schleife geprüft, ob eine der beiden Gabeln belegt ist. In diesem Fall wird durch den Aufruf von wait auf das Niederlegen einer Gabel gewartet. Sind schließlich beide Gabeln frei, können sie aufgenommen werden.
class Philosopher extends Thread {
private Forks forks; // Gabeln
int leftFork, rightFork; // die linke und rechte Gabel
// Konstruktor: initialisiert alle
// Attribute und startet den Thread
public Philosopher(Forks f, int left, int right) {
leftFork = left;
rightFork = right;
forks = f;
start();
}
// Lebenslauf eines Philosophen
public void run() {
// Anfangszustand: " Denkend "
while (true) {
// die Gabeln sind geschützt
// Warten, bis beide Gabeln verfügbar sind
while (!forks.isAvailable(leftFork) | |
!forks.isAvailable(rightFork)) {
// Gabeln sind belegt: Zustand ist
// " Hungrig " –> er muss warten
try {
forks.wait();
} catch (InterruptedException exc) { }
}
// beide Gabeln aufnehmen
forks.take(leftFork);
forks.take(rightFork);
}
// jetzt kann er eine Weile essen
try {
sleep((int) (Math.random () * 3000.0));
} catch (InterruptedException exc) { }
// Gabeln sind wieder geschützt
synchronized(forks) {
// Gabeln niederlegen
forks.put(leftFork);
forks.put(rightFork);
// alle wartenden Philosophen aufwecken
forks.notifyAll();
}
// wieder eine Weile nachdenken ...
try {
sleep((int) (Math.random() * 5000.0));
} catch (InterruptedException exc) { }
}
}
}
Das Ablegen der Gabeln ist wiederum als kritischer Abschnitt zu kennzeichnen. Zunächst werden beide Gabeln abgelegt. Anschließend werden dann alle wartenden Philosophen durch den Aufruf von notifyAll geweckt. Die betroffenen Philosophen werden nun versuchen, wieder eine Sperre auf dem forks-Objekt zu setzen. Der erste erfolgreiche Thread prüft dann, ob die Gabeln frei sind und muss gegebenenfalls wieder warten.
Für die Abarbeitung des Philosophenproblems sind nur noch das Forks-Objekt sowie die fünf Philosopher-Threads zu erzeugen (Programm 9.9). Mit dem Aufruf des Konstruktors beginnt gleichzeitig auch das »Leben« der Philosophen.
// Gabeln erzeugen
Forks forks = new Forks();
// 5 Philosophen erzeugen und ihnen ihre
// Gabeln zuweisen
Philosopher[ ] philosophers = new Philosopher[5];
for (int i = 0; i < 5; i++)
philosophers[i] = new Philosopher(forks, i, (i+1) % 5);
Das Schlüsselwort synchronized kann in Java auch als Modifikator im Rahmen einer Methodendefinition eingesetzt werden. Dadurch wird die gesamte Methode zum kritischen Abschnitt: Beim Aufruf der Methode wird für das Objekt eine Sperre gesetzt und beim Verlassen wieder freigegeben, so dass jeweils nur ein Thread zu jeder Zeit diese Methode ausführen kann. Auf dieser Basis kann leicht das Konzept des Semaphors in Form einer Java-Klasse implementiert werden (Programm 9.10).
public class Semaphore {
private int s;
public Semaphore() { s = 1; }
public synchronized void down() {
while (s == 0) {
try {
wait();
} catch (InterruptedException e) {}
}
s = 0;
}
public synchronized void up() {
s = 1;
notify();
}
}
Die Implementierung umfasst im Wesentlichen eine Variable s sowie die Methoden down zum »Herunterzählen« und up zum »Hochzählen« der Variablen, wobei der Semaphor hier nur die Werte 1 für »frei« und 0 für »gesperrt« annehmen kann. Da beide Methoden mit synchronized definiert sind, bilden sie jeweils als Ganzes einen kritischen Abschnitt. Die Verwaltung der Warteschlangen erfolgt durch das Java-Laufzeitsystem: Lediglich das Blockieren (durch wait) und Wiederaufwecken (mittels notify) der Threads muss noch implementiert werden.
Mithilfe der Klasse Semaphore kann das Philosophenproblem in Java nun auch direkt unter Verwendung von Semaphoren implementiert werden. Die Umsetzung der in Abschnitt 9.3.4 beschriebenen Methoden und deren Einbindung in Programm 9.8 sei jedoch dem Leser wieder als Übung überlassen.
