Semaphor (Programmierung) - Semaphore (programming)

Dieser Artikel behandelt den Begriff Computerprogrammierung. Für andere Verwendungen siehe Semaphore (Begriffsklärung) .
Ein Semaphor ( niederländisch : seinpaal , der in Dijkstras Originalbeschreibung verwendete Begriff).

In der Informatik ist ein Semaphor ein variabler oder abstrakter Datentyp, der verwendet wird, um den Zugriff auf eine gemeinsame Ressource durch mehrere Prozesse zu steuern und kritische Abschnittsprobleme in einem gleichzeitigen System wie einem Multitasking- Betriebssystem zu vermeiden . Ein triviales Semaphor ist eine einfache Variable, die abhängig von vom Programmierer definierten Bedingungen geändert (z. B. inkrementiert oder dekrementiert oder umgeschaltet) wird.

Eine nützliche Möglichkeit, sich einen Semaphor, wie er in einem realen System verwendet wird, als Aufzeichnung vorzustellen, wie viele Einheiten einer bestimmten Ressource verfügbar sind, verbunden mit Operationen, um diese Aufzeichnung sicher anzupassen (dh um Wettlaufbedingungen zu vermeiden ) wie Einheiten sind erworben oder frei werden, und warten Sie gegebenenfalls, bis eine Einheit der Ressource verfügbar wird.

Semaphoren sind ein nützliches Werkzeug zur Verhinderung von Wettlaufbedingungen; Ihre Verwendung ist jedoch keine Garantie dafür, dass ein Programm frei von diesen Problemen ist. Semaphoren, die eine beliebige Ressourcenzählung ermöglichen, werden Zählsemaphoren genannt , während Semaphoren, die auf die Werte 0 und 1 beschränkt sind (oder gesperrt/entsperrt, nicht verfügbar/verfügbar), binäre Semaphoren genannt werden und verwendet werden, um Sperren zu implementieren .

Das Semaphor-Konzept wurde 1962 oder 1963 vom niederländischen Informatiker Edsger Dijkstra erfunden , als Dijkstra und sein Team ein Betriebssystem für die Electrologica X8 entwickelten . Dieses System wurde schließlich als DAS Multiprogramming-System bekannt .

Bibliotheksanalogie

Angenommen, eine Bibliothek verfügt über 10 identische Lernräume, die jeweils von einem Studenten genutzt werden können. Studierende müssen an der Rezeption ein Zimmer anfordern, wenn sie einen Studienraum nutzen möchten. Wenn kein Zimmer frei ist, warten Studierende am Schreibtisch, bis jemand ein Zimmer aufgibt. Wenn ein Student die Nutzung eines Zimmers beendet hat, muss der Student zum Schreibtisch zurückkehren und angeben, dass ein Zimmer frei geworden ist.

In der einfachsten Ausführung kennt der Sachbearbeiter an der Rezeption nur die Anzahl der freien Zimmer, die er nur dann richtig kennt, wenn alle Studenten ihr Zimmer während der Anmeldung auch tatsächlich nutzen und sie am Ende wieder zurückgeben . Wenn ein Schüler ein Zimmer anfordert, verringert der Sachbearbeiter diese Zahl. Wenn ein Schüler ein Zimmer freigibt, erhöht der Sachbearbeiter diese Zahl. Der Raum kann beliebig lange genutzt werden, eine Vorreservierung ist daher nicht möglich.

