Semaphor (Informatik)

Grundidee und Aufgaben

Ein Semaphor ist eine Datenstruktur aus einer Ganzzahl (Zähler) und den atomaren, also unteilbaren Operationen „Reservieren/Probieren“ und „Freigeben“. Es verwaltet beschränkte, zählbare Ressourcen, auf die mehrere Prozesse oder Threads zugreifen, und synchronisiert asynchrone Abläufe.

Der Zähler wird gewöhnlich mit der Zahl der verfügbaren Ressourcen beziehungsweise der maximal gleichzeitig erlaubten Nutzer initialisiert. Reservieren verringert ihn um 1, Freigeben erhöht ihn um 1. Ist keine Ressource frei, muss ein reservierender Prozess warten. Im Unterschied zu Lock oder Mutex müssen der Aktivitätsträger, der reserviert, und derjenige, der freigibt, nicht identisch sein.

Semaphore können Ressourcen wie vier CPU-Kerne verteilen, den Zugriff auf gemeinsame Daten kapseln oder verfügbare Informationspakete zählen. Für letzteren Zweck startet der Semaphor mit „0 Pakete verfügbar“ und wird beim Bereitstellen hochgezählt.

Prozesswechselwirkungen und Synchronisation

Bei parallel oder zeitlich verzahnt ausgeführten Prozessen gibt es implizite und explizite Wechselwirkungen. Implizit ist eine Beeinflussung, die dem Prozess nicht bewusst ist, etwa wenn ein Systemdienst warten muss, weil andere Prozesse Betriebsmittel belegt haben. Dies erscheint als blockierender Funktionsaufruf; der Prozess kann und muss dagegen keine besonderen Vorkehrungen treffen.

Explizite Wechselwirkungen sind Konkurrenz und Kooperation. Konkurrenz liegt vor, wenn Prozesse gleichzeitig auf ein nur begrenzt vorhandenes Betriebsmittel zugreifen wollen und dessen Nutzung exklusiv sein muss, damit keine fehlerhaften Ergebnisse oder inkonsistenten Zustände entstehen. Die betreffenden Programmteile heißen kritische Abschnitte. Kooperation bedeutet, dass Prozesse ihre Aktionen bewusst abstimmen, beispielsweise in einer Auftraggeber-/Auftragnehmerbeziehung.

Reservieren und Freigeben müssen atomar sein. Eine nicht erfüllbare Reservierung kann blockieren, über eine Warteschlange behandelt oder nicht blockierend abgelehnt werden. Bei nur einem Exemplar eines Betriebsmittels sorgt wechselseitiger Ausschluss dafür, dass kritische Abschnitte zeitlich nacheinander ausgeführt werden. Bei Kooperation stellt eine passende Reihenfolge sicher, dass ein Auftragnehmer nicht vor der Auftragserteilung beginnt.

Dijkstras Semaphoroperationen

Edsger W. Dijkstra stellte Semaphore 1965 im Artikel „Cooperating sequential processes“ als Mechanismus der Prozesssynchronisation vor. Ein Semaphor enthält einen Zähler und eine Warteschlange für blockierte Prozesse. Die Initialisierung setzt den Zähler auf einen nicht negativen Wert (≥ 0) und die Warteschlange in der Regel auf leer.

Die Nutzungsoperationen heißen bei Dijkstra P und V. P steht unter anderem für „probeer te verlagen“ (versuche zu senken), V für „verhoog“ (erhöhen). Übliche Schnittstellenbezeichnungen sind für P: wait, acquire oder down; für V: signal, release, post oder up.

Bei P wird der Zähler dekrementiert. Ist er danach größer oder gleich 0, läuft der Prozess weiter. Ist er kleiner als 0, wird der Prozess blockiert und in die Warteschlange eingereiht. Bei V wird der Zähler inkrementiert; ist die Warteschlange nicht leer, wird ein Prozess daraus entblockiert und setzt hinter seinem blockierenden P-Aufruf fort. In dieser Darstellung bedeutet ein positiver Zähler, wie viele P-Aufrufe noch ohne Blockierung möglich sind. Ein negativer Zähler bedeutet mit seinem Absolutwert, wie viele Prozesse blockiert sind.

