Semaphor

Ein Semaphor (griech.: "Zeichenträger") ist eine Datenstruktur zur Synchronisation des Zugriffs auf kritische Regionen oder Ressourcen bei nebenläufigen Prozessen. 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 Dijkstra hat Semaphore erstmals im Jahre 1965 bei der Implementation seines THE Betriebssystems verwendet.

Probleme bei mehreren Prozessen

In Mehrprozesssystemen treten die folgenden Probleme auf, die mit Hilfe von Semaphoren gelöst werden können:

• 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.
• Zugriffe innerhalb des Speichers können nicht immer auf eine Maschineninstruktion abgebildet werden, insbesondere wenn die Speicherfläche für eine Struktur mehr als ein Maschinenwort beträgt oder wenn ein Maschinenwort nur teilweise geändert werden soll. Überlappende Zugriffe mehrerer Prozesse müssen verhindert werden, da sonst die Daten unter Umständen zerstört werden. Speicherflächen, die so geschützt werden müssen, nennt man kritische Bereiche.

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.

Es wird festgelegt, wieviele kritische Prozesse existieren dürfen, wobei jeder Prozess eine Ressource verbraucht. Die Zahl der noch freien Prozesse wird im Zähler festgehalten. Jeder wait-Aufruf verringert den Zähler. Wird der Zähler Null, so reiht die Methode wait den letzten Prozess in eine Warteschlange ein. Manchmal wartet der Prozess auch in einer Schleife. Die Methode signal erhöht den Zähler. Wenn der Zähler wieder positiv wird, wird der an der ersten Position befindliche Prozess aus der Warteschlange geholt. Eine andere Möglichkeit zur Synchronisation von kritischen Prozessen sind Monitore.

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.

Stehen z.B. drei gleiche Laserdrucker zu 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, werden die überzähligen in die Warteschlange des Semaphors eingereiht.

Implementation

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

 P(s)

  Semaphor s;

  {

    while (s == 0) ; /* warte bis s>0, Spinlock */

    s = s-1;

  }

 

 V(s)

  Semaphor s;

  {

    s = s+1;

  }

 

 Init(s, v)

  Semaphor s;

  Int v;

  {

    s = v;

  }

 

P und V stehen für Niederländisch "passeren", passieren und "verlaten", verlassen. Der Wert eines Semaphor ist die Anzahl an freien Einheiten der Ressource (wenn es nur eine Ressource gibt, wird ein "binärer Semaphor" mit dem Wert 0 oder 1 verwendet). 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 damit den Semaphor auf Null setzt, 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(s)

  Semaphor s;

  {

    if (s==0)

           haltean(queue); /* Anhalten des Prozesses, Einreihung in Warteschlange */

    s = s-1;

  }

 

 V(s)

  Semaphor s;

  {

    s = s+1;

    weckeauf(queue); /* Aufwecken eines Prozesses bei nichtleerer Warteschlange */

  }

 

 Init(s, v)

  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