In der Informatik ist ein Semaphor ein variabler oder abstrakter Datentyp, der eine einfache, aber nützliche Abstraktion zur Verfügung stellt, um Zugang durch vielfache Prozesse zu einer allgemeinen Quelle in einer parallelen Programmierumgebung zu kontrollieren.

Eine nützliche Weise, an ein Semaphor zu denken, ist als eine Aufzeichnung dessen, mit wie viel Einheiten einer besonderen Quelle verfügbar, mit Operationen sicher verbunden sind (d. h., ohne Rasse-Bedingungen) passen diese Aufzeichnung an, weil Einheiten erforderlich sind oder frei werden, und nötigenfalls warten, bis eine Einheit der Quelle verfügbar wird. Semaphore sind ein nützliches Werkzeug in der Verhinderung von Rasse-Bedingungen; jedoch ist ihr Gebrauch keineswegs eine Garantie, dass ein Programm von diesen Problemen frei ist. Semaphore, die einer willkürlichen Quellenzählung erlauben, werden genannt, Semaphore aufzählend, während Semaphore, die auf die Werte 0 und 1 eingeschränkt werden (oder hat sich, nicht verfügbar/verfügbar schließen lassen/aufgeschlossen), binäre Semaphore genannt werden (dieselbe Funktionalität, die mutexes haben).

Das Semaphor-Konzept wurde vom holländischen Computerwissenschaftler Edsger Dijkstra erfunden, und das Konzept hat weit verbreiteten Gebrauch in einer Vielfalt von Betriebssystemen gefunden.

Bibliotheksanalogie

Nehmen Sie an, dass eine Bibliothek 10 identische Studienzimmer, beabsichtigt hat, um von einem Studenten auf einmal verwendet zu werden. Um Streite zu verhindern, müssen Studenten um ein Zimmer vom Vorderschalter bitten, wenn sie von einem Studienzimmer Gebrauch machen möchten. Als ein Student beendet hat, ein Zimmer zu verwenden, muss der Student zum Schalter zurückkehren und anzeigen, dass ein Zimmer frei geworden ist. Wenn keine Zimmer frei sind, warten Studenten am Schalter, bis jemand ein Zimmer aufgibt.

Der Bibliothekar am Vorderschreibtisch geht nicht nach, von denen Zimmer, nur die Zahl von freien verfügbaren Zimmern besetzt wird. Wenn ein Student um ein Zimmer bittet, reduziert der Bibliothekar diese Anzahl. Wenn ein Student ein Zimmer veröffentlicht, steigert der Bibliothekar diese Zahl. Sobald der Zugang zu einem Zimmer gewährt wird, kann das Zimmer für, so lange gewünscht, verwendet werden, und so ist es nicht möglich, Zimmer vorzeitig vorzubestellen.

In diesem Drehbuch vertritt der Vorderschreibtisch ein Semaphor, die Zimmer sind die Mittel, und die Studenten vertreten Prozesse. Der Wert des Semaphors in diesem Drehbuch ist am Anfang 10. Wenn ein Student um ein Zimmer bittet, wird ihm oder ihr Zugang gewährt, und der Wert des Semaphors wird zu 9 geändert. Nachdem der folgende Student kommt, fällt es 8, dann 7 und so weiter. Wenn jemand um ein Zimmer bittet und der resultierende Wert des Semaphors negativ ist, werden sie gezwungen zu warten. Wenn vielfache Leute warten, werden sie entweder in einer Warteschlange warten, oder Terminplanung des Gemeinsamen Antrags verwenden und zurück zum Schalter laufen, wenn jemand ein Zimmer (abhängig von Natur des Semaphors) veröffentlicht.

Wichtige Beobachtungen

Wenn verwendet, für eine Lache von Mitteln geht ein Semaphor nicht nach, welcher von den Mitteln nur frei sind, wie viel es gibt. Ein anderer Mechanismus (vielleicht mehr Semaphore einschließend), kann erforderlich sein, eine besondere kostenlose Quelle auszuwählen.

