Semaphor (Informatik)

Ein Semaphor (von altgriechisch σῆμα sēma, deutsch ‚Zeichen‘ und φέρειν pherein ‚tragen‘ – also etwa „Signalgeber“) ist eine Datenstruktur, die aus einer Ganzzahl und den atomaren Nutzungsoperationen „Reservieren/Probieren“ und „Freigeben“ besteht. Sie eignet sich insbesondere zur Verwaltung beschränkter (zählbarer) Ressourcen, auf die mehrere Prozesse oder Threads zugreifen sollen, wie etwa Erzeuger und Verbraucher, sowie zur Koordination asynchroner Abläufe. Im Gegensatz zu einem Lock bzw. einem Mutex müssen die Aktivitätsträger, die „reservieren“ und „freigeben“, nicht identisch sein.

Funktionsweise

Meist wird die Ganzzahl (Zähler) beim Start des Semaphors mit dem Zahlenwert der maximal verfügbaren Ressourcen initialisiert bzw. der maximalen Zahl der Prozesse, die gleichzeitig die Ressource nutzen können. Ein Prozess, der auf die Ressource zugreifen will, muss vorher die Operation „Reservieren/Probieren“ aufrufen, und danach, wenn er die Ressource nicht mehr benötigt, die Operation „Freigeben“. Bei jeder Reservierung wird der Zähler um 1 heruntergezählt, bei Freigabe wird er wieder um 1 erhöht. Der Zähler darf nicht unter 0 fallen: Wenn eine Reservierung bei Zählerstand 0 erfolgt, wartet der reservierende Prozess, bis ein anderer Prozess Ressourcen freigegeben hat. Es gibt auch Implementierungen, die ins Negative zählen. Damit kann angezeigt werden, wie viele Prozesse auf eine Freigabe warten.

Semaphore können bei der Programmierung zur Prozesssynchronisation eingesetzt werden, also zur Lösung von Aufgaben, bei denen die parallele Ausführung mehrerer Prozesse/Threads eine zeitliche Abstimmung der Ausführungen erfordert. Sie dienen im Allgemeinen dazu, bei einer beschränkten Anzahl von Ressourcen eine Reihenfolge herzustellen, in der viele Threads sich diese knappen Elemente teilen (z. B. Ressource: „CPU-Kern“, Anzahl: 4). Dies kann auch zur Kapselung von Zugriffen auf gemeinsame Daten verwendet werden (Ressource: „Zugriffsrecht auf die Daten“, Anzahl: immer nur einer gleichzeitig). Auch zur Kommunikation zwischen Threads können Semaphore verwendet werden. Sie dienen dann meist als Zähler für verfügbare Informationspakete. Hierbei wird der Semaphor mit „0 Pakete verfügbar“ gestartet, und dann hochgezählt (und wieder bis auf 0 herunter).

Namensherkunft

Verlassenes Eisenbahnsignal (Semaphor)

Das Wort Semaphor geht auf die Formsignale mechanischer Eisenbahnsignale zurück. Die dort verwendeten Semaphore zeigen an, ob ein Zug eine Ressource belegt, also ob ein Gleisabschnitt befahren werden darf oder 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 bei dem die Nutzung eines Exemplars 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.

Sowohl das Reservieren als auch das Freigeben müssen atomare Operationen sein. Kann eine Reservierung nicht befriedigt werden, so kann sie einfach blockieren (Erlangung der Ressource via Race Condition unter den Wartenden), der Semaphor eine Warteschlange führen (i. A. blockierend) oder ablehnen (nicht blockierend). Häufig ist vom Betriebsmittel nur ein Exemplar vorhanden (sog. wechselseitiger Ausschluss), der Semaphor bewirkt dann eine Abstimmung der zeitlichen Ausführung der Prozessaktionen. Im Fall einer Konkurrenzsituation wird durch eine irgendwie gestaltete Sequentialisierung der Ausführung (der kritischen Abschnitte) erreicht, dass das Betriebsmittel nicht von mehreren Prozessen beliebig verändernd benutzt wird. 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 versucht anzufangen 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 (hier ein Beispiel in C):

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

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 Wechselwirkungssituationen von Prozessen durch Zählen
• 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(s->queue);
 }

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 (siehe Anwendungsbeispiele).

Die Nutzungsoperationen wurden von Dijkstra mit P und V bezeichnet. Dies sind Initialen niederländischer Wörter bzw. Kofferwörter für prolaag (probeer te verlagen = versuche zu senken) und verhoog. Weitere, verbreitete Erklärungen sind passeer (passieren), proberen (überprüfen) und vrijgeven (freigeben), verhogen (erhöhen). Programmierschnittstellen verwenden mnemonisch deutlichere Bezeichnungen wie wait (warten), acquire (erlangen) oder down (unten) für die P-Operation und signal (signalisieren), release (freigeben), post (abschicken) oder up (oben) 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 Semaphorzähler kleiner als 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.

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

/* up() */
 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 eine "1" als größten positiven Wert annehmen können, werden oftmals auch als binäre Semaphore bzw. Mutex locks bezeichnet. Semaphore, deren Zähler größere positive Werte als "1" annehmen können, werden zählende Semaphore genannt.

Beide Operationen müssen unteilbare, atomare 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 Darstellungen nimmt der Zähler keine negativen Werte an. (Der oben beschriebene Zählerwert ergibt sich, indem man vom Tatsächlichen die Länge der Warteschlange subtrahiert.) 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

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)  /* Es gibt 1 Ressourcen-Exemplar "Recht auf Betreten eines kritischen Abschnitts" */

