Spinlock gegen Semaphor

Was sind die grundlegenden Unterschiede zwischen einem Semaphor und einem Spin-Lock?

Wann würden wir ein Semaphor über einem Spin-Lock verwenden?

Spinlock und Semaphor unterscheiden sich hauptsächlich in vier Punkten:

1. Was sie sind
Ein Spinlock ist eine mögliche Implementierung einer Sperre, nämlich eine, die durch beschäftigtes Warten ("Drehen") implementiert wird. Ein Semaphor ist eine Verallgemeinerung einer Sperre (oder umgekehrt ist eine Sperre ein Sonderfall eines Semaphors). Üblicherweise , aber nicht notwendigerweise , sind spinlocks nur gültig innerhalb eines Prozesses während Semaphore kann verwendet werden , um zwischen verschiedenen Prozessen zu synchronisieren, auch.

Eine Sperre dient dem gegenseitigen Ausschluss, dh, jeweils ein Thread kann die Sperre erwerben und mit einem "kritischen Abschnitt" des Codes fortfahren. Normalerweise bedeutet dies Code, der einige Daten ändert, die von mehreren Threads gemeinsam genutzt werden.
Ein Semaphor hat einen Zähler und kann von einem oder mehreren Threads erfasst werden, je nachdem, welchen Wert Sie darauf posten, und (in einigen Implementierungen) davon, wie hoch sein maximal zulässiger Wert ist.

Insofern kann man eine Sperre als Sonderfall eines Semaphors mit einem Maximalwert von 1 betrachten.

2. Was sie tun
Wie oben erwähnt, ist ein Spinlock eine Sperre und daher ein Mechanismus des gegenseitigen Ausschlusses (streng 1 zu 1). Es funktioniert durch wiederholtes Abfragen und / oder Ändern eines Speicherorts, normalerweise auf atomare Weise. Dies bedeutet, dass der Erwerb eines Spinlocks eine "beschäftigte" Operation ist, die möglicherweise CPU-Zyklen für eine lange Zeit (möglicherweise für immer!) Verbrennt, während effektiv "nichts" erreicht wird.
Der Hauptanreiz für einen solchen Ansatz ist die Tatsache, dass ein Kontextwechsel einen Overhead hat, der dem Drehen einige hundert (oder vielleicht tausend) Mal entspricht. Wenn also eine Sperre durch Brennen einiger Drehzyklen erworben werden kann, kann dies insgesamt sehr gut sein effizienter. Für Echtzeitanwendungen ist es möglicherweise nicht akzeptabel, zu blockieren und zu warten, bis der Scheduler zu einem späteren Zeitpunkt zu ihnen zurückkehrt.

Im Gegensatz dazu dreht sich ein Semaphor entweder überhaupt nicht oder nur für eine sehr kurze Zeit (als Optimierung, um den Syscall-Overhead zu vermeiden). Wenn ein Semaphor nicht erfasst werden kann, blockiert es und gibt die CPU-Zeit an einen anderen Thread ab, der zur Ausführung bereit ist. Dies kann natürlich bedeuten, dass einige Millisekunden vergehen, bevor Ihr Thread erneut geplant wird. Wenn dies jedoch kein Problem darstellt (normalerweise nicht), kann dies ein sehr effizienter, CPU-konservativer Ansatz sein.

3. Wie sie sich bei Überlastung verhalten
Es ist ein weit verbreitetes Missverständnis, dass Spinlocks oder sperrfreie Algorithmen "im Allgemeinen schneller" sind oder dass sie nur für "sehr kurze Aufgaben" nützlich sind (idealerweise sollte kein Synchronisationsobjekt länger gehalten werden als absolut notwendig, jemals).
Der eine wichtige Unterschied besteht darin, wie sich die verschiedenen Ansätze bei Überlastung verhalten .

Ein gut konzipiertes System weist normalerweise eine geringe oder keine Überlastung auf (dies bedeutet, dass nicht alle Threads versuchen, die Sperre genau zur gleichen Zeit zu erlangen). Beispielsweise würde man normalerweise keinen Code schreiben, der eine Sperre erhält, dann ein halbes Megabyte zip-komprimierter Daten aus dem Netzwerk lädt, die Daten decodiert und analysiert und schließlich eine gemeinsame Referenz ändert (Daten an einen Container anhängen usw.) vor dem Lösen des Schlosses. Stattdessen würde man die Sperre nur zum Zweck des Zugriffs auf die gemeinsam genutzte Ressource erwerben .
Da dies bedeutet, dass außerhalb des kritischen Abschnitts erheblich mehr Arbeit als innerhalb des kritischen Abschnitts vorhanden ist, ist die Wahrscheinlichkeit, dass sich ein Gewinde innerhalb des kritischen Abschnitts befindet, natürlich relativ gering, und daher kämpfen nur wenige Gewinde gleichzeitig um die Sperre. Natürlich versuchen hin und wieder zwei Threads gleichzeitig, die Sperre zu erlangen (wenn dies nicht passieren könnte , würden Sie keine Sperre benötigen!), Aber dies ist eher die Ausnahme als die Regel in einem "gesunden" System .