Prozessen wird vertraut, um dem Protokoll zu folgen. Schönheit und Sicherheit werden wahrscheinlich in Verlegenheit gebracht (der praktisch bedeutet, dass sich ein Programm langsam benehmen, unregelmäßig handeln, hängen oder abstürzen kann), wenn sogar ein einzelner Prozess falsch handelt. Das schließt ein:

• die Anforderung einer Quelle und das Vergessen, es zu veröffentlichen
• die Ausgabe einer Quelle, die nie gebeten wurde
• das Halten einer Quelle seit langem, ohne es zu brauchen
• das Verwenden einer Quelle, ohne darum zuerst zu bitten.

Selbst wenn alle Prozesse diesen Regeln folgen, kann toter Mehrquellenpunkt noch vorkommen, wenn es verschiedene Mittel gibt, die durch verschiedene Semaphore geführt sind, und wenn Prozesse mehr als eine Quelle auf einmal, wie illustriert, durch das Speisenphilosoph-Problem verwenden müssen.

Semantik und Durchführung

Ein wichtiges Eigentum dieser Semaphor-Variablen besteht darin, dass ihr Wert außer durch das Verwenden des Wartens und Signal Funktionen nicht geändert werden kann.

Zählen-Semaphore werden mit zwei Operationen ausgestattet, haben historisch als V (auch bekannt als Signal ) und P angezeigt (oder warten Sie ) (sieh unten). Operation V Zunahme das Semaphor S und die Operation P Verminderung es. Die Semantik dieser Operationen wird unten gezeigt. Eckige Klammern werden verwendet, um Atomoperationen, d. h., Operationen anzuzeigen, die unteilbar von der Perspektive anderer Prozesse scheinen.

Der Wert des Semaphors S ist die Zahl von Einheiten der Quelle, die zurzeit verfügbar sind. Die P Operation verschwendet Zeit oder schläft, bis eine durch das Semaphor geschützte Quelle verfügbar wird, an der Zeit die Quelle sofort gefordert wird. Die V Operation ist das Gegenteil: Es stellt eine Quelle wieder bereit, nachdem der Prozess beendet hat, es zu verwenden.

Eine einfache Weise zu verstehen wartet und Signal Operationen sind:

• : Verminderung der Wert der Semaphor-Variable durch 1. Wenn der Wert negativ wird, die Prozess-Durchführung warten wird blockiert, d. h., zur Warteschlange des Semaphors hinzugefügt.
• : Erhöht den Wert der Semaphor-Variable durch 1. Nach der Zunahme, wenn der Wert negativ war (Bedeutung gibt von ihm Prozesse, die auf eine Quelle warten), überträgt sie einen blockierten Prozess von der Warteschlange des Semaphors zur bereiten Warteschlange.

Viele Betriebssysteme stellen effiziente Semaphor-Primitive zur Verfügung, die einen Warten-Prozess frei machen, wenn das Semaphor erhöht wird. Das bedeutet, dass Prozesse nicht Zeit verschwenden, den Semaphor-Wert unnötigerweise überprüfend.

Das Zählen-Semaphor-Konzept kann mit der Fähigkeit erweitert werden, mehr als eine "Einheit" vom Semaphor, eine in UNIX durchgeführte Technik zu fordern oder zurückzugeben. Das modifizierte V und die P Operationen sind wie folgt:

fungieren Sie V (Semaphor S, ganze Zahl I):

[S  S + ICH]

fungieren Sie P (Semaphor S, ganze Zahl I):

Wiederholung:

[wenn S> = ich:

S  S - ICH

Brechung]

