Semaphore (Programmierung)

Ein Semaphor ist eine Datenstruktur mit zwei speziellen Nutzungsoperationen. Semaphore werden bei der Programmierung zur Prozesssynchronisation eingesetzt, also zur Lösung von Aufgaben, bei denen die parallele Ausführung mehrerer Prozesse/Threads eine zeitliche Abstimmung der Ausführungen erfordert.

Namensherkunft

Verlassenes Eisenbahnsignal (Semaphor)

Das Wort Semaphor geht auf die Formsignale, mechanische Eisenbahnsignale zurück.^[1] Die dort verwendeten Semaphore zeigen an, ob ein Zug einen Gleisabschnitt befahren darf oder ob nicht.

Wechselwirkungen parallel ablaufender Prozesse

Bei der parallelen oder zeitlich verzahnten Ausführung von Prozessen treten implizite oder explizite Wechselwirkungen auf.

Bei impliziten Wechselwirkungen ist einem Prozess nicht bewusst, dass durch die Ausführung von Aktionen ein anderer Prozess beeinflusst wird. Dies ist z. B. dann der Fall, wenn ein Prozess einen Systemdienst aufruft, den das Betriebssystem nicht sofort vollständig bearbeiten kann, weil andere Prozesse die erforderlichen Betriebsmittel belegt haben. Der Prozess kann erst dann seine Aktionen weiter fortsetzen, wenn der Systemdienst ausgeführt worden ist. Hier wird die Prozesswechselwirkung als blockierender Funktionsaufruf sichtbar. Spezielle Vorkehrungen gegen eine Blockierung aufgrund impliziter Wechselwirkungen muss und kann ein Prozess nicht treffen.

Explizite Wechselwirkungen zwischen Prozessen sind:

Konkurrenz

Prozesse stehen in Konkurrenz zueinander, wenn sie gleichzeitig auf ein Betriebsmittel (z. B. Speicherstruktur, Verbindung, Gerät) zugreifen, das nur in beschränkter Anzahl zur Verfügung steht und dessen Nutzung nur exklusiv durch einen Prozess möglich ist, da es andernfalls zu fehlerhaften Ergebnissen oder inkonsistenten Zuständen kommt, d. h. wenn es kritische Abschnitte in den Programmen der Prozesse gibt.

Kooperation

Prozesse kooperieren, wenn sie ihre Aktionen bewusst aufeinander abstimmen, z. B. weil sie in einer Auftraggeber/Auftragnehmerbeziehung stehen.

Bei expliziten Wechselwirkungen muss eine Abstimmung der zeitlichen Ausführung der Prozessaktionen vorgenommen werden. Im Fall einer Konkurrenzsituation wird durch eine irgendwie gestaltete Sequentialisierung der Ausführung der kritischen Abschnitte erreicht, dass Betriebsmittel nicht von mehreren Prozessen beliebig verändernd benutzt werden (sog. wechselseitiger Ausschluss). Im Fall einer Kooperationssituation wird ebenfalls durch eine der Situation entsprechende Sequentialisierung erreicht, dass die Zusammenarbeit der Prozesse gegeben ist (z. B., dass ein Auftragnehmer nicht schon angefangen hat, etwas zu bearbeiten, obwohl der Auftraggeber noch keinen Auftrag erteilt hat).

Lösung von Dijkstra

Semaphore als Mechanismus für die Prozesssynchronisation wurden von Edsger W. Dijkstra konzipiert und 1965 in seinem Artikel Cooperating sequential processes vorgestellt.

Ein Semaphor ist eine Datenstruktur mit einer Initialisierungsoperation und zwei Nutzungsoperationen. Die Datenstruktur besteht aus einem Zähler und einer Warteschlange für die Aufnahme blockierter Prozesse:

struct Semaphor {
   int zaehler;
   Queue queue;             /* Warteschlange */
}

Zähler sowie Warteschlange sind geschützt und können nur über die Semaphoroperationen verändert werden. Die Wirkung der Nutzungsoperation kann wie folgt zusammenfassend beschrieben werden:

• Semaphore regeln durch Zählen Wechselwirkungssituationen von Prozessen
• Semaphore realisieren ein passives Warten der Prozesse, wenn eine Weiterausführung nicht gestattet werden kann

Mit der Initialisierungsoperation wird der Zähler auf einen nicht negativen Wert (>= 0) und die Warteschlange i. d. R. auf leer gesetzt.

void init (Semaphor s, int v) {
   s.zaehler = v;
   s.queue.empty ();
}