In einem solchen Fall übertrifft ein Spinlock ein Semaphor erheblich , da der Aufwand für den Erwerb des Spinlocks nur ein Dutzend Zyklen beträgt, verglichen mit Hunderten / Tausenden von Zyklen für einen Kontextwechsel oder 10 bis 20 Millionen Zyklen für den Verlust, wenn keine Sperrenüberlastung vorliegt der Rest einer Zeitscheibe.

Auf der anderen Seite brennt ein Spinlock bei hoher Überlastung oder wenn die Sperre längere Zeit gehalten wird (manchmal kann man einfach nicht anders!), Wahnsinnig viele CPU-Zyklen, um nichts zu erreichen.
Ein Semaphor (oder Mutex) ist in diesem Fall eine viel bessere Wahl, da ein anderer Thread während dieser Zeit nützliche Aufgaben ausführen kann . Wenn kein anderer Thread etwas Nützliches zu tun hat, kann das Betriebssystem die CPU drosseln und Wärme reduzieren / Energie sparen.

Auch auf einem Single-Core - System wird ein spinlock ganz in Anwesenheit von Schloss Stauen ineffizient sein, wie ein Spinnfaden wird seine komplette Zeit mit Warten auf eine Zustandsänderung verschwenden , die nicht möglicherweise passieren können (erst die Freigabe Thread geplant, die isn passiert nicht, während der wartende Thread läuft!). Daher dauert das Erhalten der Sperre bei jedem Streit im besten Fall etwa 1 1/2 Zeitscheiben (vorausgesetzt, der Freigabe-Thread ist der nächste, der geplant wird), was kein sehr gutes Verhalten ist.

4. Wie sie implementiert werden
Ein Semaphor wird heutzutage normalerweise sys_futexunter Linux verpackt (optional mit einem Spinlock, der nach einigen Versuchen beendet wird).
Ein Spinlock wird normalerweise mithilfe atomarer Operationen implementiert, ohne dass etwas vom Betriebssystem bereitgestellt wird. In der Vergangenheit bedeutete dies, entweder Compiler-Intrinsics oder nicht portable Assembler-Anweisungen zu verwenden. Inzwischen haben sowohl C ++ 11 als auch C11 atomare Operationen als Teil der Sprache. Abgesehen von der allgemeinen Schwierigkeit, nachweislich korrekten Code ohne Sperren zu schreiben, ist es jetzt möglich, Code ohne Sperren in einem vollständig portablen und (fast) schmerzloser Weg.

Ganz einfach, ein Semaphor ist ein "nachgebendes" Synchronisationsobjekt, ein Spinlock ist ein "Busywait" -Objekt. (Semaphore bieten etwas mehr, da sie mehrere Threads synchronisieren, im Gegensatz zu einem Mutex oder Guard oder Monitor oder einem kritischen Abschnitt, der einen Codebereich vor einem einzelnen Thread schützt.)

Sie würden unter mehr Umständen ein Semaphor verwenden, aber ein Spinlock verwenden, bei dem Sie für eine sehr kurze Zeit sperren werden - das Sperren ist mit Kosten verbunden, insbesondere wenn Sie viel sperren. In solchen Fällen kann es effizienter sein, ein wenig zu sperren, während darauf gewartet wird, dass die geschützte Ressource entsperrt wird. Offensichtlich gibt es einen Leistungseinbruch, wenn Sie zu lange drehen.

Wenn Sie länger als ein Thread-Quantum drehen, sollten Sie normalerweise ein Semaphor verwenden.

Über das hinaus, was Yoav Aviram und gbjbaanb sagten, war der andere wichtige Punkt, dass Sie auf einem Computer mit einer CPU niemals ein Spin-Lock verwenden würden, während ein Semaphor auf einem solchen Computer Sinn machen würde. Heutzutage ist es häufig schwierig, eine Maschine ohne mehrere Kerne oder Hyperthreading oder gleichwertig zu finden. Unter den Umständen, dass Sie nur eine einzige CPU haben, sollten Sie Semaphoren verwenden. (Ich vertraue darauf, dass der Grund offensichtlich ist. Wenn die einzelne CPU damit beschäftigt ist, auf die Freigabe der Spin-Sperre durch etwas anderes zu warten, diese jedoch auf der einzigen CPU ausgeführt wird, ist es unwahrscheinlich, dass die Sperre aufgehoben wird, bis der aktuelle Prozess oder Thread von verhindert wird das O / S, das eine Weile dauern kann und nichts Nützliches passiert, bis die Vorauszahlung erfolgt.)

