Semaphor (Informatik)

Semaphor (Informatik)

Ein Semaphor ist eine Datenstruktur, die aus einer Ganzzahl und den Nutzungsoperationen „Reservieren/Probieren“ und „Freigeben“ besteht. Sie dient der Verwaltung beschränkter (zählbarer) Ressourcen, auf die mehrere Prozesse oder Threads zugreifen können.

Inhaltsverzeichnis

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 freigegeben hat. Es gibt auch Implementierungen, die ins Negative zählen, „wie viele Interessenten aktuell 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; 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.[1] Die dort verwendeten Semaphore zeigen an, ob ein Zug eine Ressource belegen, also einen Gleisabschnitt befahren 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.

Reservieren und Freigeben müssen beide 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:

 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 (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 und verhoog.[2] 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 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 binäre Semaphore bezeichnet (wechselseitiger Ausschluss). Semaphore, deren Zähler größere positive Werte annehmen können (größer als "1"), werden zählende Semaphore genannt.

Beide Operationen müssen unteilbare Aktionen sein ("atomar"). 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 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)  /* Es gibt 1 Ressourcen-Exemplar "Recht auf Betreten eines kritischen Abschnitts" (k.A.) */
       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" */
          ...              ...
  • 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: 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 ("1 Datensatz verfügbar") hochgezählt hat.

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. 2. Auflage. Pearson Studium, München 2002, ISBN 978-3-8273-7019-8.

Einzelnachweise

  1. The Linux Programmer's Guide: Semaphores: Basic Concepts
  2. [1] E. W. Dijkstra Archive (niederländisch)

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Semaphor — Ein Semaphor (sächlich oder männlich, in Österreich nur männlich, von griechisch σήμα sema „Zeichen“ und φερειν pherein „tragen“) ist allgemein ein Signalmast oder ein Winksignal. Weitere Bedeutungen: Optischer Telegraf, ein optisches Signal zur… …   Deutsch Wikipedia

  • Monitor (Informatik) — Ein Monitor in der Informatik ist ein programmiersprachliches Konzept zur Synchronisation von Zugriffen zeitlich verschränkt oder parallel laufender Prozesse oder Threads auf gemeinsam genutzten Datenstrukturen oder Ressourcen. Inkonsistente… …   Deutsch Wikipedia

  • Gegenseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Wechselseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Producer-Consumer-Problem — Das Erzeuger Verbraucher Problem ist eine klassische, abstrakt formulierte Problemstellung der Prozesssynchronisation, welche eine Regelung der Zugriffsreihenfolge auf eine Datenstruktur durch elementerzeugende (schreibende) und… …   Deutsch Wikipedia

  • Interprozeßkommunikation — Unter Interprozesskommunikation (englisch inter process communication, IPC) versteht man Methoden zum Informationsaustausch, informatisch gesprochen Datenübertragung, von nebenläufigen Prozessen oder Threads. Im engeren Sinne versteht man unter… …   Deutsch Wikipedia

  • Atomere Befehlsfolge — In der Informatik bezeichnet atomarer Befehl oder atomare Befehlsfolge einen Befehl oder Befehle, die durch andere Befehle nicht unterbrochen werden können. Bei interruptunterstützenden Prozessoren muss dabei während der Ausführung der atomaren… …   Deutsch Wikipedia

  • Laufbedingung — Dieser Artikel erläutert Race Condition in der Informatik, für die Race Condition in der Elektronik siehe Glitch (Elektronik). Als Race Condition oder Race Hazard (deutsch: Wettlaufsituation) werden in der Programmierung Konstellationen… …   Deutsch Wikipedia

  • Race-Condition — Dieser Artikel erläutert Race Condition in der Informatik, für die Race Condition in der Elektronik siehe Glitch (Elektronik). Als Race Condition oder Race Hazard (deutsch: Wettlaufsituation) werden in der Programmierung Konstellationen… …   Deutsch Wikipedia

  • Race Hazard — Dieser Artikel erläutert Race Condition in der Informatik, für die Race Condition in der Elektronik siehe Glitch (Elektronik). Als Race Condition oder Race Hazard (deutsch: Wettlaufsituation) werden in der Programmierung Konstellationen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”