Frage Wie funktioniert Vergleichen und Tauschen?


Ich habe schon einige Posts gelesen, die sagen, dass Vergleichen und Tauschen die Atomizität garantieren, aber ich bin immer noch nicht in der Lage, das zu tun. Das ist ein allgemeiner Pseudocode für den Vergleich und den Tausch -

int CAS(int *ptr,int oldvalue,int newvalue)
{
   int temp = *ptr;
   if(*ptr == oldvalue)
       *ptr = newvalue
   return temp;
}

Wie garantiert dies die Atomarität? Zum Beispiel, wenn ich dies verwende, um einen Mutex zu implementieren,

void lock(int *mutex)
{  
    while(!CAS(mutex, 0 , 1));
}

Wie verhindert dies, dass 2 Threads gleichzeitig den Mutex erhalten? Alle Hinweise würden wirklich geschätzt werden.


10
2018-03-12 00:18


Ursprung


Antworten:


"allgemeiner Pseudocode" ist kein tatsächlicher Code einer CAS- (Vergleichs- und Austausch-) Implementierung. Spezielle Hardware-Anweisungen werden verwendet, um spezielle atomare Hardware in der CPU zu aktivieren. Zum Beispiel in x86 der LOCK CMPXCHG kann verwendet werden (http://en.wikipedia.org/wiki/Compare-and-swap).

In gcc zum Beispiel gibt es __sync_val_compare_and_swap() builtin - die Hardware-spezifische atomare CAS implementiert. Es gibt eine Beschreibung dieser Operation von einem frischen wunderbaren Buch von Paul E. McKenney (Ist parallele Programmierung schwer, und wenn ja, was können Sie dagegen tun?, 2014), Abschnitt 4.3 "Atomare Operationen", Seiten 31-32.

Wenn Sie mehr darüber wissen wollen, wie Sie eine höhere Synchronisation über atomare Operationen aufbauen und Ihr System vor Spinlocks und dem Brennen von CPU-Zyklen beim aktiven Spinnen schützen, können Sie etwas darüber lesen futex Mechanismus in Linux. Erste Arbeit über Futex ist Futexes sind schwierig von Ulrich Drepper 2011; der andere ist LWN-Artikel http://lwn.net/Articles/360699/ (Und das historische ist Fuss, Futexes und Furwocks: Schnelle Userland Locking in Linux, 2002)

Mutex-Sperren, die von Ulrich beschrieben werden, verwenden nur atomare Operationen für "schnellen Pfad" (wenn der Mutex nicht gesperrt ist und unser Thread der einzige ist, der ihn sperren will), aber wenn der Mutex gesperrt war, wird der Thread mit futex schlafen gehen ( FUTEX_WAIT ...) (und es wird die Mutex-Variable mit atomarer Operation markieren, um den Entriegelungs-Thread darüber zu informieren, "dass jemand schläft, der auf diesen Mutex wartet", so dass unlocker weiß, dass er sie mit futex (FUTEX_WAKE, ... .)


16
2018-03-12 00:20



Wie verhindert es, dass zwei Threads die Sperre erhalten? Nun, sobald ein Thread erfolgreich ist, *mutex wird sein 1, sodass der CAS eines anderen Threads fehlschlägt (weil er mit dem erwarteten Wert aufgerufen wird) 0). Das Schloss wird durch Speichern freigegeben 0 im *mutex.

Beachten Sie, dass dies eine seltsame Verwendung von CAS ist, da es im Wesentlichen ist erforderlich eine ABA-Verletzung. Normalerweise würden Sie einfach einen einfachen atomaren Austausch verwenden:

while (exchange(mutex, 1) == 1) { /* spin */ }

// critical section

*mutex = 0;   // atomically

Oder wenn Sie etwas ausgefeilter sein und Informationen darüber speichern möchten, welcher Thread die Sperre hat, können Sie Tricks mit atomic-fetch-and-add durchführen (siehe zum Beispiel den Spinlock-Code des Linux-Kernels).


2
2018-03-12 00:21