Thread Funktionalität als
Sprachkonstrukte oder externe Bibliotheken
- Java: Threads als Basisklassen und Spracherweiterungen
- Ada: Threads, ``Tasks'' genannt im Sprachumfang
- C, C++, Modula-2, FORTRAN und andere: Programmbibliotheken
- z.B. POSIX Threads Bibliothek ``Pthread''
- in OSF DCE und anderen Systemen
- OS/2 und Win32: eigene Thread-Systeme
- Userlevel-Threads vs. Kernel-Threads
- Java: green Threads, native Threads
- bei Mehrprozessorrechnern nur Kernel-Threads sinnvoll
- Prozeß (siehe Abbildung 1)
hat zunächst ein Hauptthread
- dieser kann weitere Threads erzeugen, etc.
- Zugriff und Modifikation gemeinsamer Ressourcen
(Speicher, Dateien, Netzverbindungen)
- falls alle Aufgaben getan, Terminierung
- Thread Zustände:
- running,
- blocked,
- ready oder
- terminated
Abbildung 1:
Threads innerhalb von Prozessen
|
Abbildung 1a:
Thread Zustände
|
Java-Implementierung von Threads, enthalten
in dem Java-Package java.lang:
- der Klasse Thread und dem Interface Runnable,
- dem Java-Sprachkonstrukt synchronized und
- den Methoden wait(), notify() der Basisklasse
Object.
Erzeugung von Threads:
ein Objekt einer geeigneten Klasse erzeugen,
Aufruf einer Methode dieses Objekts.
Für die Klasse gibt es zwei Möglichkeiten:
- Bildung einer Subklasse der Thread-Klasse
- Bildung einer Klasse, die das Runnable
Interface implementiert.
Subklasse von Thread
- Vorteil: bequem alle Methoden der Thread-Klasse erben verwenden
- Nachteil: keine Mehrfachvererbung in Java
wenn von Applet abgeleitet wird, kann
nicht gleichzeitig von Thread abgeleitet werden.
Implementierung des Runnable-Interface
- verlangt nur Methode public void run()
- keine weiteren Anforderungen
- zweite Methode bevorzugt
Der Thread-Konstruktor und die Thread-Methoden
start() und join()
haben die folgenden Spezifikationen.
public Thread(Runnable target)
public Thread(Runnable target, String name)
public Thread(ThreadGroup group, Runnable target, String name)
public synchronized void start()
public final void join() throws InterruptedException
- ThreadGroup definieren von Gruppen von Threads
- Operationen zur Steuerung der Mitglieder-Threads
- meist reicht die erste Variante Thread(Runnable target)
- mit start()-Methode wird run()-Methode
der Klasse myRunnable gestartet
- mit join()-Methode warten auf
normale Beendigung des Threads
- Terminierung mit stop() ab Java 1.2 nicht mehr
erster Eindruck eines parallelen Java-Programms:
class Action implements Runnable {
int var;
public Action(int v) { var = v; }
public void run() { doSomeWork(var); }
}
- erster Teil: eine Klasse, die Runnable implementiert
- Konstruktor nimmt einen Parameter entgegen
- doSomeWork() wird in der run()-Methode
verwendet
- run()-Methode wird von
start()-Methode gestartet
Thread t1 = new Thread(new Action(1));
Thread t2 = new Thread(new Action(2));
Thread t3 = new Thread(new Action(3));
try {
t1.start(); t2.start(); t3.start();
t1.join(); t2.join(); t3.join();
}
catch (InterruptedException e) { ... }
- zweiter Teil: Erzeugung von drei Threads t1,
t2 und t3
- Threads werden mit einem neuen Objekt Action erzeugt
- der Reihe nach gestartet mit mit ti.start()
- ti.join() wartet auf die Terminierung
- InterruptedException abfangen
In verschiedenen run()-Methoden u.U.
gleichzeitiger Zugriff auf globale Variablen.
- Vorsicht geboten, da sonst falsche oder zufällige Werte enthalten
- Gegenseitiger Ausschluß
( mutual exclusion)
- Abstimmen der Abarbeitungsschritte
( condition synchronization)
Wir können nicht verhindern, daß Schreib- oder
Lese-Operationen auf den globalen Speicher in
nebenläufigen Prozessen stattfinden und sichtbar werden.
- Trick: Thread in der Ausführung anhalten
- Nachteil: alle ``kritischen'' Bereiche in
allen Threads ausfindig machen
- Absichern durch Haltekonstrukt
- keine so große Einschränkung
- da oft in einer Klasse isolierbar / kontrollierbar
- Anhalten durch synchronized-Sprachkonstrukt
Das Java-Sprachkonstrukt synchronized
hat die folgenden Varianten.
synchronized (object) { ... }
synchronized (static object) { ... }
synchronized type methodName(...) { ... }
static synchronized type methodName(...) { ... }
- erste Variante: object einer beliebigen, von Object
abgeleiteten Klasse als Haltepunkt
- Java-Laufzeitsystem stellt sicher, daß immer nur
maximal ein Thread die Statements
{...}
ausführen kann
- einen ``lock'' setzen (es ``verschließen'')
- ``lock'' kann immer nur einmal zu einem gegebenen Zeitpunkt aktiv
- gegenseitiger Ausschluß (``mutual exclusion'')
- ``lock''-Objekte auch als ``mutex'' bezeichnet
- Objekt als static, dann ``lock'' Systemweit nur einmal
- mehrere Objekts haben dann verschiedene
``locks'', die untereinander nicht synchronisiert sind
Die Semantik von
synchronized type methodName(...) { S1; ...; Sn; }
entspricht
type methodName(...) {
synchronized(this) { S1; ...; Sn; }
}
- Methoden einer Klasse, die nicht als synchronized sind,
können frei auf die Objektvariablen zugreifen
- es findet keine Synchronisation statt
- keine echten Monitore, wie sie von Hoare entwickelt wurden
- Nur wenn alle Nicht- private-Methoden synchronized
und nur private-Variablen, wie Monitor
Bemerkungen:
- synchronized wird nicht vererbt !
- synchronized verringert die Parallelität, daher
oft synchronized(obj) { ... } mit minimalem Code
- synchronized ist bei mehreren CPUs eine recht
aufwendige Operation
Problem: Initialisierung innerhalb eines parallelen Ablaufs.
Beispiel: Summe von Vektoren.
Zur Verfügung stehen uns die Object-Funktionen
wait() und notify()
mit den folgenden Spezifikationen:
public final void wait() throws InterruptedException
public final void wait(long timeout)
throws InterruptedException
public final void notify()
public final void notifyAll()
wait() nur innerhalb eines
synchronized Abschnitts
- Aufruf von wait() versetzt den aufrufenden Thread
in den Wartezustand (``blocked'')
- und gleichzeitig wird der Lock ( synchronized)
auf diesen Abschnitt freigegeben
- wartet, bis ein anderer Thread notify()-Methode aufruft
- oder bis ein Timeout stattfindet
- dann warten bis er den Lock auf den Abschnitt
wieder erhält, und dann wieder ``ready'' (``runnable'')
- notify() weckt genau einen Thread im wait-Zustand auf.
- Falls mehrere Threads warten, ist nicht vorhersehbar welcher Thread
aufgeweckt wird.
- signal in Pthreads; mindestens ein Thread
- notifyAll weckt alle an diesem Objekt
wartenden Threads auf.
- Varianten mit timeout: `timed wait'
- Bedingung erneut getesten ob Timeout oder notify.
Fall eines beliebigen Booleschen Ausdrucks der erfüllt sein soll.
- Bedingungsvariable für jede semantisch verschiedene Bedingung
- Test, ob sie wahr ist, an alle Stellen verlegt, an denen
die Bedingung wahr geworden sein könnte
- dort wird mit notify (oder notifyAll) der
Eintritt der Bedingung signalisiert
- es kann von mehreren Threads gleichzeitig oder
kurz hintereinander ein notify ausgelöst werden
- daher die Verzögerungsbedingung erneut testen
- denn weiterer Thread könnte sie in der Zwischenzeit schon
wieder ungültig gemacht haben
- Problem falls notify() vor wait()
- dann immer blockiert (sogenanntes ``lost signal'')
- eine Lösung zu diesem Problem stellen Semaphore dar
- wichtigste Java Sprachkonstrukte zur Thread Programmierung
- Thread(new Runnable), start(), join()
- synchronized (.), synchronized methodName
- wait(), notify()
- Anwendungen sind zum Beispiel Semaphore, Barrieren und
das Bounded-Buffer-Problem
- Verwendung von Threads in der Applet-Programmierung
- auch viel in Java Beans und in den neuen Java Swing Klassen
Abbildung A1:ExCon
Abbildung A2:UML Seq ExCon
Abbildung B1:ExAtom
Abbildung B2:UML Seq ExAtom
2.6 Semaphore
Es gibt zwei Operationen `V' (Abkürzung für holländisch `frei')
und `P' (für `passieren') auf Semaphoren `sem':
- sem.P():
- entspricht dem Eintritt (Passieren)
in einen synchronisierten Bereich,
wobei mitgezählt wird, der wievielte
Eintritt es ist.
- sem.V():
- entspricht dem Verlassen (Freigeben)
eines synchronisierten Bereiches,
wobei ebenfalls mitgezählt wird,
wie oft der Bereich verlassen wird.
Es wird sichergestellt, daß die Anzahl der Eintritte (#P)
kleiner oder gleich der Anzahl der Austritte (#V)
plus ein Initialisierungswert ist
# P <= # V + init.
Das Zählen der P- und V-Operationen kann mit einer Variablen
s = # V + init - # P
und der Bedingung
s >= 0 erledigt werden.
Implementierungsskizze:
sem.P(): synchronized (mux) {
while (s <= 0) { "waiting = true"
wait(); }
s--;
}
sem.V(): synchronized (mux) {
s++;
if ("some are waiting") { notify(); }
}
Implementierungen:
Sema.java,
Semaphore.java
Abbildung C1:UML Semaphore
2.7 Barrieren
Mit Barrieren kann man warten, bis sich eine vorgegebene Anzahl
von Teilnehmern angemeldet hat, und dann weiterarbeiten.
public class Barrier {
private int n, b;
public Barrier(int i) {
n = i; b = 0;
}
public synchronized void check() {
b++;
if (b < n) {
try { this.wait();
} catch (InterruptedException e) {}
}
else { b = 0;
this.notifyAll();
}
}
}
Abbildung D1:UML Barrier
public class Barrier {
private int n, b;
private Sema bs, bl;
public Barrier(int i) {
n = i; b = 0;
bs = new Sema(0);
bl = new Sema(1);
}
public void check() {
bl.P();
b++;
if (b < n) {
bl.V(); bs.P();
}
else {
b = 0;
for (int j=1; j<n; j++) { bs.V(); }
bl.V();
}
}
}
2.8 BoundedBuffer
n Produzenten erzeugen Daten, die an m Konsumenten weitergegeben
werden sollen.
Zur Weitergabe der Daten dient ein Puffer,
der in der Lage sein soll, k Daten zu speichern
( 1 <= n, 1 <= m, 1 <= k ).
Falls der Puffer voll ist, sollen die Produzenten warten,
bis wieder Platz ist, und falls der Puffer leer ist,
sollen die Konsumenten warten, bis wieder Daten vorhanden sind.
Falls keine Arbeit mehr anliegt, sollen die Produzenten und
die Konsumenten terminieren.
Der Puffer wird als Ringpuffer implementiert,
siehe Abbildung E1.
Die Variablen `front' und `rear' zeigen jeweils auf den
nächsten vollen Platz zum Lesen des Puffers bzw. auf den
nächsten freien Platz zum Schreiben.
Falls der Puffer nicht voll ist, kann ein Produzent in den Puffer
schreiben, und falls der Puffer nicht leer ist,
kann ein Konsument aus dem Puffer lesen.
Die Synchronisation muß somit sicherstellen, daß der Produzent
wartet, falls der Puffer voll ist, und der Konsument wartet,
falls der Puffer leer ist. Das heißt, sei x die Anzahl der
Elemente im Puffer, dann muß immer gelten
1 <= x <= k.
Insbesondere muß gelten
x <= k
damit der Produzent eine Nachricht schreiben darf.
Und es muß gelten
1 <= x
damit der Konsument eine Nachricht lesen kann.
Abbildung E1:Ringpuffer
Implementierung:
BoundedBuffer.java
© Universität Mannheim, Rechenzentrum, 2000-2002.
Last modified: Sun Aug 1 14:15:59 CEST 2004