Wird ein Semaphor zur Organisation von Konkurrenzsituationen eingesetzt, so erfolgt eine Initialisierung mit einem positiven Wert. Ein Semaphor für eine Kooperationssituation wird hingegen mit 0 initialisiert (s. Anwendungsbeispiele).

Die Nutzungsoperationen wurden von Dijkstra mit P und V bezeichnet. Dies sind Initialen niederländischer Wörter bzw. Kofferwörter für prolaag und verhoog [1]. Weitere, verbreitete Erklärungen sind passeer, probeer und vrijgeven. Programmierschnittstellen verwenden mnemonisch deutlichere Bezeichnungen wie wait, acquire oder down für die P-Operation und signal, release oder up für die V-Operation.

Bei einem Aufruf der P-Operation wird der Zähler dekrementiert. Ist der Zähler danach größer gleich 0, so setzt der Prozess seine Aktionen fort. Ist der Zähler jedoch kleiner als 0, kehrt der Kontrollfluss nicht aus der Operation zurück. Der aufrufende Prozess wird blockiert und in die Warteschlange des Semaphors eingereiht. Bei einem Aufruf der V-Operation wird der Zähler inkrementiert. Es wird ein Prozess aus der Warteschlange entnommen und entblockiert, falls die Warteschlange nicht leer ist. Der entblockierte Prozess setzt dann seine Aktionen mit denen fort, die dem P-Aufruf folgen, der den Prozess blockierte. Die hier erläuterte Funktionsweise der Semaphoroperationen erlaubt eine einfache Ermittlung, ob es Prozesse gibt, die am Semaphor blockiert sind: ist der Sempahorzähler kleiner gleich 0, so gibt es noch blockierte Prozesse. Diese Prozesse riefen die P-Operation auf, als der Zähler bereits kleiner gleich 0 war. Die Überprüfung wird hier zwecks Verdeutlichung der Wirkung der V-Operation auf andere Prozesse explizit notiert. Konkrete Implementierungen können eine Prüfung auf nicht-leere Warteschlange auch in die Warteschlangenmethode verlagern.

void P (Semaphor s) {
  s.zaehler = s.zaehler - 1;
  if (s.zaehler < 0)
     selbst_blockieren(s.queue);    /* Blockieren des Prozesses, Einreihung in Warteschlange */
}

void V (Semaphor s) {
  s.zaehler = s.zaehler + 1;
  if (s.zaehler <= 0)
     einen_entblocken(s.queue);  /* Entblockieren eines Prozesses aus der Warteschlange */
}

Semaphore, deren Zähler aufgrund der Initialisierung und der Verwendung 1 als größten positiven Wert annehmen können, werden oftmals auch binäre Semaphore bezeichnet. Semaphore, deren Zähler größere positive Werte annehmen können, werden dann zählende Semaphore genannt.

Beide Operationen müssen unteilbare Aktionen sein. Dadurch ist garantiert, dass nach dem Aufruf einer Operation eines Semaphors kein anderer Prozess auf den gleichen Semaphor durch einen Operationsaufruf modifizierend zugreifen kann, bevor die zuerst aufgerufene Semaphoroperation vollständig ausgeführt worden ist. Die Unteilbarkeit ist notwendig, um die Synchronisation zu organisieren und Wettlaufsituationen bei Ausführung der Semaphoroperationen durch parallele Prozesse zu vermeiden.

Die obige Erläuterung der Arbeitsweise ist eine von mehreren möglichen. Diese unterscheiden sich durch die Reihenfolge der Prüfung auf Blockierung/Entblockierung und der Operation Inkrement/Dekrement. In einigen Erläuterungen nimmt der Zähler keine negativen Werte an. In diesem Fall wird die Bezeichnung binärer Semaphor dann offensichtlich. Die Wirkung der Operationen auf Prozesse ist jedoch unabhängig von der Art der Realisierung. Der obigen Erläuterung wurde wegen einer einfachen Interpretation des Zählers der Vorzug gegeben. Ist der Zähler größer als 0, so gibt sein Wert an, wie viele Prozesse noch ohne Blockierung die P-Operation aufrufen können. Ist der Zähler negativ, so gibt sein Absolutwert an, wie viele Prozesse die P-Operation aufgerufen haben und dabei blockiert wurden.

