Was ist ein Semaphor?

Ein Semaphor ist ein Programmierkonzept, das häufig zur Lösung von Multithreading-Problemen verwendet wird. Meine Frage an die Community:

Was ist ein Semaphor und wie benutzt man es?

Stellen Sie sich Semaphoren als Türsteher in einem Nachtclub vor. Es gibt eine bestimmte Anzahl von Personen, die gleichzeitig im Club zugelassen sind. Wenn der Club voll ist, darf niemand eintreten, aber sobald eine Person den Club verlässt, kann eine andere Person eintreten.

Dies ist einfach eine Möglichkeit, die Anzahl der Verbraucher für eine bestimmte Ressource zu begrenzen. Zum Beispiel, um die Anzahl gleichzeitiger Aufrufe einer Datenbank in einer Anwendung zu begrenzen.

Hier ist ein sehr pädagogisches Beispiel in C # :-)

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace TheNightclub
{
    public class Program
    {
        public static Semaphore Bouncer { get; set; }

        public static void Main(string[] args)
        {
            // Create the semaphore with 3 slots, where 3 are available.
            Bouncer = new Semaphore(3, 3);

            // Open the nightclub.
            OpenNightclub();
        }

        public static void OpenNightclub()
        {
            for (int i = 1; i <= 50; i++)
            {
                // Let each guest enter on an own thread.
                Thread thread = new Thread(new ParameterizedThreadStart(Guest));
                thread.Start(i);
            }
        }

        public static void Guest(object args)
        {
            // Wait to enter the nightclub (a semaphore to be released).
            Console.WriteLine("Guest {0} is waiting to entering nightclub.", args);
            Bouncer.WaitOne();          

            // Do some dancing.
            Console.WriteLine("Guest {0} is doing some dancing.", args);
            Thread.Sleep(500);

            // Let one guest out (release one semaphore).
            Console.WriteLine("Guest {0} is leaving the nightclub.", args);
            Bouncer.Release(1);
        }
    }
}

Der Artikel Mutexes and Semaphores Demystified von Michael Barr ist eine großartige kurze Einführung in das, was Mutexes und Semaphoren unterscheidet und wann sie verwendet werden sollten und wann nicht. Ich habe hier einige wichtige Absätze extrahiert.

Der entscheidende Punkt ist, dass Mutexe zum Schutz gemeinsam genutzter Ressourcen verwendet werden sollten, während Semaphore zur Signalisierung verwendet werden sollten. Sie sollten im Allgemeinen keine Semaphoren zum Schutz gemeinsam genutzter Ressourcen oder Mutexe zur Signalisierung verwenden. Es gibt beispielsweise Probleme mit der Bouncer-Analogie hinsichtlich der Verwendung von Semaphoren zum Schutz gemeinsam genutzter Ressourcen. Sie können sie auf diese Weise verwenden, es kann jedoch schwierig sein, Fehler zu diagnostizieren.

Während Mutexe und Semaphore einige Ähnlichkeiten in ihrer Implementierung aufweisen, sollten sie immer unterschiedlich verwendet werden.

Die häufigste (aber dennoch falsche) Antwort auf die oben gestellte Frage ist, dass Mutexe und Semaphoren sehr ähnlich sind, mit dem einzigen signifikanten Unterschied, dass Semaphoren höher als eins zählen können. Fast alle Ingenieure scheinen richtig zu verstehen, dass ein Mutex ein binäres Flag ist, das zum Schutz einer gemeinsam genutzten Ressource verwendet wird, indem der gegenseitige Ausschluss in kritischen Codeabschnitten sichergestellt wird. Auf die Frage, wie ein "Zählsemaphor" verwendet werden soll, äußern die meisten Ingenieure - die sich nur in ihrem Vertrauensgrad unterscheiden - die Meinung des Lehrbuchs, dass diese zum Schutz mehrerer gleichwertiger Ressourcen verwendet werden.

...

An dieser Stelle wird eine interessante Analogie hergestellt, bei der die Idee von Badschlüsseln als Schutz für gemeinsam genutzte Ressourcen verwendet wird - das Badezimmer. Wenn ein Geschäft über ein einziges Badezimmer verfügt, reicht ein einziger Schlüssel aus, um diese Ressource zu schützen und zu verhindern, dass mehrere Personen sie gleichzeitig nutzen.