Von Linux-Gerätetreibern von Rubinni

Im Gegensatz zu Semaphoren können Spinlocks in Code verwendet werden, der nicht schlafen kann, z. B. Interrupt-Handler

Ich bin kein Kernel-Experte, aber hier sind einige Punkte:

Selbst Uniprozessor-Maschinen können Spin-Locks verwenden, wenn beim Kompilieren des Kernels die Kernel-Preemption aktiviert ist. Wenn die Kernel-Preemption deaktiviert ist, wird Spin-Lock (möglicherweise) zu einer void- Anweisung erweitert.

Wenn wir versuchen, Semaphore mit Spin-Lock zu vergleichen, bezieht sich Semaphor meines Erachtens auf das im Kernel verwendete - NICHT auf das für IPC (Userland) verwendete.

Grundsätzlich sollte Spin-Lock verwendet werden, wenn der kritische Abschnitt klein ist (kleiner als der Overhead von Schlaf / Aufwachen) und der kritische Abschnitt nichts aufruft, was schlafen kann! Ein Semaphor ist zu verwenden, wenn der kritische Abschnitt größer ist und schlafen kann.

Raman Chalotra.

Spinlock bezieht sich auf eine Implementierung der Inter-Thread-Verriegelung unter Verwendung maschinenabhängiger Montageanweisungen (z. B. Test-and-Set). Es wird als Spinlock bezeichnet, da der Thread einfach in einer Schleife ("Spins") wartet und wiederholt prüft, bis die Sperre verfügbar wird (Besetzt warten). Spinlocks werden als Ersatz für Mutexe verwendet, die von Betriebssystemen (nicht von der CPU) bereitgestellt werden, da Spinlocks eine bessere Leistung erzielen, wenn sie für einen kurzen Zeitraum gesperrt werden.

Eine Semaphor ist eine Einrichtung, die von Betriebssystemen für IPC bereitgestellt wird. Daher dient ihr Hauptzweck der Kommunikation zwischen Prozessen. Da es sich um eine vom Betriebssystem bereitgestellte Einrichtung handelt, ist die Leistung nicht so gut wie die eines Spinlocks für die Verriegelung zwischen den Köpfen (obwohl dies möglich ist). Semaphoren eignen sich besser zum Verriegeln über längere Zeiträume.

Das heißt - die Implementierung von Splinlocks in der Montage ist schwierig und nicht portabel.

Ich möchte meine Beobachtungen hinzufügen, allgemeiner und nicht sehr Linux-spezifisch.

Abhängig von der Speicherarchitektur und den Prozessorfunktionen benötigen Sie möglicherweise eine Drehsperre, um ein Semaphor auf einem Multi-Core- oder Multiprozessorsystem zu implementieren, da in solchen Systemen eine Race-Bedingung auftreten kann, wenn zwei oder mehr Threads / Prozesse dies wünschen ein Semaphor erwerben.

Ja, wenn Ihre Speicherarchitektur das Sperren eines Speicherabschnitts durch einen Kern / Prozessor bietet, der alle anderen Zugriffe verzögert, und wenn Ihre Prozessoren einen Test and Set anbieten, können Sie ein Semaphor ohne Spin-Lock implementieren (aber sehr vorsichtig! ).

Da jedoch einfache / billige Mehrkernsysteme entwickelt werden (ich arbeite in eingebetteten Systemen), unterstützen nicht alle Speicherarchitekturen solche Mehrkern- / Mehrprozessorfunktionen, sondern nur Test-and-Set oder gleichwertige. Dann könnte eine Implementierung wie folgt sein:

• das Spin-Lock erwerben (beschäftigt warten)
• versuche das Semaphor zu erwerben
• Lassen Sie die Drehsperre los
• Wenn das Semaphor nicht erfolgreich erfasst wurde, setzen Sie den aktuellen Thread aus, bis das Semaphor freigegeben wird. Andernfalls fahren Sie mit dem kritischen Abschnitt fort

Die Freigabe des Semaphors müsste wie folgt implementiert werden:

• Erwerben Sie das Spin-Lock
• Lassen Sie das Semaphor los
• Lassen Sie die Drehsperre los

Ja, und für einfache binäre Semaphoren auf Betriebssystemebene könnte nur ein Spin-Lock als Ersatz verwendet werden. Aber nur, wenn die zu schützenden Codeabschnitte wirklich sehr klein sind.

