next up previous contents index
Next: 3.6.1 Semaphoren Implementierung Up: 3 POSIX threads Previous: 3.5 Bedingungsvariablen und Mutual

3.6 Semaphore

Um die Verwendung von Mutexen und Bedingungsvariablen deutlicher zu machen, wollen wir eine allgemeinere Variante von Mutexen besprechen und implementieren. Dieses allgemeinere Konzept sind die sog. Semaphoren  (Signalmasten,  Leuchttürme),  die im Gegensatz zu Mutexen nicht nur die Zustände blocked und unblocked einnehmen können, sondern beliebig viele (abzählbar viele). Semaphoren wurden zuerst entwickelt, um das Problem der ``lost signals'' zu lösen.

Es gibt zwei Operationen `P' und `V' auf Semaphoren `sem':

Es wird sichergestellt, daß die Anzahl der locks tex2html_wrap_inline2546 der Anzahl der unlocks plus ein Initialisierungswert ist.

displaymath2548

Das Zählen der P- und V-Operationen kann mit einer Variablen tex2html_wrap_inline2550 und der Bedingung tex2html_wrap_inline2552 erledigt werden. Damit erhalten wir folgende (abstrakte) Implementierung der Operationen:

Man sieht, daß jetzt keine V-Operation (signal) verloren geht: auch wenn V vor P ausgeführt wird, ist sichergestellt, daß P ohne weitere Verzögerung beendet wird.

Ein Spezialfall der Semaphoren sind die Mutexe,  die wir schon kennen. Sie sind sog. binäre Semaphoren, bei denen der Zähler s nur die Werte 0 und 1 annimmt. Mutexe werden meist als

implementiert, was zu den ``lost signals'' führt. Die korrekte Fassung für V wäre

Ein Problem bei der Implementierung von V(sem) bleibt natürlich, daß s in der Regel als Integer nur Werte bis tex2html_wrap_inline2574 bzw. tex2html_wrap_inline2576 annehmen kann. Korrekterweise müßte daher auch hier die Implementierung von V(sem) sein

Die Implementierung von Semaphoren mit Hilfe von Mutexen und Bedingungsvariablen gibt uns auch ein erstes Beispiel, wie das allgemeine await Statement zu implementieren ist. Implementierungsskizze:

       P(sem): lock(sem.mux);
               WHILE sem.s <= 0 DO "waiting:=true"
                     wait(sem.pos, sem.mux) END;
               DEC(sem.s)
               unlock(sem.mux):

       V(sem): lock(sem.mux):
               INC(sem.s);
               IF some are waiting THEN signal(sem.pos) END;
               unlock(sem.mux);
Das Prinzip zur Implementierung von await wird an diesem Beispiel auch deutlich: aus ``await s > 0 ...'' wird
       IF not (s>0) THEN wait(sem.pos) ...
Nach dem s > 0 geworden sein kann, nämlich nach INC(s) in V(sem), wird bei Bedarf signalisiert, daß s nun positiv ist
       INC(s); ...; signal(sem.pos);

Bemerkung: Das Zählen der wartenden Pthreads könnte man einsparen, falls in V(sem) die Signal-Operation bedingungslos nach jedem INC(s) ausgeführt würde. tex2html_wrap_inline2239 u.U. schlechtere Performance




next up previous contents index
Next: 3.6.1 Semaphoren Implementierung Up: 3 POSIX threads Previous: 3.5 Bedingungsvariablen und Mutual

parallel@rz.uni-mannheim.de
Mon Okt 28 14:38:25 PST 1996