Semaphore beheben den Nachteil des aktiven Wartens anderer Synchronisationslösungen wie spezielle Maschinenbefehle oder Spinlocks, da ein Prozess blockiert wird, bis der Blockadegrund entfallen ist. Die Definition lässt offen, welcher blockierte Prozess im Rahmen der Ausführung der V-Operation der Warteschlange entnommen wird. Ein Semaphor, der eine echte Warteschlange nach dem Windhundprinzip (engl. „first come, first served“) garantiert, wird manchmal als starker Semaphor bezeichnet. Ein schwacher Semaphor garantiert hingegen nicht die chronologisch richtige Abarbeitung der Warteschlange. So wird z. B. beim Echtzeitbetrieb das Entblockieren von Prozessen an deren Priorität statt an deren Blockierungszeitpunkt gebunden.

Anwendungsbeispiele

• Einsatz in Konkurrenzsituationen I
  In einem kritischen Abschnitt ka_A verändert Prozess A eine Datenstruktur, die der Prozess gemeinsam mit einem Prozess B nutzt. Prozess B verändert die Datenstruktur in seinem kritischen Abschnitt ka_B. Ein Semaphor in Ausschlussfunktion wird eingesetzt, um zu erreichen, dass sich die Prozesse A und B niemals gleichzeitig in ihren kritischen Abschnitten befinden. Hierzu wird der Semaphor mit 1 initialisiert, es wird also ein binärer Semaphor eingesetzt:

       Gemeinsam von A und B genutzter Semaphor: mutex
       Initialisierung:                          init (mutex, 1)
       
       Prozess A           Prozess B
          ...                 ...
          P (mutex)           P (mutex)   /* Anzeige 'will k.A. betreten' */
          ka_A                ka_B
          V (mutex)           V (mutex)   /* Anzeige 'habe k.A. verlassen' */
          ...                 ...

• Einsatz in Konkurrenzsituationen II
  Benötigen Prozesse jeweils exklusiv ein Betriebsmittel, das nur in beschränkter Anzahl zur Verfügung steht, so wird mittels eines zählenden Semaphors erreicht, dass ein Prozess dann blockiert wird, wenn alle Betriebsmittel in Benutzung sind. Der Semaphor wird mit der Anzahl verfügbarer Betriebsmittel initialisiert:

       Semaphor zur Betriebsmittelverwaltung: available
       Initialisierung:                       init (available, n)
       
       Prozess
          ...
          P (available)    /* Anzeige des Nutzungswunschs */
          ...              /* Nutzung des Betriebsmittels */
          V (available)    /* Anzeige des Nutzungsabschlusses */
          ...

• Einsatz in Kooperationssituationen
  Prozess A enthält einen Programmabschnitt C_I, in dem eine Datenstruktur initialisiert wird, die dann von Prozess B in einem Programmabschnitt C_V verarbeitet wird. Offensichtlich muss C_I unter allen Umständen vor C_V ausgeführt werden. Es wird ein Semaphor in Signalisierungsfunktion eingesetzt:

       Gemeinsam von A und B genutzter Semaphor: inform
       Initialisierung:                          init (inform, 0)
       
       Prozess A           Prozess B
          ...                 ...
          C_I                 P (inform)
          V (inform)          C_V
          ...                 ...

Implementierung

Eine Implementierung der Semaphormechanismen ist konzeptionell im Betriebssystem anzusiedeln, da sie eng mit der Prozessverwaltung zusammenarbeiten muss. Eine Realisierung der Unteilbarkeit auf Monoprozessorsystemen kann dann z. B. mittels Unterbrechungssperre erfolgen. Im Fall von Multiprozessorsystemen ist eine Klammerung der Anweisungsfolgen der Semaphoroperationen durch Spinlocks erforderlich. Eine Realisierung durch das Betriebssystem ermöglicht ferner, dass mehrere Prozesse mit ihren eigentlich disjunkten Adressräumen einen Semaphor gemeinsam nutzen können.

Werden Semaphore von einem Thread-Paket, das im Benutzeradressraum läuft (User-Level-Threads), angeboten, so gestaltet sich die Realisierung der Unteilbarkeit aufwändiger. Sie muss beliebige Unterbrechungen berücksichtigen und hängt davon ab, welche Informationen über User-Level-Threads im Kern vorliegen.

Verwandte Themen

• Mutex - Oberbegriff für Verfahren die wechselseitigen Ausschluss von Datenzugriffen ermöglichen.
• Monitor - ein programmiersprachliches Konzept zur Prozesssynchronisation.
• Jacketing - die Möglichkeit, einen blockierenden Systemaufruf zu umgehen.

Weblinks

Literatur

• Andrew S.Tanenbaum: Moderne Betriebssysteme. Pearson Studium; Auflage: 2., überarb. A. , 2002, ISBN 978-3-8273-7019-8.

Einzelnachweise

1. ↑ The Linux Programmer's Guide: Semaphores: Basic Concepts