Wie bereits erwähnt, sollten Sie vorsichtig sein, wenn Sie Ihr eigenes Betriebssystem implementieren. Das Debuggen solcher Fehler macht Spaß (meine Meinung, nicht von vielen geteilt), ist aber meistens sehr mühsam und schwierig.

Ein "Mutex" (oder "gegenseitige Ausschlusssperre") ist ein Signal, mit dem zwei oder mehr asynchrone Prozesse eine gemeinsam genutzte Ressource für die ausschließliche Verwendung reservieren können. Der erste Prozess, der das Eigentum an dem "Mutex" erhält, erwirbt auch das Eigentum an der gemeinsam genutzten Ressource. Andere Prozesse müssen warten, bis der erste Prozess sein Eigentum am "Mutex" freigibt, bevor sie versuchen, ihn zu erhalten.

Das häufigste Locking-Primitiv im Kernel ist der Spinlock. Das Spinlock ist ein sehr einfaches Einzelhalterschloss. Wenn ein Prozess versucht, einen Spinlock zu erwerben, und dieser nicht verfügbar ist, versucht der Prozess weiter (dreht sich), bis er den Lock erhalten kann. Diese Einfachheit schafft ein kleines und schnelles Schloss.

Spinlock wird genau dann verwendet, wenn Sie ziemlich sicher sind, dass Ihr erwartetes Ergebnis sehr kurz vor Ablauf der Ausführungszeit Ihres Threads eintreten wird.

Beispiel: Im Gerätetreibermodul schreibt der Treiber "0" in das Hardwareregister R0 und muss nun warten, bis dieses R0-Register 1 wird. Das H / W liest das R0 und erledigt einige Arbeiten und schreibt "1" in R0. Dies ist im Allgemeinen schnell (in Mikrosekunden). Jetzt ist das Drehen viel besser als schlafen zu gehen und vom H / W unterbrochen zu werden. Natürlich muss beim Drehen auf die H / W-Fehlerbedingung geachtet werden!

Es gibt absolut keinen Grund für eine Benutzeranwendung, sich zu drehen. Es macht keinen Sinn. Sie werden sich drehen, damit ein Ereignis eintritt, und dieses Ereignis muss von einer anderen Anwendung auf Benutzerebene abgeschlossen werden, die niemals innerhalb eines kurzen Zeitrahmens garantiert wird. Ich werde mich also im Benutzermodus überhaupt nicht drehen. Ich schlafe besser () oder mutexlock () oder semaphore lock () im Benutzermodus.

Aus was ist der Unterschied zwischen Spinlocks und Semaphore? von Maciej Piechotka :

Beide verwalten eine begrenzte Ressource. Ich werde zuerst den Unterschied zwischen binärem Semaphor (Mutex) und Spin Lock beschreiben.

Spin-Locks führen eine ausgelastete Wartezeit durch - dh sie läuft weiter:

while (try_acquire_resource ()); 
 ...  
Freisetzung();

Es führt ein sehr leichtes Sperren / Entsperren durch, aber wenn der Sperr-Thread von einem anderen verhindert wird, der versucht, auf dieselbe Ressource zuzugreifen, versucht der zweite einfach, Ressourcen freizugeben, bis ihm die CPU-Quanten ausgehen.
Auf der anderen Seite verhält sich Mutex eher wie:

if (! try_lock ()) {
    add_to_waiting_queue ();
    warten();
}}
...
process * p = get_next_process_from_waiting_queue ();
p-> wakeUp ();

Wenn der Thread versucht, blockierte Ressourcen zu erhalten, wird er angehalten, bis er für ihn verfügbar ist. Das Sperren / Entsperren ist viel schwerer, aber das Warten ist "frei" und "fair".

Semaphor ist eine Sperre, die mehrfach (aus der Initialisierung bekannt) mehrmals verwendet werden darf. Beispielsweise dürfen 3 Threads gleichzeitig die Ressource enthalten, jedoch nicht mehr. Es wird zum Beispiel bei Produzenten- / Konsumentenproblemen oder allgemein in Warteschlangen verwendet:

P (resources_sem)
resource = resources.pop ()
...
resources.push (Ressourcen)
V (resources_sem)

Unterschied zwischen Semaphor, Mutex & Spinlock?

Unter Linux sperren

Die Spin-Sperre kann nur von einem Prozess gehalten werden, während das Semaphor von einem oder mehreren Prozessen gehalten werden kann. Spin Lock warten, bis der Prozess eine Sperre aufhebt und dann eine Sperre erhält. Semaphor ist Schlafschloss dh wartet und geht schlafen.