In diesem Szenario stellt der Zählhalter an der Rezeption einen Zählsemaphor dar, die Räume sind die Ressource und die Schüler repräsentieren Prozesse/Threads. Der Wert des Semaphors in diesem Szenario beträgt anfänglich 10, wobei alle Räume leer sind. Wenn ein Schüler einen Raum anfordert, erhält er Zugang und der Wert des Semaphors wird auf 9 geändert. Nachdem der nächste Schüler kommt, sinkt er auf 8, dann 7 und so weiter. Wenn jemand einen Raum anfordert und der aktuelle Wert des Semaphors 0 ist, muss er warten, bis ein Raum freigegeben wird (wenn der Zähler von 0 erhöht wird). Wenn einer der Räume freigegeben wurde, aber mehrere Studenten warten, kann eine beliebige Methode verwendet werden, um denjenigen auszuwählen, der den Raum belegt (wie FIFO oder Münzwurf). Und natürlich muss ein Student den Angestellten erst dann über die Freigabe seines Zimmers informieren, nachdem er es wirklich verlassen hat, sonst kann es zu einer unangenehmen Situation kommen, wenn dieser Student gerade das Zimmer verlässt (sie packen ihre Lehrbücher usw.). und ein anderer Schüler betritt den Raum, bevor sie ihn verlassen.

Wichtige Beobachtungen

Wenn zu steuern den Zugriff auf einen gebrauchten Pool von Ressourcen, nur ein Semaphor Spuren , wie viele Ressourcen sind frei; es verfolgt nicht, welche der Ressourcen frei sind. Ein anderer Mechanismus (möglicherweise mit mehr Semaphoren) kann erforderlich sein, um eine bestimmte freie Ressource auszuwählen.

Das Paradigma ist besonders mächtig, weil die Semaphorenzählung als nützlicher Auslöser für eine Reihe verschiedener Aktionen dienen kann. Der Bibliothekar oben kann das Licht im Studiensaal ausschalten, wenn keine Schüler mehr übrig sind, oder ein Schild anbringen, das besagt, dass die Räume sehr beschäftigt sind, wenn die meisten Räume belegt sind.

Der Erfolg des Protokolls erfordert, dass Anwendungen es korrekt befolgen. Fairness und Sicherheit werden wahrscheinlich gefährdet (was praktisch bedeutet, dass sich ein Programm langsam verhält, unregelmäßig reagiert, hängen bleibt oder abstürzt ), wenn auch nur ein einzelner Prozess falsch handelt. Das beinhaltet:

  • eine Ressource anfordern und vergessen, sie freizugeben;
  • Freigeben einer Ressource, die nie angefordert wurde;
  • eine Ressource für lange Zeit halten, ohne sie zu benötigen;
  • eine Ressource verwenden, ohne sie zuerst anzufordern (oder nach der Freigabe).

Selbst wenn alle Prozesse diesen Regeln folgen, kann es dennoch zu einem Multi-Ressourcen- Deadlock kommen, wenn verschiedene Ressourcen von unterschiedlichen Semaphoren verwaltet werden und wenn Prozesse mehr als eine Ressource gleichzeitig verwenden müssen, wie das Problem der Restaurantphilosophen veranschaulicht .

Semantik und Implementierung

Zählsemaphoren sind mit zwei Operationen ausgestattet, die historisch als P und V bezeichnet wurden (siehe § Operationsnamen für alternative Namen). Die Operation V inkrementiert den Semaphor S und die Operation P dekrementiert ihn.

Der Wert des Semaphors S ist die Anzahl der derzeit verfügbaren Einheiten der Ressource. Die P-Operation verschwendet Zeit oder schläft, bis eine durch den Semaphor geschützte Ressource verfügbar wird, zu welcher Zeit die Ressource sofort beansprucht wird. Die V-Operation ist die Umkehrung: Sie stellt eine Ressource wieder zur Verfügung, nachdem der Prozess ihre Verwendung beendet hat. Eine wichtige Eigenschaft des Semaphors S besteht darin, dass sein Wert nur unter Verwendung der V- und P-Operationen geändert werden kann.

