2.c. Synchronisation

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;

Init (Semaphor s, int v) {
s = v;
}

P(Semaphor s) {
while (s <= 0) { }
s = s – 1;
}

V(Semaphor s) {
s = s + 1;
}

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;
Queue queue;

Init (Semaphor s, int v) {
s = v;
}

P(Semaphor s) {
while (s <= 0) {
halte_Prozess_an(queue);
}
s = s – 1;
}

V(Semaphor s) {
s = s + 1;
wecke_Prozess_auf(queue);
}

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); }