Wenn es mehrere Badezimmer gibt, könnte man versucht sein, sie gleichermaßen zu verschlüsseln und mehrere Schlüssel herzustellen - dies ähnelt einem Semaphor, das missbraucht wird. Sobald Sie einen Schlüssel haben, wissen Sie nicht mehr, welches Badezimmer verfügbar ist. Wenn Sie diesen Weg beschreiten, werden Sie wahrscheinlich Mutexe verwenden, um diese Informationen bereitzustellen, und sicherstellen, dass Sie kein Badezimmer nehmen, das bereits belegt ist .

Ein Semaphor ist das falsche Werkzeug, um mehrere der im Wesentlichen gleichen Ressourcen zu schützen, aber so viele Menschen denken darüber nach und verwenden es. Die Bouncer-Analogie unterscheidet sich deutlich: Es gibt nicht mehrere Ressourcen derselben Art, sondern eine Ressource, die mehrere gleichzeitige Benutzer aufnehmen kann. Ich nehme an, ein Semaphor kann in solchen Situationen verwendet werden, aber es gibt selten Situationen in der realen Welt, in denen die Analogie tatsächlich gilt - es gibt häufiger mehrere vom gleichen Typ, aber immer noch individuelle Ressourcen, wie die Badezimmer, die nicht verwendet werden können diesen Weg.

...

Die korrekte Verwendung eines Semaphors dient zur Signalisierung von einer Aufgabe zur anderen. Ein Mutex soll von jeder Aufgabe, die die von ihm geschützte gemeinsam genutzte Ressource verwendet, immer in dieser Reihenfolge verwendet und freigegeben werden. Im Gegensatz dazu signalisieren oder warten Aufgaben, die Semaphoren verwenden, nicht beide. Beispielsweise kann Task 1 Code zum Posten (dh Signalisieren oder Inkrementieren) eines bestimmten Semaphors enthalten, wenn die "Power" -Taste gedrückt wird, und Task 2, der die Anzeige aktiviert, hängt an demselben Semaphor. In diesem Szenario ist eine Aufgabe der Erzeuger des Ereignissignals. der andere der Verbraucher.

...

Hier wird ein wichtiger Punkt hervorgehoben, dass Mutexe Echtzeit-Betriebssysteme auf schlechte Weise stören und eine Prioritätsumkehr verursachen, bei der eine weniger wichtige Aufgabe aufgrund der gemeinsamen Nutzung von Ressourcen vor einer wichtigeren Aufgabe ausgeführt werden kann. Kurz gesagt, dies geschieht, wenn eine Aufgabe mit niedrigerer Priorität einen Mutex verwendet, um eine Ressource A abzurufen, und dann versucht, B abzurufen, aber angehalten wird, weil B nicht verfügbar ist. Während es wartet, kommt eine Aufgabe mit höherer Priorität und benötigt A, aber es ist bereits gebunden und durch einen Prozess, der nicht einmal ausgeführt wird, weil er auf B wartet. Es gibt viele Möglichkeiten, dies zu lösen, aber es wird meistens behoben durch Ändern des Mutex und des Task-Managers. Der Mutex ist in diesen Fällen viel komplexer als ein binäres Semaphor.

...

Die Ursache für die weit verbreitete moderne Verwechslung zwischen Mutexen und Semaphoren ist historisch, da sie bis zur Erfindung des Semaphors (Hauptstadt "S" in diesem Artikel) durch Djikstra im Jahr 1974 zurückreicht. Vor diesem Datum war keiner der den Informatikern bekannten Interrupt-sicheren Task-Synchronisations- und Signalisierungsmechanismen für die Verwendung durch mehr als zwei Tasks effizient skalierbar. Dijkstras revolutionäres, sicheres und skalierbares Semaphor wurde sowohl beim Schutz kritischer Abschnitte als auch beim Signalisieren angewendet. Und so begann die Verwirrung.