Eine einfache Möglichkeit, Warte- (P) und Signal- (V) Operationen zu verstehen , ist:

  • wait : Verringert den Wert der Semaphor-Variablen um 1. Wenn der neue Wert der Semaphor-Variablen negativ ist, wird der Prozess, der wait ausführt , blockiert (dh der Warteschlange des Semaphors hinzugefügt). Andernfalls setzt der Prozess die Ausführung fort, nachdem er eine Einheit der Ressource verwendet hat.
  • signal : Erhöht den Wert der Semaphor-Variable um 1. Wenn der Wert vor dem Inkrementieren negativ war (dh es warten Prozesse auf eine Ressource), überträgt es einen blockierten Prozess aus der Warteschlange des Semaphors in die Bereit-Warteschlange.

Viele Betriebssysteme stellen effiziente Semaphor-Primitive bereit, die einen wartenden Prozess freigeben, wenn der Semaphor inkrementiert wird. Dies bedeutet, dass Prozesse keine Zeit damit verschwenden, den Semaphorwert unnötig zu überprüfen.

Das Konzept des Zählsemaphors kann um die Fähigkeit erweitert werden, mehr als eine "Einheit" vom Semaphor zu beanspruchen oder zurückzugeben, eine in Unix implementierte Technik . Die modifizierten V- und P-Operationen sind wie folgt, wobei eckige Klammern verwendet werden, um atomare Operationen anzuzeigen , dh Operationen, die aus der Perspektive anderer Prozesse unteilbar erscheinen: 

function V(semaphore S, integer I):
    [S ← S + I]

function P(semaphore S, integer I):
    repeat:
        [if S ≥ I:
        S ← S − I
        break]

Der Rest dieses Abschnitts bezieht sich jedoch auf Semaphoren mit unären V- und P-Operationen, sofern nicht anders angegeben.

Um Hunger zu vermeiden , hat ein Semaphor eine zugehörige Warteschlange von Prozessen (normalerweise mit FIFO- Semantik). Wenn ein Prozess eine P-Operation an einem Semaphor ausführt, der den Wert Null hat, wird der Prozess der Warteschlange des Semaphors hinzugefügt und seine Ausführung wird ausgesetzt. Wenn ein anderer Prozess das Semaphor durch Ausführen einer V-Operation inkrementiert und sich Prozesse in der Warteschlange befinden, wird einer von ihnen aus der Warteschlange entfernt und nimmt die Ausführung wieder auf. Wenn Prozesse unterschiedliche Prioritäten haben, kann die Warteschlange nach Priorität geordnet werden, sodass der Prozess mit der höchsten Priorität zuerst aus der Warteschlange genommen wird.

Wenn die Implementierung keine Atomarität der Inkrement-, Dekrement- und Vergleichsoperationen gewährleistet, besteht die Gefahr, dass Inkremente oder Dekremente vergessen werden oder der Semaphorwert negativ wird. Atomarität kann durch Verwendung eines Maschinenbefehls erreicht werden, der in der Lage ist , den Semaphor in einer einzigen Operation zu lesen, zu modifizieren und zu schreiben . In Abwesenheit eines solchen Hardwarebefehls kann eine atomare Operation durch die Verwendung eines Software-Algorithmus zum gegenseitigen Ausschließen synthetisiert werden . Auf Einprozessorsystemen können atomare Operationen durch vorübergehendes Aussetzen von Preemption oder Deaktivieren von Hardware- Interrupts sichergestellt werden . Dieser Ansatz funktioniert nicht auf Mehrprozessorsystemen, bei denen es möglich ist, dass zwei Programme, die sich einen Semaphor teilen, gleichzeitig auf verschiedenen Prozessoren laufen. Um dieses Problem in einem Mehrprozessorsystem zu lösen, kann eine Sperrvariable verwendet werden, um den Zugriff auf den Semaphor zu steuern. Die Sperrvariable wird unter Verwendung eines Test-and-Set-Lock- Befehls manipuliert .

Beispiele

Triviales Beispiel

Betrachten Sie eine Variable A und eine boolesche Variable S . Auf A wird nur zugegriffen, wenn S als wahr markiert ist. Somit ist S ein Semaphor für A .

