Leichte Spinlocks, die aus atomaren Operationen des GCC gebaut wurden?

Question

Ich möchte die Synchronisation minimieren und schreiben lock-freie Code wenn möglich in einem Projekt von mir. Wenn es absolut notwendig ist, würde ich gerne leichte Spinlocks ersetzen, die aus atomaren Operationen für pthread und win32 Mutex Locks bestehen. Mein Verständnis ist, dass dies Systemaufrufe unterhalb sind und einen Kontextwechsel verursachen könnten (was für sehr schnelle kritische Abschnitte unnötig sein kann, in denen es einfach wäre, sich ein paar Mal zu drehen).

Die atomaren Operationen Ich beziehe mich hier gut dokumentiert: http://gcc.gnu.org/onlinedocs/gcc-4.4.1/gcc/Atomic-Builtins.html

Hier ist ein Beispiel zu veranschaulichen, was ich rede. Stellen Sie sich einen RB-Baum mit mehreren Lesern und Schreibern vor. RBTree :: exists() ist schreibgeschützt und Thread-sicher, RBTree :: insert() würde exklusiven Zugriff durch einen einzigen Schreiber (und keine Leser) erfordern, um sicher zu sein. Einige Code:

class IntSetTest 
{ 
private: 
    unsigned short lock; 
    RBTree<int>* myset; 

public: 
    // ... 

    void add_number(int n) 
    { 
     // Aquire once locked==false (atomic) 
     while (__sync_bool_compare_and_swap(&lock, 0, 0xffff) == false); 

     // Perform a thread-unsafe operation on the set 
     myset->insert(n); 

     // Unlock (atomic) 
     __sync_bool_compare_and_swap(&lock, 0xffff, 0); 
    } 

    bool check_number(int n) 
    { 
     // Increment once the lock is below 0xffff 
     u16 savedlock = lock; 
     while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false) 
      savedlock = lock; 

     // Perform read-only operation  
     bool exists = tree->exists(n); 

     // Decrement 
     savedlock = lock; 
     while (__sync_bool_compare_and_swap(&lock, savedlock, savedlock-1) == false) 
      savedlock = lock; 

     return exists; 
    } 
}; 

(lässt annehmen, dass es nicht exception-sicher zu sein braucht)

Ist dieser Code in der Tat Thread-sicher? Gibt es irgendwelche Vor-/Nachteile für diese Idee? Irgendein Rat? Ist die Verwendung von Spinlocks so eine schlechte Idee, wenn die Threads nicht wirklich gleichzeitig sind?

Vielen Dank im Voraus. ;)

Answer 1

Sie benötigen eine volatile Qualifier auf lock, und ich würde auch eine sig_atomic_t machen. Ohne die volatile Qualifier, dieser Code:

u16 savedlock = lock; 
    while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false) 
     savedlock = lock; 

nicht lock wieder lesen, wenn savedlock in dem Körper der while-Schleife zu aktualisieren. Betrachten Sie den Fall, dass lock 0xffff ist. Dann wird vor der Überprüfung der Schleifenbedingung 0xffff sein, so dass der while Zustand vor dem Aufruf __sync_bool_compare_and_swap kurzgeschlossen wird. Da __sync_bool_compare_and_swap nicht aufgerufen wurde, tritt der Compiler keine Speicherbarriere auf, so dass vernünftigerweise davon ausgegangen werden kann, dass sich der Wert lock unter Ihnen nicht geändert hat, und vermeiden Sie es erneut in .

Re: sig_atomic_t, gibt es eine anständige Diskussion here. Die gleichen Überlegungen, die für Signalhandler gelten, würden auch für Threads gelten.

Mit diesen Änderungen würde ich meinen, dass Ihr Code threadsicher wäre. Ich würde jedoch immer noch Mutexe empfehlen, da Sie wirklich nicht wissen, wie lange Ihr RB-Tree-Einsatz im allgemeinen Fall dauern wird (nach meinen vorherigen Kommentaren unter der Frage).

Answer 2

Es ist vielleicht erwähnenswert, dass wenn Sie die Win32-Mutexe verwenden, dass ab Vista ein Thread-Pool für Sie bereitgestellt wird. Abhängig davon, für was Sie den RB-Baum verwenden, können Sie damit ersetzen.

Auch, was Sie beachten sollten, ist, dass atomare Operationen nicht besonders schnell sind. Microsoft sagte, dass sie ein paar hundert Zyklen waren.

Anstatt zu versuchen, die Funktion auf diese Weise zu "schützen", wäre es wahrscheinlich effizienter, die Threads einfach zu synchronisieren, entweder zu einem SIMD/Thread-Pool-Ansatz zu wechseln oder einfach einen Mutex zu verwenden.

Aber natürlich, ohne Ihren Code zu sehen, kann ich wirklich keine Kommentare mehr machen. Das Problem mit Multithreading ist, dass Sie das gesamte Modell von jemandem sehen müssen, um es zu verstehen.