Später wurde es den Entwicklern von Betriebssystemen jedoch nach dem Erscheinen des prioritätsbasierten präventiven RTOS (z. B. VRTX, ca. 1980), der Veröffentlichung von wissenschaftlichen Arbeiten zur Einrichtung von RMA und den durch die Prioritätsumkehr verursachten Problemen sowie einer Arbeit zur Priorität klar Vererbungsprotokolle im Jahr 1990 3 wurde deutlich, dass Mutexe mehr als nur Semaphoren mit einem binären Zähler sein müssen.

Mutex: gemeinsame Nutzung von Ressourcen

Semaphor: Signalisierung

Verwenden Sie keines für das andere, ohne die Nebenwirkungen sorgfältig zu berücksichtigen.

Mutex: Exklusiver Mitgliederzugriff auf eine Ressource

Semaphor: n-Mitglied Zugriff auf eine Ressource

Das heißt, ein Mutex kann verwendet werden, um den Zugriff auf einen Zähler, eine Datei, eine Datenbank usw. zu synchronisieren.

Ein Sempahore kann dasselbe tun, unterstützt jedoch eine feste Anzahl gleichzeitiger Anrufer. Zum Beispiel kann ich meine Datenbankaufrufe in ein Semaphor (3) einschließen, sodass meine Multithread-App die Datenbank mit höchstens 3 gleichzeitigen Verbindungen erreicht. Alle Versuche werden blockiert, bis einer der drei Steckplätze geöffnet wird. Sie machen Dinge wie naives Drosseln wirklich sehr, sehr einfach.

Stellen Sie sich ein Taxi vor, das insgesamt 3 ( hinten ) +2 ( vorne ) Personen einschließlich des Fahrers aufnehmen kann. A semaphoreerlaubt also nur 5 Personen gleichzeitig in einem Auto. Und a mutexerlaubt nur 1 Person auf einem einzigen Sitz des Autos.

Daher Mutexsoll exklusiver Zugriff für eine Ressource ( wie einen Betriebssystem-Thread ) gewährt werden, während a Semaphoreden Zugriff für n Ressourcen gleichzeitig ermöglichen soll.

@Craig:

Ein Semaphor ist eine Möglichkeit, eine Ressource zu sperren, sodass garantiert wird, dass während der Ausführung eines Codeteils nur dieser Codeteil Zugriff auf diese Ressource hat. Dadurch wird verhindert, dass zwei Threads gleichzeitig auf eine Ressource zugreifen, was zu Problemen führen kann.

Dies ist nicht nur auf einen Thread beschränkt. Ein Semaphor kann so konfiguriert werden, dass eine feste Anzahl von Threads auf eine Ressource zugreifen kann.

Semaphor kann auch als ... Semaphor verwendet werden. Zum Beispiel, wenn Sie mehrere Prozessdaten in eine Warteschlange einreihen und nur eine Aufgabe Daten aus der Warteschlange verbraucht. Wenn Sie nicht möchten, dass Ihre aufwendige Aufgabe die Warteschlange ständig nach verfügbaren Daten abfragt, können Sie Semaphor verwenden.

Hier wird das Semaphor nicht als Ausschlussmechanismus, sondern als Signalmechanismus verwendet. Die konsumierende Aufgabe wartet auf das Semaphor. Die produzierende Aufgabe wird auf dem Semaphor veröffentlicht.

Auf diese Weise wird die konsumierende Aufgabe nur dann ausgeführt, wenn Daten aus der Warteschlange entfernt werden müssen

Es gibt zwei wesentliche Konzepte für die Erstellung gleichzeitiger Programme: Synchronisation und gegenseitiger Ausschluss. Wir werden sehen, wie diese beiden Arten von Sperren (Semaphoren sind im Allgemeinen eine Art Sperrmechanismus) uns helfen, Synchronisation und gegenseitigen Ausschluss zu erreichen.

Ein Semaphor ist ein Programmierkonstrukt, das uns hilft, Parallelität zu erreichen, indem sowohl Synchronisation als auch gegenseitiger Ausschluss implementiert werden. Es gibt zwei Arten von Semaphoren: Binär und Zählen.