Man kann sich ein Ampelsignal ( S ) kurz vor einem Bahnhof ( A ) vorstellen . In diesem Fall, wenn das Signal grün ist, kann man den Bahnhof betreten. Wenn es gelb oder rot (oder eine andere Farbe) ist, ist der Bahnhof nicht zugänglich.

Login-Warteschlange

Betrachten Sie ein System, das nur zehn Benutzer (S=10) unterstützen kann. Immer wenn sich ein Benutzer anmeldet, wird P aufgerufen, wodurch das Semaphor S um 1 dekrementiert wird. Immer wenn sich ein Benutzer abmeldet, wird V aufgerufen, wobei S um 1 erhöht wird, was einen verfügbar gewordenen Login-Slot darstellt. Wenn S 0 ist, müssen alle Benutzer, die sich anmelden möchten, warten, bis S > 0 ist und die Anmeldeanforderung in eine FIFO-Warteschlange eingereiht wird; Der gegenseitige Ausschluss wird verwendet, um sicherzustellen, dass Anfragen der Reihe nach in die Warteschlange gestellt werden. Immer wenn S größer als 0 wird (Anmeldeslots verfügbar), wird eine Anmeldeanforderung aus der Warteschlange entfernt und der Benutzer, der die Anforderung besitzt, darf sich anmelden.

Produzenten-Konsumenten-Problem

Beim Producer-Consumer-Problem erzeugt ein Prozess (der Producer) Datenelemente und ein anderer Prozess (der Consumer) empfängt und verwendet sie. Sie kommunizieren über eine Queue der maximalen Größe N und unterliegen folgenden Bedingungen:

  • der Konsument muss warten, bis der Produzent etwas produziert, wenn die Warteschlange leer ist;
  • der Produzent muss warten, bis der Konsument etwas verbraucht, wenn die Warteschlange voll ist.

Die Semaphorlösung des Producer-Consumer-Problems verfolgt den Zustand der Warteschlange mit zwei Semaphoren: emptyCount, die Anzahl der leeren Stellen in der Warteschlange und fullCount, die Anzahl der Elemente in der Warteschlange. Um die Integrität zu wahren, emptyCountkann sie niedriger (aber nie höher) als die tatsächliche Anzahl leerer Plätze in der Warteschlange und fullCountniedriger (aber nie höher) als die tatsächliche Anzahl der Elemente in der Warteschlange sein. Leere Orte und Gegenstände stellen zwei Arten von Ressourcen dar, leere Kisten und volle Kisten, und die Semaphoren emptyCountund fullCountbehalten die Kontrolle über diese Ressourcen.

Der binäre Semaphor useQueuestellt sicher, dass die Integrität des Zustands der Warteschlange selbst nicht beeinträchtigt wird, beispielsweise durch zwei Produzenten, die gleichzeitig versuchen, einer leeren Warteschlange Elemente hinzuzufügen, wodurch deren interner Zustand beschädigt wird. Alternativ könnte ein Mutex anstelle des binären Semaphors verwendet werden.

Der emptyCountist anfänglich N , fullCountist anfänglich 0 und useQueueist anfänglich 1.

Der Produzent macht wiederholt Folgendes: 

produce:
    P(emptyCount)
    P(useQueue)
    putItemIntoQueue(item)
    V(useQueue)
    V(fullCount)

Der Verbraucher tut Folgendes wiederholt 

consume:
    P(fullCount)
    P(useQueue)
    item ← getItemFromQueue()
    V(useQueue)
    V(emptyCount)

Nachfolgend ein sachliches Beispiel:

  1. Ein einzelner Verbraucher betritt seinen kritischen Abschnitt. Da fullCount0 ist, blockiert der Verbraucher.
  2. Mehrere Produzenten betreten den kritischen Abschnitt des Produzenten. Nicht mehr als N Produzenten dürfen ihren kritischen Abschnitt betreten, da emptyCountihr Zugang eingeschränkt ist.
  3. Die Produzenten erhalten nacheinander Zugriff auf die Warteschlange useQueueund legen Artikel in der Warteschlange ab.
  4. Sobald der erste Produzent seinen kritischen Abschnitt verlässt, fullCountwird inkrementiert, sodass ein Verbraucher seinen kritischen Abschnitt betreten kann.

