Semaphor (Informatik)

Ein Semaphor (griech.: Zeichenträger) ist eine Datenstruktur zur Lösung von Problemen, bei denen mehrere Prozesse ein Betriebsmittel verwenden wollen, von dem nur eine begrenzte Zahl zur Verfügung steht. Der häufigste Sonderfall ist, dass nur ein einziges Exemplar dieses Betriebsmittels zur Verfügung steht. Bei der Art des Betriebsmittels kann es sich um verschiedenste Ressourcen (z.B. CPUs) oder Programmteile (sogenannte kritische Regionen) handeln. Ursprünglich bezeichnet das Wort Semaphor einen Signalmast mit beweglichen Flügeln, wie er zur Nachrichtenübertragung in früheren Jahrhunderten eingesetzt wurde, später auch eine Verkehrsampel. Auch bei der Eisenbahn wurden die Formsignale als Semaphore bezeichnet. Der Informatiker Edsger W. Dijkstra hat Semaphore erstmals im Jahre 1965 bei der Implementierung seines Betriebssystems verwendet.

Probleme bei mehreren Prozessen

In Mehrprozess-Systemen und Mehr-Prozessor-Systemen treten die folgenden Probleme auf, die mit Hilfe von Semaphoren gelöst werden können:

Teilen von globalen Ressourcen

Ressourcen wie Drucker, Speicher, Prozessoren sind beschränkt. Stehen z. B. drei gleiche Drucker zur Verfügung, so muss der Zugriff auf diese Drucker geregelt werden. Es können maximal drei Druckaufträge parallel ausgeführt werden. Will ein vierter Prozess drucken, so muss er auf das Ende eines Auftrags warten.

Interprozesskommunikation/Prozesssynchronisation

Zugriffe auf thread-globalen Speicher müssen bei möglichem Zugriff aus mehreren Threads gekapselt werden. Bei Ein-Prozessor-Systemen sind u.U. noch Tricks in Form von temporärem Unterdrücken von Interrupts oder Taskwechseln oder atomaren Read-Modify-Write-Befehlen möglich. Spätestens bei Mehrprozessorsystemen sind Semaphoren und entsprechend abgestimmte Programme notwendig. Auf eine Datenstruktur sind folgende Zugriffsarten möglich:
- ein oder mehrere Lese-Threads
- exakt ein Schreib-Thread
- keine Zugriffe

Mehrere Schreibzugriffe gleichzeitig führen zu inkonsistenten Daten, gleichzeitiges Lesen und Schreiben zu Inkonsistenzen der gelesenen Daten. Um das zu verhindern, müssen Datenstrukturen um Semaphoren oder kritische Abschnitte erweitert werden, die vor Zugriff auf die eigentliche Struktur geholt und wieder zurückgegeben werden.

Dijkstras Lösung

Die Datenstruktur verfügt über einen Zähler und eventuell eine Prozess-Warteschlange sowie über die Methoden wait und signal. Zunächst verwendete Dijkstra die Bezeichnungen P und V (niederländisch für passeren / vrijgeven (passieren / freigeben)).

Es wird festgelegt, wieviele kritische Prozesse existieren dürfen, wobei jeder Prozess eine Ressource beansprucht. Die Zahl der noch freien Ressourcen wird im Zähler festgehalten. Jeder wait-Aufruf verringert den Zähler. Ist der Zähler danach kleiner als Null, wird der aufrufende Prozess in die Warteschlange des Semaphors eingereiht, sonst darf er den kritischen Abschnitt betreten. Die Methode signal erhöht den Zähler. War der Zähler vorher kleiner als Null, wird der an der ersten Position befindliche Prozess aus der Warteschlange befreit. Manchmal wartet auch der Prozess bei wait in einer Schleife, falls und solange der Zähler gleich Null ist, und verringert ihn erst anschließend (inzwischen wurde er ja wieder erhöht).

Stehen z.B. drei gleiche Drucker zur Verfügung, können die Druckaufträge über ein Semaphor mit dem Maximalwert drei verwaltet werden. Zunächst erhält jeder Drucker einen Auftrag. Überschreitet die Zahl der aktuellen Aufträge die Zahl drei, kommen die überzähligen in die Warteschlange.

Im einfachsten Fall besteht ein Semaphor aus einem Bit, das gesetzt sein kann oder nicht, was auch binärer Semaphor oder Mutex genannt wird. Ein Prozess, der einen kritischen Bereich betritt, löscht das Semaphor-Bit. Dies verhindert das Betreten des Bereichs durch andere Prozesse. Der Semaphor wird wieder gelöst, wenn der Prozess den kritischen Bereich verlässt. Wartende Prozesse werden dann nacheinander aktiviert.

Eine andere Möglichkeit zur Synchronisation von kritischen Prozessen sind Monitore.

Implementation

Ein Semaphor ist eine geschützte Variable (oder ein abstrakter Datentyp), auf die nur über folgende Funktionen zugegriffen werden kann:

P(Semaphor s)
{
  while (s <= 0) ;     // warte bis s>0, Spinlock
  s = s-1 ;            // sobald s>0 belege eine Ressource
}

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

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

Der Wert eines Semaphors ist die Anzahl an freien Einheiten der Ressource. Die Funktion P() wartet, bis eine Ressource verfügbar ist, worauf sie unmittelbar darauf eine beansprucht. V() ist die umgekehrte Funktion, die die Ressource wieder verfügbar macht, nachdem sie vom Prozess nicht mehr verwendet wird. Die Funktionen P() und V() müssen atomar sein, d.h. kein anderer Prozess kann auf die Semaphore während deren Ausführung zugreifen. Die Funktion V() wird auch als up, die Funktion P() als down bezeichnet.

Vermeidung von Warteschleifen

Warteschleifen verschwenden unnötig Prozessorzeit. Um eine Warteschleife zu vermeiden, kann einem Semaphor eine Liste von Prozessen zugeordnet werden. Wenn ein Prozess die P()-Funktion ausführt und der Semaphor bereits auf Null gesetzt ist, dann wird der Prozess dieser Liste, die Warteschlange genannt wird, hinzugefügt. Wenn ein Prozess den Semaphor mit der V()-Funktion erhöht, und andere Prozesse in der Warteliste sind, dann wird einer davon von der Liste genommen und fortgesetzt.

Queue queue;             /* Warteschlange */

P(Semaphor s)
{
  if (s==0)
         haltean(queue); /* Anhalten des Prozesses, Einreihung in Warteschlange */
  s = s-1;
}

V(Semaphor s)
{
  s = s+1;
  weckeauf(queue);       /* Aufwecken eines Prozesses bei nichtleerer Warteschlange */
}

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

Dabei ist jedoch zu beachten, dass bei Prozessoren, die keine speziellen Befehle zur Verwaltung von Listen besitzen, wieder kritische Bereiche bei der Implementation der Warteschlangen auftreten. Diese müssen dann mit anderen Methoden (Spinlock, Verhindern einer Unterbrechung) geschützt werden.

Siehe auch: Interprozesskommunikation