Semaphor (Informatik)

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

Inhaltsverzeichnis

1 Namensherkunft
2 Wechselwirkungen parallel ablaufender Prozesse
3 Lösung von Dijkstra
4 Anwendungsbeispiele
5 Implementierung
6 Siehe auch
7 Weblinks

[Bearbeiten] Namensherkunft

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.

[Bearbeiten] Wechselwirkungen parallel ablaufender Prozesse

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

Bei impliziten Wechselwirkungen ist einem Prozess nicht bewusst, dass eine seiner Aktionen durch die Ausführung von Aktionen anderer Prozesse 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 von einem 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).

[Bearbeiten] 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 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 wie 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 und die Warteschlange i.d.R. auf leer gesetzt.

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

Die Nutzungsoperationen wurden von Dijkstra mit P und V bezeichnet. Dies sind Initialen niederländischer Wörter für Probeer te verlagen / Verhogen (versuchen zu verringern / erhöhen) [1]. 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 Null, 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. Ist der Zähler danach kleiner gleich 0, so wird ein Prozess aus der Warteschlange entfernt. Dieser Prozess setzt dann seine Aktionen mit denen fort, die dem blockierenden P-Aufruf folgen.

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

void V (Semaphor s) {
  s.zaehler = s.zaehler + 1;
  if (s.zaehler <= 0)
     ready (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.

Alle 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 nicht 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 der Gleichartigkeit der Operationen der Vorzug gegeben. Bei Verwendung eines Zählers, der auch negative Werte annimmt, wird verdeutlicht, wie viele Prozesse an dem Semaphor blockiert sind.

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.

[Bearbeiten] 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, m.a.W. es wird 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
          ...                 ...

[Bearbeiten] Implementierung

Eine Implementierung der Semaphormechanismen ist konzeptionell im Betriebssystem anzusiedeln, da sie eng mit der Prozessverwaltung zusammen arbeiten 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 aufwendiger. Sie muss beliebige Unterbrechungen berücksichtigen und hängt davon ab, welche Informationen über User-Level-Threads im Kern vorliegen.