Comment fonctionne la comparaison et l’échange

J’ai lu pas mal d’articles qui disaient que comparer et échanger garantissait l’atomicité, mais je ne suis toujours pas en mesure de comprendre comment il fonctionne. Voici un pseudo-code général pour comparer et échanger:

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

Comment cela garantit-il l’atomicité? Par exemple, si je l’utilise pour implémenter un mutex,

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

comment cela empêche-t-il 2 threads d’acquérir le mutex en même temps? Tous les indicateurs seraient vraiment appréciés.

“pseudo-code général” n’est pas un code réel d’implémentation de CAS (comparaison et échange). Des instructions matérielles spéciales sont utilisées pour activer du matériel atomique spécial dans la CPU. Par exemple, dans x86, LOCK CMPXCHG pouvez utiliser LOCK CMPXCHG ( http://en.wikipedia.org/wiki/Compare-and-swap ).

Dans gcc, par exemple, il existe __sync_val_compare_and_swap() intégré – qui implémente un CAS atomique spécifique au matériel. Vous trouverez une description de cette opération dans le nouveau livre merveilleux de Paul E. McKenney ( La programmation parallèle est-elle difficile et, dans l’affirmative, que pouvez-vous faire?, Section 4.3), section 4.3 “Opérations atomiques”, pages 31 à 32.

Si vous voulez en savoir plus sur la création d’une synchronisation de niveau supérieur sur des opérations atomiques et sur la sauvegarde de votre système contre les spinlocks et la gravure de cycles de processeurs sur une rotation active, vous pouvez lire quelque chose sur le mécanisme futex sous Linux. Le premier article sur les futex est que les futex sont délicats pour Ulrich Drepper 2011; l’autre est l’article de LWN http://lwn.net/Articles/360699/ (et l’historique est Fuss, Futexes et Furwocks: Fast Userland Locking sous Linux , 2002).

Les serrures de mutex décrites par Ulrich utilisent uniquement des opérations atomiques pour “fast path” (lorsque le mutex n’est pas verrouillé et que notre thread est le seul à vouloir le verrouiller), mais si le mutex était verrouillé, il se mettait en veille en utilisant futex ( FUTEX_WAIT …) (et il va marquer la variable mutex en utilisant l’opération atomique, pour informer le fil de délocking de “il y a quelqu’un qui dort sur ce mutex”, alors déverrouilleur saura qu’il doit le réveiller en utilisant futex (FUTEX_WAKE, .. .)

Comment cela empêche-t-il deux threads d’acquérir le verrou? Eh bien, une fois que l’un des threads réussit, *mutex 1 , donc le CAS de tout autre thread échouera (car il est appelé avec la valeur attendue 0 ). Le verrou est libéré en stockant 0 dans *mutex .

Notez qu’il s’agit d’une utilisation inhabituelle de CAS, car elle nécessite essentiellement une violation de l’ABA. Typiquement, vous utiliseriez simplement un échange atomique simple:

 while (exchange(mutex, 1) == 1) { /* spin */ } // critical section *mutex = 0; // atomically 

Ou si vous voulez être un peu plus sophistiqué et stocker des informations sur le fil qui a le verrou, vous pouvez faire des trucs avec atomic-fetch-and-add (voir par exemple le code de verrou tournant du kernel Linux).