Ein Semaphor besteht aus zwei Teilen: einem Zähler und einer Liste von Aufgaben, die auf den Zugriff auf eine bestimmte Ressource warten. Ein Semaphor führt zwei Operationen aus: Warten (P) [dies ist wie das Erhalten einer Sperre] und Loslassen (V) [ähnlich wie das Aufheben einer Sperre] - dies sind die einzigen zwei Operationen, die man an einem Semaphor ausführen kann. In einem binären Semaphor bewegt sich der Zähler logischerweise zwischen 0 und 1. Sie können sich vorstellen, dass er einer Sperre mit zwei Werten ähnelt: offen / geschlossen. Ein Zählsemaphor hat mehrere Werte für die Zählung.

Es ist wichtig zu verstehen, dass der Semaphorzähler die Anzahl der Aufgaben verfolgt, die nicht blockiert werden müssen, dh Fortschritte erzielen können. Aufgaben blockieren und fügen sich nur dann zur Liste des Semaphors hinzu, wenn der Zähler Null ist. Daher wird eine Aufgabe zur Liste in der Routine P () hinzugefügt, wenn sie nicht fortgesetzt werden kann, und mit der Routine V () "freigegeben".

Nun ist es ziemlich offensichtlich zu sehen, wie binäre Semaphoren verwendet werden können, um Synchronisation und gegenseitigen Ausschluss zu lösen - sie sind im Wesentlichen Sperren.

Ex. Synchronisation:

thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}

//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}

main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}

Im obigen Beispiel kann B2 erst ausgeführt werden, nachdem B1 die Ausführung beendet hat. Angenommen, Thread A wird zuerst ausgeführt - gelangt zu sem.P () und wartet, da der Zähler 0 (geschlossen) ist. Faden B kommt, beendet B1 und gibt dann Faden A frei - der dann B2 vervollständigt. So erreichen wir die Synchronisation.

Betrachten wir nun den gegenseitigen Ausschluss mit einem binären Semaphor:

thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...

}

main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}

Der gegenseitige Ausschluss ist ebenfalls recht einfach - m1 und m2 können nicht gleichzeitig in den kritischen Bereich eintreten. Daher verwendet jeder Thread dasselbe Semaphor, um die beiden kritischen Abschnitte gegenseitig auszuschließen. Ist es nun möglich, eine größere Parallelität zu erreichen? Kommt auf die kritischen Abschnitte an. (Überlegen Sie, wie man sonst Semaphoren verwenden könnte, um einen gegenseitigen Ausschluss zu erreichen. Hinweis Hinweis: Muss ich unbedingt nur ein Semaphor verwenden?)

Semaphor zählen: Ein Semaphor mit mehr als einem Wert. Schauen wir uns an, was dies bedeutet - eine Sperre mit mehr als einem Wert? Also offen, geschlossen und ... hmm. Was nützt eine mehrstufige Sperre beim gegenseitigen Ausschluss oder bei der Synchronisation?

Nehmen wir das leichtere von beiden:

Synchronisation mit einem Zählsemaphor: Angenommen, Sie haben 3 Aufgaben - Nr. 1 und 2, die Sie nach 3 ausführen möchten. Wie würden Sie Ihre Synchronisation gestalten?