Beachten Sie, dass emptyCountdies viel niedriger sein kann als die tatsächliche Anzahl leerer Plätze in der Warteschlange, zum Beispiel in dem Fall, in dem viele Produzenten sie verringert haben, aber warten, bis sie angeschaltet sind, useQueuebevor sie leere Plätze füllen. Beachten Sie, dass dies immer gilt, mit Gleichheit, wenn und nur wenn keine Produzenten oder Konsumenten ihre kritischen Abschnitte ausführen. emptyCount + fullCount ≤ N

Vorgangsnamen

Die kanonischen Namen V und P stammen aus den Anfangsbuchstaben niederländischer Wörter. V wird allgemein als verhogen ("Zunahme") erklärt. Für P wurden mehrere Erklärungen angeboten, darunter proberen ("zu testen" oder "versuchen"), passeren ("passieren") und pakken ("greifen"). Dijkstras frühester Aufsatz zu diesem Thema gibt Passering ("Passing") als Bedeutung für P und vrijgave ("Release") als Bedeutung für V an. Er erwähnt auch, dass die Terminologie von der in Eisenbahnsignalen verwendeten stammt. Dijkstra schrieb anschließend, dass er beabsichtigte, P für prolaag zu stehen , kurz für probeer te verlagen , wörtlich "versuchen zu reduzieren", oder parallel zu den im anderen Fall verwendeten Begriffen "versuchen zu verringern".

In ALGOL 68 , dem Linux-Kernel , und in einigen englischen Lehrbüchern werden die V- und P- Operationen up bzw. down genannt . In der Software-Engineering-Praxis werden sie oft als signal and wait , release and Acquire (was die Standard- Java- Bibliothek verwendet) oder post and pend bezeichnet . Einige Texte nennen sie vacate and beschaffen , um den ursprünglichen niederländischen Initialen zu entsprechen.

Semaphoren vs. Mutexe

Ein Mutex ist ein Sperrmechanismus , der manchmal dieselbe grundlegende Implementierung wie das binäre Semaphor verwendet. Die Unterschiede zwischen ihnen liegen in ihrer Verwendung. Während ein binäres Semaphor umgangssprachlich als Mutex bezeichnet werden kann, hat ein echter Mutex einen spezifischeren Anwendungsfall und eine spezifischere Definition, da nur die Aufgabe , die den Mutex gesperrt hat, ihn entsperren soll. Diese Einschränkung zielt darauf ab, einige potenzielle Probleme bei der Verwendung von Semaphoren zu lösen:

  1. Prioritätsumkehr : Wenn der Mutex weiß, wer ihn gesperrt hat und ihn entsperren soll, ist es möglich, die Priorität dieser Aufgabe zu erhöhen, wenn eine Aufgabe mit höherer Priorität beginnt, auf den Mutex zu warten.
  2. Vorzeitige Task-Beendigung: Mutexe können auch Löschsicherheit bieten, wenn die Task, die den Mutex enthält, nicht versehentlich gelöscht werden kann.
  3. Terminierungs-Deadlock: Wenn eine Mutex-haltende Task aus irgendeinem Grund beendet wird, kann das Betriebssystem den Mutex freigeben und wartenden Tasks diesen Zustand signalisieren.
  4. Rekursions-Deadlock: Eine Aufgabe darf einen wiedereintretenden Mutex mehrmals sperren, wenn sie ihn gleich oft entsperrt.
  5. Versehentliche Freigabe: Bei der Freigabe des Mutex wird ein Fehler ausgelöst, wenn die freigebende Aufgabe nicht ihr Besitzer ist.

Siehe auch

Verweise

Externe Links

Einführungen

Verweise