Es gibt auch Darstellungen, in denen der Zähler nicht negativ wird; die Wirkung auf die Prozesse bleibt gleich. Binäre Semaphore können höchstens den positiven Wert „1“ annehmen und werden oft auch Mutex locks genannt. Zählende Semaphore können größere positive Werte annehmen. Atomarität verhindert Wettlaufsituationen während der Semaphoroperationen. Anders als bei aktivem Warten, etwa mit Spinlocks, wartet ein blockierter Prozess passiv. Starke Semaphore garantieren eine Warteschlange nach dem Windhundprinzip („first come, first served“); schwache Semaphore nicht, etwa wenn im Echtzeitbetrieb Priorität wichtiger als der Blockierungszeitpunkt ist.

Typische Anwendungen

Für Konkurrenz in kritischen Abschnitten verwenden zwei Prozesse A und B einen gemeinsamen binären Semaphor mutex, initialisiert mit init(mutex, 1). Beide führen vor ihrem kritischen Abschnitt P(mutex) und danach V(mutex) aus. Damit befinden sie sich niemals gleichzeitig in ihren kritischen Abschnitten ka_A und ka_B.

Für mehrere gleichartige, begrenzte Betriebsmittel wird ein zählender Semaphor s_available mit init(s_available, n) initialisiert. Ein Prozess führt P(s_available) vor der Nutzung aus und V(s_available) danach. Sind alle n Betriebsmittel belegt, blockiert der nächste Prozess.

Für Kooperation kann Prozess A zuerst in C_I eine Datenstruktur initialisieren und anschließend V(s_inform) ausführen. Der gemeinsame Semaphor s_inform ist mit init(s_inform, 0) initialisiert. Prozess B führt P(s_inform) vor seinem Verarbeitungsabschnitt C_V aus und wartet dadurch, bis A signalisiert hat, dass ein Datensatz verfügbar ist.

Staffelstabmuster und Umsetzung

Das von Gregory R. Andrews vorgeschlagene Passing the Baton Pattern (Staffelstab-Algorithmus) löst Konkurrenz um eine gemeinsame Ressource bei komplexen Bedingungssynchronisationen, beispielsweise bei Prioritätskriterien oder zur Vermeidung von Verhungern. Es gibt für jeden Prozess oder jede Prozessklasse einen privaten Semaphor priv, initialisiert mit 0, sowie einen mutex für wechselseitigen Ausschluss, initialisiert mit 1.

Beim Erwerben sperrt ein Prozess zunächst mutex. Ist seine Zugriffsbedingung nicht erfüllt, wird seine Blockierung erfasst, mutex freigegeben und auf priv[proc_id] gewartet. Beim Freigeben oder nach erfolgreichem Erwerben prüft die Funktion Staffelstab_Weitergeben, ob ein blockierter Prozess die Ressource nun nutzen darf. Falls ja, wird dessen priv-Semaphor signalisiert; andernfalls wird mutex freigegeben. Der „Staffelstab“ wird also höchstens an einen wartenden Prozess weitergegeben.

Semaphormechanismen sind konzeptionell im Betriebssystem angesiedelt, weil sie eng mit der Prozessverwaltung zusammenarbeiten. Auf Monoprozessorsystemen kann die Unteilbarkeit durch Unterbrechungssperre umgesetzt werden, auf Multiprozessorsystemen durch Spinlocks um die Anweisungsfolgen der Semaphoroperationen. Das Betriebssystem ermöglicht außerdem die gemeinsame Nutzung eines Semaphors durch Prozesse mit getrennten Adressräumen. Bei User-Level-Threads im Benutzeradressraum ist die Atomarität aufwändiger zu realisieren, da beliebige Unterbrechungen berücksichtigt werden müssen.