Um Verhungern zu vermeiden, hat ein Semaphor eine verbundene Warteschlange von Prozessen (gewöhnlich ein erster - in, zuerst). Wenn ein Prozess eine P Operation auf einem Semaphor durchführt, das die Wertnull hat, wird der Prozess zur Warteschlange des Semaphors hinzugefügt. Wenn ein anderer Prozess das Semaphor durch das Durchführen einer V Operation erhöht, und es Prozesse auf der Warteschlange gibt, wird einer von ihnen von der Warteschlange entfernt und setzt Ausführung fort. Wenn Prozesse verschiedene Prioritäten haben, kann der Warteschlange durch den Vorrang befohlen werden, so dass der höchste Vorzugsprozess von der Warteschlange zuerst genommen wird.

Wenn die Durchführung atomicity der Zunahme, Verminderung und Vergleich-Operationen nicht sichert, dann gibt es eine Gefahr der Zunahme oder Verminderung, die, oder vom Semaphor-Wert wird vergisst, der negativ wird. Atomicity kann durch das Verwenden einer Maschineninstruktion erreicht werden, die im Stande ist, das Semaphor in einer einzelnen Operation zu lesen, zu modifizieren und zu schreiben. Ohne solch eine Hardware-Instruktion kann eine Atomoperation durch den Gebrauch einer Software gegenseitiger Ausschluss-Algorithmus synthetisiert werden. Auf uniprocessor Systemen können Atomoperationen gesichert werden, indem sie Vorkaufsrecht provisorisch aufgehoben wird oder Hardware-Unterbrechungen unbrauchbar gemacht wird. Diese Annäherung arbeitet an Mehrverarbeiter-Systemen nicht, wo es für zwei Programme möglich ist, die ein Semaphor teilen, auf verschiedenen Verarbeitern zur gleichen Zeit zu laufen. Um dieses Problem in einem Mehrverarbeiter-System zu beheben, kann eine sich schließen lassende Variable verwendet werden, um Zugang zum Semaphor zu kontrollieren. Die sich schließen lassende Variable wird mit einem Test manipuliert und hat Schloss (TSL) Befehl gesetzt.

Beispiel: Problem des Erzeugers/Verbrauchers

Im Produktions-Verbraucherproblem erzeugt ein Prozess (der Erzeuger) Datensachen, und ein anderer Prozess (der Verbraucher) erhält und verwendet sie. Sie teilen das Verwenden einer Warteschlange der maximalen Größe N mit. Offensichtlich muss der Verbraucher auf den Erzeuger warten, um etwas zu erzeugen, wenn die Warteschlange leer ist. Vielleicht subtiler muss der Erzeuger auf den Verbraucher warten, um etwas zu verbrauchen, wenn der Puffer voll ist.

Das Problem wird leicht behoben, wenn wir die Warteschlange als eine Reihe von Kästen modellieren, die entweder leer oder voll sind, und leere Kästen als ein Typ der Quelle und vollen Kästen als ein anderer Typ der Quelle betrachten. Der Erzeuger "entfernt" einen leeren Kasten und "schafft" dann einen vollen, während der Verbraucher die Rückseite tut.

Vorausgesetzt, dass und Semaphore aufzählen, und am Anfang N ist, während am Anfang 0 ist, tut der Erzeuger das folgende wiederholt:

erzeugen Sie:

P (emptyCount)

putItemIntoQueue (Artikel)

V (fullCount)

Der Verbraucher tut das folgende wiederholt:

verzehren Sie sich:

P (fullCount)

Artikel  getItemFromQueue

V (emptyCount)

Gewöhnlich werden entweder fullCount oder emptyCount auf 1, mit dem anderen Satz zu 0 gesetzt. Der Erzeuger oder Verbraucher, der zuerst geht, werden Verminderung der P zu 0, und nach seiner kritischen Abteilung schätzen, es wird den V Wert zu 1 erhöhen. Auf der zweiten Wiederholung wird es auf dem P blockieren, seitdem es es auf 0 nach dem Ergreifen davon das erste Mal gesetzt hat, und der andere Prozess laufen wird, das erste ebenso veröffentlichend, sobald es den V Befehl am Ende schlägt.