thread t1{
...
s.P();
//block of code B1

thread t2{
...
s.P();
//block of code B2

thread t3{
...
//block of code B3
s.V();
s.V();
}

Wenn Ihr Semaphor also geschlossen beginnt, stellen Sie sicher, dass der Block t1 und t2 zur Liste des Semaphors hinzugefügt wird. Dann kommt alles wichtige t3, beendet sein Geschäft und befreit t1 und t2. In welcher Reihenfolge werden sie befreit? Hängt von der Implementierung der Semaphorliste ab. Könnte FIFO sein, könnte eine bestimmte Priorität haben usw. (Hinweis: Überlegen Sie, wie Sie Ihre Ps und Vs anordnen würden, wenn t1 und t2 in einer bestimmten Reihenfolge ausgeführt werden sollen und wenn Sie sich der Implementierung des Semaphors nicht bewusst sind.)

(Finden Sie heraus: Was passiert, wenn die Anzahl der Vs größer ist als die Anzahl der Ps?)

Gegenseitiger Ausschluss Verwenden von Zählsemaphoren: Ich möchte, dass Sie dafür Ihren eigenen Pseudocode erstellen (damit Sie die Dinge besser verstehen!) - aber das grundlegende Konzept lautet: Ein Zählsemaphor von counter = N ermöglicht es N Aufgaben, frei in den kritischen Abschnitt einzutreten . Dies bedeutet, dass Sie N Aufgaben (oder Threads, wenn Sie möchten) in den kritischen Bereich eingeben, aber die N + 1-Aufgabe blockiert wird (wird in unsere Liste der bevorzugten blockierten Aufgaben aufgenommen) und nur dann durchgelassen wird, wenn jemand V das Semaphor ist zumindest einmal. Anstatt zwischen 0 und 1 zu schwingen, bewegt sich der Semaphorzähler jetzt zwischen 0 und N, sodass N Aufgaben frei ein- und ausgehen können und niemand blockiert wird!

Nun meine Güte, warum brauchst du so ein dummes Ding? Ist es nicht der Sinn des gegenseitigen Ausschlusses, nicht mehr als einen Mann auf eine Ressource zugreifen zu lassen? (Hinweis Hinweis ... Sie haben nicht immer nur ein Laufwerk in Ihrem Computer, oder ...?)

Zu denken : Wird gegenseitiger Ausschluss durch ein Zählsemaphor allein erreicht? Was ist, wenn Sie 10 Instanzen einer Ressource haben und 10 Threads (über das Zählsemaphor) eingehen und versuchen, die erste Instanz zu verwenden?

Ein Semaphor ist ein Objekt, das eine natürliche Zahl enthält (dh eine ganze Zahl größer oder gleich Null), für die zwei Änderungsoperationen definiert sind. Eine Operation Vaddiert 1 zum natürlichen. Die andere Operation Pverringert die natürliche Zahl um 1. Beide Aktivitäten sind atomar (dh es kann keine andere Operation gleichzeitig mit a Voder a ausgeführt werdenP ).

Da die natürliche Zahl 0 nicht verringert werden kann, Pblockiert der Aufruf eines Semaphors mit einer 0 die Ausführung des aufrufenden Prozesses (/ thread) bis zu einem Zeitpunkt, an dem die Zahl nicht mehr 0 und istP erfolgreich (und atomar) ausgeführt werden kann.

Wie in anderen Antworten erwähnt, können Semaphoren verwendet werden, um den Zugriff auf eine bestimmte Ressource auf eine maximale (aber variable) Anzahl von Prozessen zu beschränken.

Ich habe die Visualisierung erstellt, die helfen soll, die Idee zu verstehen. Semaphor steuert den Zugriff auf eine gemeinsame Ressource in einer Multithreading-Umgebung.

ExecutorService executor = Executors.newFixedThreadPool(7);

Semaphore semaphore = new Semaphore(4);

Runnable longRunningTask = () -> {
    boolean permit = false;
    try {
        permit = semaphore.tryAcquire(1, TimeUnit.SECONDS);
        if (permit) {
            System.out.println("Semaphore acquired");
            Thread.sleep(5);
        } else {
            System.out.println("Could not acquire semaphore");
        }
    } catch (InterruptedException e) {
        throw new IllegalStateException(e);
    } finally {
        if (permit) {
            semaphore.release();
        }
    }
};

// execute tasks
for (int j = 0; j < 10; j++) {
    executor.submit(longRunningTask);
}
executor.shutdown();

Ausgabe

Semaphore acquired
Semaphore acquired
Semaphore acquired
Semaphore acquired
Could not acquire semaphore
Could not acquire semaphore
Could not acquire semaphore

Beispielcode aus dem Artikel

Ein Hardware- oder Software-Flag. In Multitasking-Systemen ist ein Semaphor eine Variable mit einem Wert, der den Status einer gemeinsamen Ressource angibt. Ein Prozess, der die Ressource benötigt, überprüft das Semaphor, um den Ressourcenstatus zu bestimmen, und entscheidet dann, wie fortzufahren ist.

Semaphoren wirken wie Fadenbegrenzer.

Beispiel: Wenn Sie einen Pool von 100 Threads haben und eine DB-Operation ausführen möchten. Wenn zu einem bestimmten Zeitpunkt 100 Threads auf die Datenbank zugreifen, liegt möglicherweise ein Sperrproblem in der Datenbank vor, sodass wir ein Semaphor verwenden können, das jeweils nur einen begrenzten Thread zulässt. Das folgende Beispiel lässt jeweils nur einen Thread zu. Wenn ein Thread die acquire()Methode aufruft release(), erhält er den Zugriff und nach dem Aufrufen der Methode wird der Zugriff freigegeben, sodass der nächste Thread den Zugriff erhält.

    package practice;
    import java.util.concurrent.Semaphore;

    public class SemaphoreExample {
        public static void main(String[] args) {
            Semaphore s = new Semaphore(1);
            semaphoreTask s1 = new semaphoreTask(s);
            semaphoreTask s2 = new semaphoreTask(s);
            semaphoreTask s3 = new semaphoreTask(s);
            semaphoreTask s4 = new semaphoreTask(s);
            semaphoreTask s5 = new semaphoreTask(s);
            s1.start();
            s2.start();
            s3.start();
            s4.start();
            s5.start();
        }
    }

    class semaphoreTask extends Thread {
        Semaphore s;
        public semaphoreTask(Semaphore s) {
            this.s = s;
        }
        @Override
        public void run() {
            try {
                s.acquire();
                Thread.sleep(1000);
                System.out.println(Thread.currentThread().getName()+" Going to perform some operation");
                s.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        } 
    }

Stellen Sie sich vor, jeder versucht, auf die Toilette zu gehen, und es gibt nur eine bestimmte Anzahl von Schlüsseln für die Toilette. Wenn nicht mehr genügend Schlüssel vorhanden sind, muss diese Person warten. Stellen Sie sich das Semaphor also als den Satz von Schlüsseln vor, die für Badezimmer verfügbar sind (die Systemressourcen), auf die verschiedene Prozesse (Badezimmerbesucher) Zugriff anfordern können.

Stellen Sie sich nun zwei Prozesse vor, die gleichzeitig versuchen, auf die Toilette zu gehen. Das ist keine gute Situation und Semaphore werden verwendet, um dies zu verhindern. Leider ist das Semaphor ein freiwilliger Mechanismus und Prozesse (unsere Badezimmerbesucher) können es ignorieren (dh selbst wenn es Schlüssel gibt, kann jemand die Tür einfach auftreten).

Es gibt auch Unterschiede zwischen Binär- / Mutex- und Zählsemaphoren.

Lesen Sie die Vorlesungsunterlagen unter http://www.cs.columbia.edu/~jae/4118/lect/L05-ipc.html .

Dies ist eine alte Frage, aber eine der interessantesten Anwendungen von Semaphoren ist eine Lese- / Schreibsperre, die nicht explizit erwähnt wurde.

Die R / W-Sperren funktionieren auf einfache Weise: Verbrauchen Sie eine Erlaubnis für einen Leser und alle Genehmigungen für Schriftsteller. Eine triviale Implementierung der Ar / W-Sperre erfordert jedoch eine Metadatenänderung beim Lesen (tatsächlich zweimal), die zu einem Flaschenhals werden kann, der immer noch erheblich besser ist als ein Mutex oder eine Sperre.

Ein weiterer Nachteil ist, dass Autoren auch ziemlich einfach gestartet werden können, es sei denn, das Semaphor ist fair oder die Schreibvorgänge erhalten Genehmigungen für mehrere Anforderungen. In diesem Fall benötigen sie einen expliziten Mutex untereinander.

Weitere Lese :

Ein Semaphor ist eine Möglichkeit, eine Ressource zu sperren, sodass garantiert wird, dass während der Ausführung eines Codeteils nur dieser Codeteil Zugriff auf diese Ressource hat. Dadurch wird verhindert, dass zwei Threads gleichzeitig auf eine Ressource zugreifen, was zu Problemen führen kann.