2. Synchronisation
c. Semaphore
Semaphore in der Informatik wurden 1965 von Dijkstra entwickelt,
sie sollen gegenseitigen Ausschluss ohne aktives Warten realisieren.
Hierzu wird eine spezielle Variable eingeführt, das Semaphor. Man unterscheidet
binäre Semaphore, bei der die Variable nur die Werte 0 oder 1 annehmen
kann, sowie starke und schwache Semaphore. Diese Typen von Semaphoren lassen
die Variable auch andere Werte als 0 oder 1 annehmen, um z.B. eine Gruppe von
Betriebsmitteln abzubilden (z.B. bei drei zur Verfügung stehenden Druckern
wäre die Variable s=3). Bei starken Semaphoren werden die Prozesse in einer
bestimmten Abfolge aus dem Wartebereich des Semaphors wieder aktiviert, bei
den schwachen Semaphoren gibt es hierüber keine weitere Festlegung.
Semaphore implementieren zwei Operationen, die zumeist mit
P(s) und V(s) bezeichnet werden:
P(s) steht für das niederländische Wort „passeren“, übersetzt
„passieren“. Beim Aufruf der Funktion wird zuerst der Wert der Variable
überprüft. Wenn dieser 0 ist, dann wird dem Prozess das Betreten seines
kritischen Abschnittes, bzw. die Belegung des Betriebsmittels verweigert. Dies
geschieht in der einfachsten Variante des Semaphors mit aktivem Warten. Wenn
der Wert der Semaphorvariable größer als 0 ist, wird diese um 1 dekrementiert
und der Prozess kann mit der Ausführung fortfahren.
Die Operation V(s) (V steht für niederländisch „verlaten“,
also „verlassen“) gibt die Ressource wieder frei, inkrementiert
den Wert von s also um eins.
Diese Operationen müssen atomar auszuführen sein,
d.h. kein anderer Prozess kann auf die Semaphore während der Ausführung
zugreifen.
Neben den beiden oben beschriebenen Operationen muss es noch eine Operation
zum Initialisieren des Semaphors geben. Eine mögliche Implementierung dieses
Synchronisierungskonzeptes könnte also wie folgt lauten:
Semaphor s; P(Semaphor s) { V(Semaphor s) { |
Diese Variante vermeidet noch nicht das aktive Warten, so dass dem Semaphor ein Wartebereich zugeordnet wird, in der die blockierten Prozesse auf das „Aufwecken“ warten, ohne Rechenleistung dafür in Anspruch zu nehmen. Die erweiterte Lösung sieht dann wie folgt aus:
Semaphor s; P(Semaphor s) { V(Semaphor s) { |
Hierbei ist zu beachten, dass die Operationen zum Aufwecken und Einreihen in die Warteschlange besondere Beachtung benötigen, da dort ebenfalls wieder kritische Abschnitte auftreten.
Ein binärer Semaphor kann leicht zur Implementierung des gegenseitigen Ausschlusses verwendet werden, wie das folgende Beispiel zeigen soll.
Semaphor s; // Wertebereich für s ->
[0,1] Prozess 1: while (true) { P(s); kritischer Abschnitt1; V(s); } |
Da die Semaphorvariable nur die
Werte 1 und 0 annehmen kann, wird durch das Dekrementieren dieser Variable in
der Prozedur P(s) anderen Prozessen das Betreten des kritischen Abschnittes
verboten, solange ein Prozess noch nicht wieder die Operation V(s) aufgerufen
hat.
Erzeuger-Verbraucher-Problem
Eine häufig im Zusammenhang mit Semaphoren genannte
Fragestellung ist das Erzeuger-Verbraucher-Problem.
Ein Puffer in einem System ist ein Beispiel für dieses Problem. Es gibt
mehrere Erzeuger, die bestimmte Daten produzieren, und eine Anzahl von Verbrauchern,
die diese Daten für ihre Zwecke verarbeiten. Dabei soll gelten, dass die
Erzeuger nicht in einen schon vollen Puffer (bei einem begrenzten Puffer) schreiben,
und die Verbraucher nicht aus einem leeren Puffer lesen dürfen. Also muss
gegeben sein, dass die entsprechenden Prozesse blockiert werden, sobald diese
Voraussetzungen nicht mehr erfüllt werden. Zu diesem Zweck werden drei
Semaphore eingeführt, dabei eine, um den kritischen Bereich des Zugriffs
auf den Puffer zu schützen. Zwei Semaphore sollen den Prozessen signalisieren,
ob Elemente im Puffer vorhanden sind, bzw. ob der Puffer voll ist im Falle des
Erzeugerprozesses.
Semaphor mutex = 1; // Binäres Semaphor, Schützen
des KA Semaphor full = 0; // Anzeige, ob Puffer voll Semaphor empty = n; // Anzeige, ob Elemente im Puffer. Initialisierung mit Puffergröße n |
|
Erzeuger: while (true) { produzieren(item); P(empty); P(mutex); in Puffer schreiben(item); V(mutex); V(full); } |
Verbraucher: while (true) { P(full); P(mutex); aus Puffer entfernen(item); V(mutex); V(empty); verbrauchen(item); } |