Ist meine Spin-Lock-Implementierung korrekt und optimal?

Question

Ich bin mit einem Spin-Lock einen sehr kleinen kritischen Abschnitt zu schützen. Contention geschieht sehr selten so ein Spin-Lock ist besser geeignet als ein normales Mutex.

Mein aktueller Code ist wie folgt, und geht davon aus x86 und GCC:

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

Also ich frage mich:

• Ist dieser Code korrekt? Ist es richtig mutual exclusion gewährleisten?
• funktioniert es auf allen x86-Betriebssysteme?
• funktioniert es auch auf x86_64? Auf allen Betriebssystemen?
• Ist es optimal?
  • Ich habe Spin-Lock-Implementierungen gesehen mit Vergleichs- und Swap, aber ich bin mir nicht sicher, was besser ist.
  • Nach der GCC Atom builtins Dokumentation ( http: //gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html ) gibt es auch __sync_lock_release. Ich bin kein Experte für Speicherbarrieren so ich bin mir nicht sicher, ob es in Ordnung ist für mich, dies zu verwenden, anstatt __sync_synchronize.
  • Ich bin für den Fall zu optimieren, in dem es keinen Streit.

I do not care auf alle über Anstoß. Es kann 1 sein, vielleicht zwei andere Threads versucht, den Spin-Lock zu sperren einmal alle paar Tage .

Answer 1

Also ich frage mich:

* Is it correct?

Im Kontext erwähnt, würde ich sagen, ja.

* Is it optimal?

Das ist eine geladene Frage. Durch das Rad neu erfinden neu erfinden Sie auch eine Menge Probleme, die von anderen Implementierungen

gelöst wurden

• Ich würde eine Verschwendung Schleife bei Ausfall erwarten, wo Sie nicht versuchen, das Sperrwort zugreifen zu können.

• Die Verwendung einer vollständigen Barriere in den entriegelten muss nur Release Semantik haben (das ist, warum Sie __sync_lock_release verwenden würden, so dass Sie st1.rel auf itanium statt mf bekommen würden, oder ein lwsync auf powerpc, ...). Wenn Sie wirklich interessieren sich nur für x86 oder x86_64 die Arten von Barrieren verwendet hier oder nicht keine Rolle, wie viel (aber wenn Sie, wo Sie den Sprung auf Intel Itanium für einen HP-IPF-Port machen, dann würden Sie das nicht wollen).

• Sie haben nicht die Pause () Anweisung, dass Sie in der Regel, bevor Sie Ihren Abfall Schleife setzen würden.

• , wenn es Streit ist Sie etwas , semop oder sogar ein stummer Schlaf in Verzweiflung. Wenn Sie wirklich brauchen, um die Leistung, dass diese kauft man dann der futex Vorschlag wahrscheinlich gut ist. Wenn Sie die Leistung diese Käufe müssen Sie schlecht genug, um hält Dieser Code Sie eine Menge Forschung zu tun haben.

Beachten Sie, dass es ein Kommentar war zu sagen, dass die Freigabe Barriere nicht erforderlich war. Das ist nicht wahr, auch auf x86, weil die Freisetzung Barriere dient auch als eine Anweisung an die Compiler nicht andere Speicher mischen greifen um die „Barriere“. Sehr viel wie das, was würden Sie, wenn Sie verwenden asm ( "" ::: "memory").

* on compare and swap

Auf x86 wird die sync_lock_test_and_set auf eine xchg Anweisung Karte, die eine implizite Sperre Präfix hat. Auf jeden Fall das kompakteste generierten Code (insb. Wenn Sie ein Byte für die „Sperrwort“ anstelle eines int), aber nicht weniger richtig, als wenn Sie verwendet LOCK cmpxchg. Die Verwendung von Vergleichs- und Auslagerungs für ausgefallenere algorthims verwendet werden (wie einen Nicht-Null-Zeiger auf Metadaten für die ersten „Kellner“ in die lockword bei Ausfall setzen).

Answer 2

Sieht für mich in Ordnung. Btw, hier ist die Lehrbuch Implementierung, die effizienten, auch im behaupteten Fall ist.

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}

Answer 3

Als Antwort auf Ihre Fragen:

1. Sieht ok mir
2. das OS Unter der Annahme, unterstützt GCC (und GCC hat die Funktionen implementiert); dies sollte auf allen x86-Betriebssystemen arbeiten. Die GCC-Dokumentation schlägt vor, dass eine Warnung erzeugt werden, wenn sie nicht auf einer bestimmten Plattform unterstützt werden.
3. Es gibt nichts x86-64 spezifischen hier, also ich sehe nicht, warum nicht. Dies kann zu einer Abdeckung erweitert werden jeder Architektur, dass GCC unterstützt, aber es vielleicht optimalere Möglichkeiten, dies auf nicht x86-Architekturen zu erzielen.
4. Sie könnten etwas besser dran mit __sync_lock_release() im unlock() Fall verwendet wird; da dies die Verriegelungs dekrementieren und eine Speicherbarriere in einem einzigen Arbeitsgang hinzufügen. Jedoch davon aus, dass Ihre Behauptung, dass es selten Streit sein wird; es sieht gut für mich.