Es ist wichtig zu bemerken, dass die Ordnung von Operationen notwendig ist. Zum Beispiel, wenn der Erzeuger den Artikel in die Warteschlange nach dem Erhöhen fullCount legt, kann der Verbraucher den Artikel erhalten, bevor es geschrieben worden ist. Wenn der Erzeuger den Artikel in die Warteschlange legt, bevor decrementing emptyCount der Erzeuger die Größe-Grenze der Warteschlange überschreiten könnte.

Funktionsnamenetymologie

Die kanonischen Namen P und V kommen aus den Initialen von holländischen Wörtern. V tritt für verhogen ("Zunahme") ein. Mehrere Erklärungen sind für P, einschließlich proberen für angeboten worden, "um," passeer für "den Pass", Pro-Bier für "den Versuch" und pakken für "den Griff" zu prüfen. Jedoch hat Dijkstra geschrieben, dass er beabsichtigt hat, dass P, um für den Handkoffer prolaag, kurz für Pro-Bier te verlagen wörtlich einzutreten, "versuchen, abzunehmen," oder den im anderen Fall gebrauchten Begriffen anzupassen, "versuchen Sie abzunehmen." Diese Verwirrung stammt von der Tatsache, dass die Wörter für die Zunahme und Abnahme sowohl mit dem Brief V in Niederländisch beginnen, als auch die Wörter dargelegt würden vollständig für diejenigen unmöglich verwirrend sein, die mit der holländischen Sprache nicht vertraut sind.

Im Algol 68 wird der Kern von Linux, und in einigen englischen Lehrbüchern, dem P und den V Operationen beziehungsweise unten und genannt. In der Softwaretechnikpraxis werden sie häufig genannt warten und geben Zeichen, erwerben und veröffentlichen (den die javanische Standardbibliothek verwendet), oder pend und Posten. Einige Texte nennen sie beschaffen und machen frei, um die ursprünglichen holländischen Initialen zu vergleichen.

Semaphor gegen mutex

Ein mutex ist im Wesentlichen dasselbe Ding wie ein binäres Semaphor, und verwendet manchmal dieselbe grundlegende Durchführung. Jedoch wird der Begriff "mutex" gebraucht, um eine Konstruktion zu beschreiben, die zwei Prozesse davon abhält, dasselbe Stück des Codes durchzuführen, oder auf dieselben Daten zur gleichen Zeit zuzugreifen. Der Begriff "binäres Semaphor" wird gebraucht, um eine Konstruktion zu beschreiben, die Zugang zu einer einzelnen Quelle beschränkt.

In vielen Fällen hat ein mutex ein Konzept eines "Eigentümers": Der Prozess, der den mutex geschlossen hat, ist der einzige Prozess, der erlaubt ist, ihn aufzuschließen. Im Gegensatz haben Semaphore allgemein diese Beschränkung, etwas nicht, wovon das Produktions-Verbraucherbeispiel oben abhängt.

Siehe auch

• Zigarettenraucher-Problem
• Speisenphilosoph-Problem
• Problem der Leser-Schriftsteller
• Das Schlafen des Friseur-Problems
• Produktions-Verbraucherproblem
• Mutex
• Einspringender mutex, der "zählen" kann, aber auf eine verschiedene Weise zu einem Zählen-Semaphor.
• Asynchrones Semaphor
• Monitor

Zeichen und Verweisungen

Außenverbindungen

• , Dijkstra führt das Konzept (in Niederländisch) ein
• semaphore.h, der Schnittstelle - Die Grundspezifizierungsausgabe 6 von Open Group, IEEE Std 1003.1 programmiert
• Das kleine Buch von Semaphoren Allen B. Downey
• Ein pragmatischer, historisch orientierter Überblick auf der Allgemeinheit von Synchronisationsprimitiven, Jouni Leppäjärvi