Prozess A           Prozess B
...                 ...
P (mutex) P (mutex) /* versuche "Betreten-Recht" zu reservieren (blockierend) */
ka_A                ka_B
V (mutex) V (mutex) /* freigeben des "Betreten-Rechts" */
...                 ...

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: s_available
Initialisierung: init (s_available, n)

Prozess
...
P (s_available) /* Anzeige des Nutzungswunschs; warte bis "für mich reserviert wurde" */
... /* Nutzung des Betriebsmittels */
V (s_available) /* Anzeige des Nutzungsabschlusses, freigeben */
...

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: s_inform
Initialisierung: init (s_inform, 0)

Prozess A           Prozess B
...                 ...
C_I                 P (s_inform)
V (s_inform) C_V
...                 ...

Prozess B versucht zu reservieren und muss warten, bis Prozess A mittels Freigabe s_inform auf 1 (Datensatz verfügbar) hochgezählt hat.

Passing the Baton Pattern

Das von Gregory R. Andrews vorgeschlagene Passing the Baton Pattern (deutsch: Staffelstab-Algorithmus) ist ein allgemeines Schema zur Lösung vieler generischer Programmierprobleme, bei denen mehrere nebenläufige Prozesse um dieselbe Ressource mit komplexen Bedingungssynchronisationen konkurrieren, z. B. Erfüllung bestimmter Prioritätskriterien oder Vermeidung von Verhungern. Bei einer gemeinsam genutzten Ressource erfordert das Pattern eine private Semaphore priv (initialisiert auf 0) für jeden beteiligten Prozess oder jede Klasse von Prozessen und eine einzige Semaphore mutex für den gegenseitigen Ausschluss (initialisiert auf 1).

Der Pseudocode für jeden Prozess lautet:

void Prozess(int proc_id, int res_id)
{
	Ressource_Erwerben(proc_id, res_id);
	
	<Die Ressource res_id benutzen>;
	
	Ressource_Freigeben(proc_id, res_id);
}

Die Funktionen für das Erwerben und Freigeben der Ressource sind wie folgt aufgebaut:

void Ressource_Erwerben(int proc_id, int res_id)
{
	P(mutex);
	
	if (<die Bedingung für den Zugriff auf res_id ist nicht erfüllt für proc_id>)
	{
		<erfassen, dass proc_id für res_id blockiert ist>;
		V(mutex);
		P(priv[proc_id]);
		<erfassen, dass proc_id für res_id nicht mehr blockiert ist>;
	}
	
	<erfassen, dass proc_id auf res_id zugreift>;
	
	Staffelstab_Weitergeben(proc_id, res_id); // siehe unten
}

void Ressource_Freigeben(int proc_id, int res_id)
{
	P(mutex);
	
	<erfassen, dass proc_id auf res_id nicht mehr zugreift>;
	
	Staffelstab_Weitergeben(proc_id, res_id); // siehe unten
}

Beide Operationen verwenden die Funktion Staffelstab_Weitergeben:

void_Staffelstab_Weitergeben(int proc_id, int res_id)
{
	if <die Bedingung für den Zugriff auf res_id ist von mindestens einem blockierten Prozess erfüllt>
	{
		int p = <Wahl eines blockierten Prozesses um ihn zu reaktivieren>;
		V(priv[p]);
	}
	else
	{
		V(mutex);
	}
}

Anmerkungen:

Das Pattern wird Passing the Baton genannt, weil ein Prozess, der die Ressource freigibt, sowie ein frisch reaktivierter Prozess höchstens einen anderen angehaltenen Prozess aktiviert, d. h. sozusagen "den Staffelstab an ihn weitergibt". Die mutex Semaphore wird nur dann freigegeben, wenn ein Prozess sich selbst blockiert (während der Funktion Ressource_Erwerben) oder wenn es innerhalb der Operation Staffelstab_Weitergeben nicht möglich ist, einen anderen blockierten Prozess zu reaktivieren.

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.
• Bolt-Variable – Variante des Semaphors zur flexibleren Realisierung eines Read-Write-Lock.

Literatur

• Andrew S. Tanenbaum: Moderne Betriebssysteme (= Pearson Studium – IT). Dritte aktualisierte Auflage. Addison-Wesley Verlag, 2009, ISBN 978-3-8273-7342-7, S. 1248 (englisch, Originaltitel: Modern Operating Systems.). 
• James H. Anderson, Yong-Jik Kim, Ted Herman: Shared-memory mutual exclusion: major research trends since 1986. In: Distrib. Comput. Band 16, Nr. 2–3. Springer-Verlag, September 2003, ISSN 0178-2770, S. 75–110, doi:10.1007/s00446-003-0088-6. 
• M. Raynal, D. Beeson: Algorithms for mutual exclusion. MIT Press, Cambridge MA 1986, ISBN 0-262-18119-3. 

Weblinks

• Implementierung von Semaphoren in FreeBSD, Kernel
• Implementierung von Semaphoren in FreeBSD, API
• Schnittstellenspezifikation bzw. API über Semaphoren in FreeBSD
• sem_init(3)
• sem_post(3)
• sem_wait(3)
• sem_getvalue(3)
• sem_destroy(3)
• sem(4)