Answer 4

Wenn Sie auf eine aktuelle Version von Linux sind, können Sie in der Lage sein, ein verwenden futex - ein "schneller User-Space-Mutex":

  

Eine richtig programmiert futex-basierte Sperre wird nicht Systemaufrufe der Ausnahme, wenn das Schloss behauptet wird

In dem unbestrittenen Fall, die Sie mit Ihrem spinlock zu optimieren sind versuchen, wird die futex verhält sich wie ein spinlock, ohne einen Kernel syscall zu erfordern. Wenn die Sperre angefochten wird, nimmt der Warteplatz im Kernel ohne busy-Warte.

Answer 5

Ich frage mich, ob die CAS-Implementierung der richtigen auf x86_64 ist. Es ist fast zweimal schneller auf meinem i7 X920 Laptop (Fedora 13 x86_64, gcc 4.4.5).

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}

Answer 6

Ich kann nicht auf Richtigkeit kommentieren, aber der Titel Ihrer Frage aufgeworfen, eine rote Fahne, bevor ich auch die Frage Körper lesen. Synchronisierungsgrund ist teuflisch schwer Korrektheit, um sicherzustellen, ... wenn überhaupt möglich, du bist besser dran mit einer gut gestalteten / gepflegt Bibliothek, vielleicht pThreads oder boost: :. Gewinde

Answer 7

ist eine Verbesserung vorschlagen wird mit TATAS (Test-and-Test -and-set). Mit CAS-Operationen sind recht teuer für den Prozessor betrachtet, so ist es besser, sie zu vermeiden, wenn möglich. Ein andere Sache, stellen Sie sicher, dass Sie nicht von Priorität Inversion leiden werden (was ist, wenn ein Thread mit hohen Priorität versucht, die Sperre zu erhalten, während ein Thread mit niedriger Priorität versucht, die Sperre zu befreien? Unter Windows zum Beispiel dieser Frage wird letztlich durch gelöst durch der Scheduler eine priority boost verwenden, aber Sie können Ihre Threads Zeitscheibe, falls Sie nicht gelingt, den Erwerb der Sperre in dem letzten 20 Versuche (zB ..)

explizit aufgeben

Answer 8

Ihr Unlock-Vorgang muss nicht die Speichergrenze; die Zuordnung zum Ausschluß ist atomar, solange es auf der x86 ausgerichtet DWort.

Answer 9

Im speziellen Fall von x86 (32/64) Ich glaube nicht, dass Sie überhaupt in dem Entsperrcode einen Speicher Zaun benötigen. x86 führt keine Umordnung, außer dass speichert erster Put in einem Speicherpuffer ist und so sie sichtbar werden kann für andere Threads verzögert werden. Und ein Thread, der einen Speicher tut, und liest dann aus der gleichen Variable wird von seinem Speicherpuffer lesen, wenn sie noch nicht in dem Speicher geleert wird. Also alles, was Sie brauchen, ist eine asm Anweisung Compiler Umordnungen zu verhindern. Sie laufen Gefahr, von einem Thread die Sperre etwas länger als nötig aus der Perspektive der anderen Threads zu halten, aber wenn Sie nicht über Konkurrenz egal das sollte keine Rolle. In der Tat ist, pthread_spin_unlock so implementiert, die auf meinem System (Linux x86_64).

Mein System auch Geräte pthread_spin_lock mit lock decl lockvar; jne spinloop; statt mit xchg (was, was __sync_lock_test_and_set Anwendungen sind), aber ich weiß nicht, ob es tatsächlich ein Unterschied in der Leistung ist.

Answer 10

Es gibt einige falsche Annahmen.

Als erstes SpinLock macht nur Sinn, wenn Ressource auf einer anderen CPU gesperrt ist. Wenn ressource auf derselben CPU gesperrt ist (das ist immer der Fall auf Einprozessorsystemen), benötigen Sie Scheduler, um Unlock ressource zu entspannen. Sie aktuelle Code wird auf Einprozessor-System arbeiten, weil Scheduler Aufgaben wechseln automatisch, aber es ist eine Verschwendung von ressource.

Ein Multiprozessorsystem, gleiche kann happends, aber Aufgabe kann von einer CPU auf einen anderen migrieren. Kurz gesagt, die Verwendung von Spin-Lock ist richtig, wenn Sie garantieren, dass Ihre Aufgaben auf verschiedene CPU ausgeführt werden.

Zweitens ein Mutex Verriegelung schnell (so schnell wie spinlock), wenn entriegelt wird. Mutexes Verriegelung (und Entriegelung) ist langsam (sehr langsam) nur dann, wenn Mutex bereits gesperrt ist.

Also, in Ihrem Fall, schlage ich zu verwenden mutexes.