Thread t1 = new Thread(new R1()); ... Thread tn = new Thread(new Rn()); t1.start(); ... tn.start(); t1.join(); ... tn.join();zusammen mit
class Ri implements Runnable { public void run() { Si; } }
Object lock = new Object(); ... synchronized (lock) { S1; ...; Sn; }
/* init */ Object condb = new Object(); /* waiter */ synchronized (condb) { while (! B) condb.wait(); S1; ...; Sn; } /* tester */ // B koennte wahr werden if (B) condb.notify();
Um einschätzen zu können, an welchen Stellen und in welchen Situationen wir synchronisieren müssen, wollen wir uns kurz über die dafür wichtigen Prozessoreigenschaften informieren. Daraus leiten wir dann einige Regeln zur Verwendung von atomic bzw. synchronized ab.
In den meisten registerbasierten CPUs, d.h. in allen modernen Prozessoren, sind die elementaren Maschinenoperationen oft atomar. Auch in interpretierten Programmiersprachen wie Java sind die Operationen mit Datentypen, die im Prozessor per Maschinenbefehl ausgeführt werden, atomar. Genauer werden wir folgende Annahmen machen.
Die obigen Annahmen sind oft bei CPUs mit parallelen Ausführungseinheiten für Berechnungen und Adressdekodierungen nicht erfüllt, aber es ist sichergestellt, daß die obigen Annahmen aus Programmsicht erfüllt sind. Zum Beispiel auf Rechnern mit Cache-Architektur (wie bei fast allen RISC-CPUs) gilt folgendes:
Für die Programmierung von Parallelrechnern ergeben sich somit folgende Regeln:
Bei noch nicht richtig synchronisierten Programmen kann es vorkommen, daß Programmzustände in anderen Prozessen den Zustand in einem Prozeß beeinflussen. Dieses Verhalten nennt man Interferenz. Das Ziel der parallelen Programmierung ist es, diese Beeinflussung zu erkennen, zu vermeiden, beziehungsweise die wechselseitigen Beeinflussungen zu synchronisieren.
Die Möglichkeiten zur Vermeidung von Interferenz sind die folgenden:
atomic end.
await B then S end.
await (h = 1) then S1; h = 2 end; ...Warten bis h=1 ist, dann das Statement S1 ausführen und h auf 2 setzen, damit kann dann await (h=2) ... end terminieren.
await (h = n) then Sn; h = 1 end.
Bevor wir uns im nächsten Kapitel an die Implementierung von parallelen Algorithmen wagen, wollen wir in diesem Abschnitt der Frage nachgehen, ob ein Programm ``richtig'' oder ``korrekt'' ist, d.h. ob ein Programm in jeder Situation genau das tut, was es soll, und ob es die Ergebnisse liefert, die wir erwarten. In kniffeligen Situationen wird man versuchen, die Nachweise für die Korrektheit streng formal durchzuführen, damit nur ja kein entscheidender Fall vergessen wird. Eine Besprechung dieses Formalismus, (genannt axiomatische Semantik) liegt außerhalb der Thematik dieses Buches. Wer sich dafür interessiert, kann dies z.B. in dem Buch von Andrews [And91] finden. Wir geben hier nur eine kurze Einführung in die Konzepte. Dabei führen wir zunächst die nötigen Begriffe ein und besprechen dann die für parallele Programme wichtigen Begriffe genauer. Besonders der letzte Teil ist wegen der Scheduling-Problematik im weiteren wichtig.
Um über die Korrektheit von Programmen zu diskutieren, benutzt man die Begriffe ``Sicherheit'' und ``Lebendigkeit''. Ein Programm ist sicher, falls keine schlechten (fehlerhaften) Zustände eintreten können. Ein Programm ist lebendig, falls irgendwann alle gewünschten Zustände eintreten.
Bei sequentiellen Programmen haben diese Eigenschaften folgende Bedeutung.
Bei parallelen Programmen kommen folgende Bedingungen, die wir im folgenden ausführlicher besprechen, hinzu.
Ein Nachweis für die Korrektheit eines parallelen Programms setzt sich dann zusammen aus den Nachweisen der Korrektheit für die sequentiellen Abschnitte (partielle Korrektheit und Terminierung), aus Beweisen für Interferenz-Freiheit und Deadlock-Freiheit von nebenläufigen Abschnitten sowie Beweisen für die Fairness des benutzten oder implementierten Schedulings.
Bei den formalen Beweisen werden jedem Programmteil zwei Prädikate zugeordnet (Prädikate sind Boolesche Ausdrücke die auch andere mathematische Konstrukte enthalten dürfen). Das erste Prädikat wird als Vorbedingung (Precondition) bezeichnet und beschreibt die Bedingung, die gelten muß, damit der Programmteil sinnvoll ausgeführt werden kann. Und das zweite, als Nachbedingung (Postcondition) bezeichnet, beschreibt die Bedingung, die gilt, nachdem der Programmteil ausgeführt wurde. Eine Bedingung heißt Invariante, wenn sie sowohl vor als auch nach der Ausführung eines Programmteils gilt. Ein Programm ist damit partiell korrekt, falls die Vorbedingung des ersten Programmteils und die Nachbedingung des letzten (ausgeführten) Programmteils die gewünschte Anforderung für das Programm erfüllt und falls die Vorbedingungen aller Programmteile von den Nachbedingungen der vorhergehenden Programmteile erfüllt (impliziert) werden.
Beweise für die Deadlock-Freiheit kann man damit wie folgt konzipieren. Wenn etwa BAD ein Prädikat bezeichnet, das einen Deadlock charakterisiert, so könnte man zeigen, daß
für alle Vorbedingungen Q in allen Programmteilen giltWomit dann bewiesen wäre, daß die Bedingung BAD nicht eintreten kann, das Programm also Deadlock-frei wäre.Q BAD.
Eine andere Technik benutzt eine Invariante I, die in allen Programmteilen gilt, und zeigt
I BAD.Wodurch dann ebenfalls sichergestellt ist, daß BAD nicht eintreten kann.
Ist das nicht möglich, kann eventuell noch durch sogenanntes exclusion of configurations zum Beispiel durch explizites await sichergestellt werden, daß keine Interferenz auftritt.
Bei der Programmeigenschaft Lebendigkeit unterscheiden wir die entsprechenden Eigenschaften des Laufzeitsystems des Computers und den vom Programmierer realisierten Ablauf des gesamten parallelen Programms. Zunächst muß das Laufzeitsystem des Computers natürlich durch die richtige Implementierung von con, atomic und await dafür sorgen, daß kein Programmteil bevorzugt wird und auch die await-Bedingungen genügend oft wahr werden. Aber auch das Programm selbst muß so geschrieben sein, daß nicht durch ungünstige zeitliche Abläufe einige Programmteile nicht ausgeführt werden. In diesem Abschnitt führen wir die notwendigen Begriffe ein; die Anwendung dieser Begriffe auf Java wird in Abschnitt 6.5 [von K+Y] vorgestellt.
Die Eigenschaften des Laufzeitsystems des Computers werden unter dem Begriff Scheduling-Strategien zusammengefaßt. Hier werden folgende Begriffe unterschieden
Der erste Begriff verlangt die Fairness beim con- und atomic-Statement. Die beiden anderen Begriffe beziehen sich auf den Fall, daß das await Statement hinzukommt. Zur Verdeutlichung der Begriffe betrachten wir einige Beispiele.
In Abbildung 2.4 wird bei `unconditionally fair' Scheduling auch das Statement cont=false einmal ausgeführt, wodurch dann die while-Schleife beendet wird und das con-Statement terminiert. Ein unconditional fair Scheduling ist vom Betriebssystem z.B. durch Round-Robin-Prozess-Scheduling einfach realisierbar. Dabei werden die Prozesse wie Perlen an einem Rosenkranz reihum aktiviert und deaktiviert.
In Abbildung 2.5 folgt bei `weak fair' Scheduling u.U. keine Terminierung, denn das await-Statement wird zwar unendlich oft ausgeführt, aber es ist nicht sichergestellt, daß in diesem Moment `try' den Wert true hat. In diesem Fall wird `cont' nie auf false gesetzt, und das while-Statement terminiert nicht. Nur bei `strong fair' Scheduling folgt die Terminierung, da dann garantiert wird, daß das await-Statement unendlich oft ausgeführt wird und die Bedingung auch unendlich oft den Wert true annimmt.
Wie man sieht, kann das nur der Fall sein, wenn das await-Statement genau zwischen den Statements try=true und try=false an der Stelle `tick' ausgeführt wird. Die Bestimmung dieses Zeitpunkts ist aber nur nach eingehender Analyse des Programmtextes möglich und kann praktisch nicht vom Betriebssystem und dem Laufzeitsystem durchgeführt werden. Dies ist nur in Spezialfällen realisierbar.
Für den Programmierer bedeutet dies, daß man sich in der Regel auf unconditionally fair Scheduling für atomare Aktionen verlassen kann. Praktisch nie wird aber ein strong fair Scheduling für await realisiert sein. Das heißt beim Entwickeln von Programmen müßte an Stellen, wie beim obigen Beispiel bei tick, ein weiteres await eingeführt werden, das wartet bis das andere await die Veränderung gesehen hat.
© Universität Mannheim, Rechenzentrum, 2000-2002.
Last modified: Wed Oct 5 12:07:26 CEST 2005